数据结构：队列

• 顺序队
  • 类型定义
  • 基本运算
    • 初始化顺序队
    • 销毁顺序队
    • 判断是否为空队
    • 进队
    • 出队
• 循环队列
  • 基本运算
    • 初始化循环队列
    • 销毁循环队列
    • 判断是否为空队
    • 进队
    • 出队
• 链队
  • 类型定义
  • 基本运算
    • 初始化链队
    • 销毁链队
    • 判断是否为空队
    • 进队
    • 出队

队列（Queue）简称为队，它也是一种运算「受限」的线性表，其限制仅允许在表的一端进行插入，而在表的另一端进行删除。把进行插入的一端称做队尾（Rear），进行删除的一端称做队首或队头（Front）。向队列中插入新元素称为进队或入队（Enqueue），新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队（Dequeue），元素出队后，其后继元素就成为队首元素。

队列的主要特点是「先进先出」，因为队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序出队，所以又把队列称为先进先出表。

顺序队

顺序队是队列的顺序存储结构，把元素按照其进队的顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。

约定：

• q->rear指向队尾元素
• q->front指向队头元素的前一个位置
• 初始化时front = rear = -1

顺序队的四个要素：

• 队空条件：q->front == q->rear
• 队满条件：q->rear == MaxSize - 1
• 进队操作：q->rear++;并将要进队的元素e放在q->rear处
• 出队操作：q->front++;并从q->front处取出要出队元素e

当队列非空时，元素的个数$m$可用q->rear - q->front计算得到，可见：

• 队满时$m=$ MaxSize​
• 队空时$m=0$

当队空时，做出队操作，这种现象称为下溢。当队列满时，再做入队操作，这种现象称为上溢。

类型定义

注意：front和rear是整型变量，头指针front总是指向队列中队头元素的前一个位置，而尾指针rear总是指向队列中队尾元素的所在位置。

#define ElemType int        // 元素类型
#define MaxSize 10          // 最大长度
typedef struct
{
    ElemType data[MaxSize];
    int front, rear;        // 队首和队尾指针
} SqQueue;

基本运算

初始化顺序队

构造一个空队列$q$。将front和rear指针均设置成初始状态，即$-1$值。

// 初始化顺序队
void initQueue(SqQueue *&q)
{
    q = (SqQueue *) malloc(sizeof(SqQueue));
    q->front = q->rear = -1;
}

销毁顺序队

// 销毁顺序队
void destroyQueue(SqQueue *&q)
{
    free(q);
}

判断是否为空队

// 判断是否为空队
bool isEmpty(SqQueue *q)
{
    return q->front == q->rear;
}

进队

在队列不满的条件下，先将队尾指针rear增$1$，然后将元素添加到该位置。

// 进队
bool enQueue(SqQueue *&q, ElemType e)
{
    if (q->rear == MaxSize - 1) return false;   // 队满上溢出
    q->rear++;
    q->data[q->rear] = e;
    return true;
}

出队

在队列$q$不为空的条件下，将队首指针front增$1$，并将该位置的元素值赋给$e$。

// 出队
bool deQueue(SqQueue *&q, ElemType &e)
{
    if (q->front == q->rear) return false;  //队空下溢出
    q->front++;
    e = q->data[q->front];
    return true;
}

循环队列

为了能够充分地使用数组中的存储空间，并解决队列的「假溢出」问题，把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，称为循环队列或环形队列（Round-Robin Queue）。

解决假溢出的方法：把数组q->data从逻辑上看成一个环，即规定q->data[0]是q->data[MaxSize - 1]的下一个元素。当q->data[MaxSize - 1]已经插入元素以后，就把q->rear置成$0$，再有元素插入时，就插到q->data[0]的位置上。

当循环队列出现「队空」和「队满」状态时，条件均为q->front == q->rear

为解决循环队列中「队空」和「队满」时条件相同的问题，可采用此方法：少用一个元素空间，把下图所示的情况视为队满，此时的状态是队尾指针加1就会从后面赶上队头指针，此时队满的条件是： (q->rear + 1) % MaxSize == q->front

循环队列的四个要素：

• 队空条件：q->front == q->rear
• 队满条件：(q->rear + 1) % MaxSize == q->front
• 进队操作：q->rear = (q->rear + 1) % MaxSize;并将要进队的元素e放在q->rear处
• 出队操作：q->front = (q->front + 1) % MaxSize;并从q->front处取出要出队元素e

