队列的定义

队列是指在表的一端进行插入操作，在另一端进行删除操作的一种数据结构。它是一种先进先出的线性表，就如同日常生活中排队的场景一样，最早进入队列的人最早离开。在队列中，先进入的一端称为队头（front），后进入的一端称为队尾（rear）。

队列的抽象数据类型的定义：

ADT Queue{
    数据对象；
    数据关系；
    
    基本操作：
        InitQueue(&Q)
            操作结果：创造一个空队列
        ClearQueue(&Q)
            初始条件：存在一个队列
            操作结果：清空这个队列
        QueueEmpty(Q)
            初始条件：存在一个队列
            操作结果：判断Q是否为空队列
        QueueLength(Q)
            初始条件：存在一个队列
            操作结果：得到这个队列的长度（元素的个数）
        InQueue(&Q,e)
            初始条件：存在一个队列
            操作结果：插入元素e到队列Q的队尾
        DeQueue(&Q)
            初始条件：存在一个队列
            操作结果：删除队列中的队首元素
        GetHeadQueue(Q,&e)
            初始条件：存在一个队列
            操作结果：用e返回Q的头元素的值
}

队列的存储表示及实现

队列的存储表示有两种，分别为顺序存储和链式存储。采用顺序存储结构的队列称为顺序队列，采用链式存储的队列称为链式队列。

存储表示

1.顺序队列的表示及实现

1.宏定义解释

#define QueueSize 100  //队列的容量
#define ERROR 0;
#define OK 1;

2.结构类型

typedef struct{
    int data[QueueSize];  //定义数组的最大容量
    int front;      // 头指针
    int rear;       //尾指针
}SqQueue;

3.基本操作的实现

（1）初始化队IinitQueue

int InitQueue(SqQueue &Q){
    Q.front=0;  //头指针指向0
    Q.rear=0;  //尾指针指向0
    return OK;
}

（2）清空队列ClearQueue

int ClearQueue(SqQueue &Q){
    Q.front=Q.rear=0;
    return OK;
}

（3）判断队列是否为空QueueEmpty

int QueueEmpty(SqQueue Q){
    if(Q.front==Q.rear)  //如果头指针和尾指针指向一样的，则是空队列
        return TRUE;
    else
        return FALSE;
}

（4）求队列的长度QueueLength

int QueueLength(SqQueue Q){
    return(Q.rear-Q.front);  //直接相减就是长度
}

（5）将元素入队列InQueue

int InQueue(SqQueue &Q,int x){
//将元素x放在队尾当中
    if(Q.front==QueueSize)
        return ERROR;
    else
    {
        Q.data[Q.rear]=x;
        (Q.rear)++;
    }
    return OK;
}

（6）将元素删除DeQueue

int DeQueue(SqQueue &Q){
//将队首元素删除并返回
    int x;
    if(Q.front==Q.rear)
        return ERROR;
    else
    {
        x=Q.data[Q.front];
        (Q.front)++;  //front指针后移
    }
    return x;
}

（7）返回队首元素GetheadQueue

int GetheadQueue(SqQueue Q,int &e){
//将队首元素的值返回
    if(Q.front==Q.rear)  //如果是空队列
        return ERROR;
    e=Q.data[Q.front];
    return OK;
}

---

需要注意的是，在对顺序队列进行插入和删除操作的过程中，可能会出现假溢出现象，即经过多次插入和删除操作后，实际上队列还有存储空间，但是又无法向队列中插入元素的现象。例如下图所示，当在队列中插入元素33之后，尾指针按照“规则”会后移一位，这时就超出了数组在宏定义中所定义的容量大小，造成假溢出。

假溢出

2.循环队列的表示及实现

循环队列即当队尾指针rear和队头指针front到达存储空间的最大值的时候，让这两个指针转化为0，这样就可以将元素插入到队列中还没有利用的存储单元当中。例如上图当中，在33插入之后，rear将变为0，这时可以继续将元素插入下标为0的存储单元中。这样就构成了一个首尾相连的队列。

循环队列

1.宏定义解释

#define QueueSize 100  //初始容量
#define ERROR 0;
#define OK 1;

2.结构类型

typedef struct Squeue{
    DataType data[QueueSize];  //存储元素的数组
    int front;  //头指针
    int rear;  //尾指针
}SeqQueue;

3.基本操作

（1）初始化InitQueue

int InitQueue(SeqQueue &Q){
    Q.front=0;
    Q.rear=0;
    return OK;
}

（2）清空队列ClearQueue

