一.循环队列

1.构建结构

//定义队列的结构
typedef struct{
    //队头
    int front;
    //队尾
    int real;
    //队空间(静态空间)
    SElemType data[MAXSIZE];
} SqQueue;

2.初始化队列

//初始化队列
Status InitQueue(SqQueue *queue){
    queue->front = queue->real = 0;
    return OK;
}

3.清空队列

//清空队列
Status ClearQueue(SqQueue *queue){
    if (!queue) {
        return ERROR;
    }
    queue->front = 0;
    queue->real = 0;
    return OK;
}

4.判断是否为空队列

//判断队列是否为空
Status EmptyQueue(SqQueue queue){
    if (queue.front == queue.real) {
        return TRUE;
    }
    return FALSE;
}

5.获取队列的长度

//获得队列的长度
int GetQueueLength(SqQueue queue){
    return (queue.real - queue.front + MAXSIZE)%MAXSIZE;
}

6.便利队列

//遍历队列
Status TraversalQueue(SqQueue queue){
    printf("队列内容是：\n");
    //从队头开始遍历
    int i = queue.front;
    //因为是循环队列，所以从队头开始查到队尾结束，%MAXSIZE是为了取具体位置
    while ((i + queue.front)%MAXSIZE != queue.real) {
        printf("%d\n",queue.data[i]);
        i = (i+1)%MAXSIZE;
    }
    return OK;
}

7.入队

//入队
Status PushQueue(SqQueue *queue, SElemType data){
    if ((queue->real + 1)%MAXSIZE == queue->front) {//队满了
        return ERROR;
    }
    queue->data[queue->real] = data;
    //以为你是循环队列，所以real不能一直++，估要+1后%MAXSIZE
    queue->real = (queue->real + 1)%MAXSIZE;
    return OK;
}

8.出队

//出队
Status PopQueue(SqQueue *queue, SElemType *data){
    if (queue->front == queue->real) {//空队列
        return ERROR;
    }
    *data = queue->data[queue->front];
    printf("出队的是：%d\n",*data);
    queue->front = (queue->front + 1)%MAXSIZE;
    return OK;
}

二.链式队列

无需关心队列是否满了
内存空间不连续
链式需要关心节点的释放

1.节点结构

//构造队列结点
typedef struct QNode {
    SElemType data;
    struct QNode *next;
}QNode,*QListNode;
//构造队列
typedef struct{
    QListNode front;
    QListNode real;
    //用来记录队列的长度
    int count;
} SQueue;

2.初始化链式队列

//初始化链式队列
Status InitNodeQueue(SQueue *queue){
    queue->front = queue->real = (QListNode)malloc(sizeof(QNode));
    if (!queue->front) {
        return ERROR;
    }
    //队头指向Null
    queue->front->next = NULL;
    queue->count = 0;
    return OK;
}

3.判断是否为空的链式队列

//是否是空的链式队列
Status EmptyNodeQueue(SQueue queue){
    if (queue.front == queue.real) {
        return TRUE;
    }
    return FALSE;
}

4.清空队列

//将链式队列清空
Status ClearNodeQueue(SQueue *queue){
    if (queue->front == queue->real) {//如果是空队列
        printf("空队列\n");
        return ERROR;
    }
    queue->real = queue->front;
    queue->count = 0;
    QListNode p = queue->front->next,temp;
    queue->front->next = NULL;
    while (p) {
        temp = p;
        free(p);
        p = temp->next;
    }    return OK;
}

5.链式队列的长度

//获得链式队列的长度
int GetNodeQueueLenght(SQueue queue){
    /*
     //方法一
    if (queue.front == queue.real) {//空队列
        return 0;
    }
    int i = 1;
    QListNode p = queue.front->next;
    while (p) {
        p = p->next;
        if (p) {
            i++;
        }
    }
    return i;
    */
    //方法二：
    return queue.count;
}

6.便利链式队列

//遍历链式队列
Status TraversalNodeQueue(SQueue queue){
    if (queue.front == queue.real) {
        printf("空队列\n");
        return ERROR;
    }
    printf("队列内容：");
    QListNode p = queue.front->next;
    while (p) {
        printf("%4d",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

7.链式队列入队

//入队
Status PushNodeQueue(SQueue *queue, SElemType data){
    //链式队列无需判断队满
    QListNode temp = (QListNode)malloc(sizeof(QNode));
    temp->data = data;
    temp->next = NULL;
    //修改队尾指向的结点
    queue->real->next = temp;
    //更新队尾
    queue->real = temp;
    //队的长度自增1
    queue->count++;
    return OK;
}

8.链式队列出队

//出队
Status PopNodeQueue(SQueue *queue, SElemType *data){
    if (queue->front == queue->real) {
        printf("空队列\n");
        return ERROR;
    }
    //获得队头结点
    QListNode temp = queue->front->next;
    *data = temp->data;
    //更新队头指向的结点
    queue->front->next = temp->next;
    free(temp);
    return OK;
}