基本运算

初始化循环队列

构造一个空队列$q$。将front和rear指针均设置成初始状态，即$0$值。

// 初始化循环队列
void initQueue(SqQueue *&q)
{
    q = (SqQueue *) malloc(sizeof(SqQueue));
    q->front = q->rear = 0;
}

销毁循环队列

// 销毁循环队列
void destroyQueue(SqQueue *&q)
{
    free(q);
}

判断是否为空队

// 判断是否为空队
bool isEmpty(SqQueue *q)
{
    return q->front == q->rear;
}

进队

在队列不满的条件下，先将队尾指针rear循环增$1$，然后将元素添加到该位置。

// 进队
bool enQueue(SqQueue *&q, ElemType e)
{
    // 队满上溢出
    if ((q->rear + 1) % MaxSize == q->front) return false;
    q->rear = (q->rear + 1) % MaxSize;
    q->data[q->rear] = e;
    return true;
}

出队

在队列$q$不为空的条件下，将队首指针front循环增$1$，并将该位置的元素值赋给$e$。

// 出队
bool deQueue(SqQueue *&q, ElemType &e)
{
    // 队空下溢出
    if (q->front == q->rear) return false;
    q->front = (q->front + 1) % MaxSize;
    e = q->data[q->front];
    return true;
}

链队

队列的链式存储结构称为链队，采用单链表实现。

链队的四个要素：

• 队空条件：q->front == NULL || q->rear == NULL
• 队满条件：不考虑
• 进队操作：将包含e​的结点插入到单链表表尾
• 出队操作：删除单链表首数据结点

类型定义

链队中数据结点类型DataNode定义如下:

#define ElemType int        // 元素类型
typedef struct QNode
{
    ElemType data;          // 数据元素
    struct QNode *next;
} DataNode;

链队结点类型LinkQuNode定义如下:

typedef struct
{
    DataNode *front;        // 指向单链表队头节点
    DataNode *rear;         // 指向单链表队尾节点
} LinkQuNode;

基本运算

初始化链队

构造一个空队列，即只创建一个链队结点，其front和rear域均置为NULL。

// 初始化链队
void initQueue(LinkQuNode *&q)
{
    q = (LinkQuNode *) malloc(sizeof(LinkQuNode));
    q->front = q->rear = NULL;
}

销毁链队

释放链队占用的存储空间，包括链队结点和所有数据结点的存储空间。

// 销毁链队
void destroyQueue(LinkQuNode *&q)
{
    DataNode *pre = q->front, *p;   // p指向队头数据节点
    if (pre != NULL)                // 释放数据节点占用空间
    {
        p = pre->next;
        while (p != NULL)
        {
            free(pre);
            pre = p;
            p = p->next;
        }
    }
    free(pre);						// 以上与单链表销毁的方法相同
    free(q);                        // 释放链队节点占用空间
}

判断是否为空队

// 判断是否为空队
bool isEmpty(LinkQuNode *q)
{
    return q->rear == NULL;
}

进队

创建data域为e的数据结点$p$。若原队列为空，则将链队结点的两个指针域均指向结点$p$，否则将结点$p$链到单链表的末尾，并让链队结点的rear域指向它。

// 进队
void enQueue(LinkQuNode *&q, ElemType e)
{
    DataNode *p;
    p = (DataNode *) malloc(sizeof(DataNode));
    p->data = e;
    p->next = NULL;
    if (q->rear == NULL)    // 若链队为空, 新结点是队首结点又是队尾结点
    {
        q->front = q->rear = p;
    } else
    {
        q->rear->next = p;  // 将p结点链到队尾, 并将rear指向它
        q->rear = p;
    }
}

出队

若原队列不为空，则将第一个数据结点的data域值赋给e并删除。若出队之前队列中只有一个结点，则需将链队结点的两个指针域均置为NULL，表示队列已为空。

bool deQueue(LinkQuNode *&q, ElemType &e)
{
    DataNode *t;
    if (q->rear == NULL) return false;  // 队列为空
    t = q->front;                       // t指向第一个数据结点
    if (q->front == q->rear)            // 队列中只有一个结点时
    {
        q->front = q->rear = NULL;
    } else                              // 队列中有多个结点时
    {
        q->front = q->front->next;
    }
    e = t->data;
    free(t);
    return true;
}