数据结构——队列及循环队列

说明：严蔚敏的《数据结构》（C语言版）学习笔记，记录一下，以备后面查看。

#include <stdio.h>
#include <stdlib.h>

#define OK 1;
#define ERROR -1;

typedef int QElemType;
typedef int Status;

//定义队列节点
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

//队列
typedef struct{
    QueuePtr front;  //队头指针
    QueuePtr rear;   //队尾指针
}LinkQueue;

//初始化队列
Status InitQueue(LinkQueue *q){
    q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!q->front) return ERROR;
    q->front->next = NULL;
    return OK;
}

//销毁队列
Status DestroyQueue(LinkQueue *q){
    while(q->front){
        q->rear = q->front->next;
        free(q->front);
        q->front = q->rear;
    }
    return OK;
}

//插入元素
Status EnQueue(LinkQueue *q, QElemType e){
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) return ERROR;
    p->data = e;
    p->next = NULL;
    q->rear->next = p; //队列末尾指向p
    q->rear = p; //p记为尾指针
    return OK;
}

//出队列
Status DeQueue(LinkQueue *q, QElemType *e){
    if(q->front == q->rear) return ERROR;
    QueuePtr p = q->front->next; //指向队列头部第一个元素
    *e = p->data;
    q->front->next = p->next;
    if(q->rear == p) q->rear = q->front;
    free(p);
    return OK;
}

初始化的时候,让front和rear都等于0，此时队列元素个数是0,当入队4个元素后如下图

此时对队列元素的个数是 rear - front = 4, 假如队列变为下面的样子，rear < front

队列中空一格的原因是为了区别队列是“空”还是“满”，当队列尾指针的下一个位置是头指针则说明队列满了。

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR -1
#define MAXQSIZE 100 //最大队列长度

typedef int QElemType;
typedef int Status;

//循环队列
typedef struct{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

//初始化循环队列
Status InitQueue(SqQueue *q){
    q->base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if (!q) return ERROR;
    q->front = q->rear = 0;
    return OK;
}

//获取队列长度
int QueueLength(SqQueue *q){
    return (q->rear - q->front + MAXQSIZE) % MAXQSIZE;
}

//入队
Status EnQueue(SqQueue *q, QElemType e){
    if ((q->rear + 1) % MAXQSIZE == q->front) {
        return ERROR;
    }
    q->base[q->rear] = e;
    q->rear = (q->rear + 1) % MAXQSIZE;
    return OK;
}

//出队
Status DeQueue(SqQueue *q, QElemType *e){
    if(q->front == q->rear) return ERROR;
    *e = q->base[q->front];
    q->front = (q->front + 1) % MAXQSIZE;
    return OK;
}