int ClearQueue(SeqQueue &Q){
    Q.front=0;
    Q.rear=0;
    return OK;
}

（3）判断队列是否为空QueueEmpty

int QueueEmpty(SeqQueue Q){
    if(Q.front==Q.rear)  //如果头指针和尾指针指向一样的，则是空队列
        return TRUE;
    else
        return FALSE;
}

（4）求队列的长度QueueLength

int QueueLength(SeqQueue Q){
    return(Q.rear-Q.front+QueueSize)%SqueueSize;  //循环队列有特殊情况
}

（5）将元素入队InQueue

int InQueue(SeqQueue &Q,int x){
//将元素x插入到队列中
    if(Q.front==((Q.rear+1)%QueueSize){  //判断是否会假溢出
        return ERROR;
    }
    else{
        Q.data[Q.rear]=x;  //将x插入到尾指针处
        Q.rear=(Q.rear+1)%QueueSize;  //尾指针后移（注意循环）
        return OK;
    }
}

（6）将元素删除DeQueue

int DeQueue(SeqQueue &Q){
//将队头元素删除并返回
    int x
    if(Q.front==Q.rear){  //判断是否为空
        return ERROR;
    }
    else{
        x=Q.data[Q.front];  //将队头元素赋给x
        Q.front=(Q.front+1)%QueueSize;  //队头指针指向后面一个
        return x;  //返回x
    }
}

（7）返回队首元素GetheadQueue

int GetheadQueue(SqQueue Q,int &e){
//将队首元素的值返回
    if(Q.front==Q.rear)  //如果是空队列
        return ERROR;
    e=Q.data[Q.front];
    return OK;
}

3.链式队列的表示及实现

一个链式队列通常用链表来实现。其中，链表包括两个域：数据域和指针域。使用的方法是和链表相似的。在链式队列中，指向第一个元素位置的指针称为队头指针front，而指向最后一个元素位置的指针称为队尾指针rear。同样为了操作方便，我们可以在链式队列的第一个结点之前添加一个头结点，并让队头指针指向头结点。

1.结构类型

typedef struct QNode{
//结点类型的定义
    DataType data;  //数据域
    struct QNode* next;  //指针域
}LQNode,*QueuePtr;

typedef struct{
//队列类型的定义
    QueuePtr front;  //头指针
    QueuePtr rear;  //尾指针
}LinkQueue;

2.基本操作的实现

（1）链式队列的初始化InitQueue

void InitQueue(LinkQueue *LQ){
    LQ->front=LQ->rear=(LQNode*)malloc(sizeof(LQnode));
    if(LQ->front==NULL){
        exit(-1);
    }
    LQ->front->next=NULL;  //把头结点的指针域置为0
}

（2）清空链式队列ClearQueue

void ClearQueue(LinkQueue *LQ){
    while(LQ->front!=NULL){
        LQ->rear=LQ->front->next;  //队尾指针指向队头指针的下一个
        free(LQ->front);  //释放掉此时的队头的结点
        LQ->front=LQ->rear;  //队头指向队尾
    }
}

（3）判断队列是否为空QueueEmpty

int QueueEmpty(LinkQueue LQ){
    if(LQ.front->next==NULL){
        return 1;  //若头结点的指针域为空，则队列为空，返回1
    }
    else{
        return 0;  //不为空则返回0
    }
}

（4）入队操作InQueue

int InQueue(LinkQueue *LQ,DataType e){
    LQNode *s;  //创建一个新的结点
    s=(LQNode*)malloc(sizeof(LQNode));  //为新的结点申请空间
    if(!s){
        exit(-1);  //如果申请失败则退出
    }
    s->data=e;  //新结点的数据域为e
    s->next=NULL;  //新结点的指针域指向空
    LQ->rear->next=s;  //原来队列的尾指针指向s
    return OK;
}

（5）出队操作DeQueue

int DeQueue(LinkQueue *LQ,DataType *e){
    LQNode *s;  //创建一个新的结点
    if(LQ->front==LQ->rear){  //判断是否为空
        return ERROR;
    }
    else{
        s=LQ->front->next;  
        *e=s->data;
        LQ->front->next=s->next;
        free(s);  //释放掉队头元素
        return OK;
    }
}

（6）取队头元素GetHeadQueue

int GetHeadQueue(LinkQueue LQ,DataType *e){
    LQNode *s;
    if(LQ.front==LQ.rear){
        return ERROR;
    }
    else{
        s=LQ->front->next;  //指向队头元素的位置
        *e=s->data;
        return OK;
    }
}