队列

循环队列

#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <iostream>

#define MaxSize 5
typedef int ElementType;

typedef struct{
    ElementType data[MaxSize]; // 数组，存储MaxSize -1 个元素 (为什么，用来判断队列是否是满的)
    int front; // 队列头
    int rear; // 队列尾     
}SqQueue;


void InitQueue(SqQueue &Q){
    Q.front = Q.rear = 0;
}

bool isEmpty(SqQueue Q){
    if(Q.front == Q.rear) return true;
    return false;
}

bool EnQueue(SqQueue &Q, ElementType element){
    if((Q.rear+1)%MaxSize == Q.front) return false; // 队列已经满了
    Q.data[Q.rear] = element;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

bool DeQueue(SqQueue &Q, ElementType & e){
    // 判断队里是否为空
    if(isEmpty(Q)) return false;
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) %MaxSize;
    return true;
}


int main() {
    SqQueue Q;
    bool ret;
    ElementType element;
    InitQueue(Q);
    ret = isEmpty(Q);
    if(ret) {
        puts("当前队列为空");
    }

    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);

    ret = DeQueue(Q,element);
    if(ret) {
        puts("出队成功");
        printf("出队元素为%d", element);
    }
}

使用链表实现队列

初始化队列

入队

#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <iostream>


typedef int ElementType;

typedef struct LinkNode{
    ElementType data;
    struct LinkNode * next;
}LinkNode;

typedef struct{
    LinkNode *front;
    LinkNode *rear;    
}LinkQueue;


void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

// 使用尾部插入法
bool EnQueue(LinkQueue &Q, ElementType element){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = element;
    s->next = NULL;
    Q.rear->next = s; // 让rear始终指向最后一个元素
    Q.rear = s; 
}

// 使用头部删除法
bool DeQueue(LinkQueue &Q, ElementType & e){
    if(Q.front == Q.rear) return false; // 队列为空
    LinkNode *p = Q.front->next; // 头结点什么都没有存，所以头结点的下一个节点才有数据
    e = p->data;
    Q.front->next = p->next;   // 断链
    if(Q.rear == p) { // 如果删除的是最后一个元素
        Q.rear = Q.front;
    }

    free(p);
    return true;
}


int main() {
    LinkQueue Q;
    bool ret;
    ElementType element;

    // 初始化
    InitQueue(Q);

    // 入队
    EnQueue(Q, 3);
    EnQueue(Q, 4);
    EnQueue(Q, 5);
    EnQueue(Q, 6);

    // 出队
    ret = DeQueue(Q,element);

    if(ret) {
        puts("出队成功");
        printf("出队元素为%d", element);
    }
}