队列基础

1. 队列的定义

    队列是一种特殊的线性表，它包含一个队头（front）和一个队尾（rear），其中队头只允许删除元素，队尾只允许插入元素。队列的特定是先进入队列的元素先出来，即先进先出（FIFO）。出队列时，只有当前面的元素都退出之后，后面的元素才能退出。

                                                  

                                                                    图 队列示意图

2. 队列的操作

    队列的主要操作有下面6种：

    （1）InitQueue(&Q)：初始化操作，独立一个空队列Q。

    （2）QueueEmpty(Q)：若Q为空队列，返回1，否则返回0。

    （3）EnterQueue(&Q,x)：插入元素X到队列Q的队尾。

    （4）DeleteQueue(&Q,&e)：删除Q的队首元素，并用e返回其值。

    （5）Gethed(Q,&e)：用e返回Q的队首元素。

    （6）ClearQueue(&Q)：将队列Q清空。

3. 队列的顺序存储

    队列有两种存储方式：顺序存储和链式存储。采用顺序存储结构的队列称为顺序队列，采用链式存储结构的队列称为链式队列。

    链式队列通常采用一维数组进行存储。其中，连续的存储单元一次存放队列中的元素。同时，使用两个指针分别表示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的位置指针称为队头指针front，指向最后一个元素位置的指针称为队尾指针rear。

    顺序队列的类型定义如下：

#define QueueSize 40    /* 队列的容量 */
typedef struct Squeue{
        DataType queue[QueueSize];
        int front,rear;           /* 队头指针和队尾指针 */
}SeqQueue;

    顺序队列会出现“真溢出”和“假溢出”现象。所谓“真溢出”是指插入元素已超过分配的存储空间，不能再继续插入元素；而“假溢出”是指队尾指针已经达到数组的尾端，而队头指针之前有删除元素后留下的剩余空间，这是经过多次插入和删除操作引起的，像这种有存储空间而不能再进行插入元素操作的溢出称为“假溢出”。

                             

                                                                         图 假溢出示意图

    为了避免顺序队列造成“假溢出”现象，通常采用顺序循环队列来实现队列的顺序存储。为了充分利用存储空间，消除“假溢出”现象，就是当队尾指针rear和队头指针front到达存储空间的最大值QueueSize时，让队尾指针和队头指针自动转化为存储空间的最小值0。这样就把顺序队列使用的存储空间构造成一个逻辑上首尾相连的循环队列。注意：顺序循环队列中的入队操作和出队操作都要取模，确保操作不出界。

                          

                                                                        图 顺序循环队列

4. 队列的链式存储

    为了避免顺序队列在进行插入和删除操作时大量移动元素，可以采取链式存储结构表示队列。一个链式队列通常采用链表实现。其中，链表包括两个域：数据域和指针域。数据域用来存放队列中的元素，指针域用来存放队列中下一个元素的地址。同时，使用两个指针分别指示链表中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素位置的指针称为队头指针front，指向最后一个元素的位置的指针称为队尾指针rear。

    链式队列的类型定义如下：

/* 节点类型定义 */
typedef struct QNode
{
        DataType data;
        struct QNode* next;
}LQNode, *QueuePtr;
/* 队列类型定义 */
typedef struct
{
        QueuePtr front;
        QueuePtr rear;
}LinkQueue;

                                                              

                                                                               图 链式队列示意图

5. 双端队列

    双端队列是一种特殊的队列，它是在线性表的两端对插入和删除操作限制的线性表。双端队列可以再队列的任何一端进行插入和删除操作，而一般的队列要求在一端插入元素，另一端删除元素。

    输入受限的双端队列：线性表的两端都可以输出数据元素，但是只能在一端输入数据元素。
    输出受限的双端队列：线性表的两端都可以输入数据元素，但是只能在一端输出数据元素。

                                              

                                                                                      图 双端队列示意图