3.2 队列

先进先出的线性表：顺序队列的假溢出、循环队列的三种判满方案、链队列与双端队列。

队列的定义

向队列中插入元素称为入队或进队，删除元素称为出队或离队。队列的操作特性是先进先出（First In First Out，FIFO），就像排队买饭。

顺序队列与假溢出

用数组存放队列元素，并附设两个指针：front 指向队头元素，rear 指向队尾元素的下一个位置。

• 初始状态（队空）：Q.front == Q.rear == 0
• 入队：先送值到队尾，再将队尾指针加 1
• 出队：先取队头元素，再将队头指针加 1

问题来了：能否用 Q.rear == MaxSize 作为队满的条件？不能。如下图，队列中只有一个元素，但 rear 已经等于 MaxSize，再入队就会”溢出”——然而数组前面明明还有空位。这种现象称为假溢出。

循环队列

解决假溢出的办法是：把存储队列的数组从逻辑上视为一个环，称为循环队列。当队首指针 Q.front = MaxSize − 1 后，再前进一个位置就自动到 0，这可以利用取余运算 % 来实现：

• 队首指针进 1：Q.front = (Q.front + 1) % MaxSize
• 队尾指针进 1：Q.rear = (Q.rear + 1) % MaxSize
• 队列长度：(Q.rear − Q.front + MaxSize) % MaxSize

1#define MaxSize 8
2typedef struct {
3    ElemType data[MaxSize];
4    int front, rear;     // 队头指针、队尾指针
5} SqQueue;
6// 初始化：Q.front = Q.rear = 0
7bool EnQueue(SqQueue &Q, ElemType x) {
8    if ((Q.rear + 1) % MaxSize == Q.front)
9        return false;                    // 队满
10    Q.data[Q.rear] = x;
11    Q.rear = (Q.rear + 1) % MaxSize;     // 队尾指针加 1 取模
12    return true;
13}
14bool DeQueue(SqQueue &Q, ElemType &x) {
15    if (Q.rear == Q.front)
16        return false;                    // 队空
17    x = Q.data[Q.front];
18    Q.front = (Q.front + 1) % MaxSize;   // 队头指针加 1 取模
19    return true;
20}
21// 队列长度：(Q.rear - Q.front + MaxSize) % MaxSize

如何区分队空与队满？

在循环队列中，队空时 front == rear；如果入队速度快于出队，队尾指针很快会追上队首指针，此时队满时也有 front == rear。为了区分，有三种处理方式：

1. 牺牲一个单元（最常用，也是上面动画采用的方式）：约定”队头指针在队尾指针的下一位置作为队满的标志”。
   • 队满：(Q.rear + 1) % MaxSize == Q.front
   • 队空：Q.front == Q.rear
   • 元素个数：(Q.rear − Q.front + MaxSize) % MaxSize
2. 增设 size 数据成员：队空 Q.size == 0，队满 Q.size == MaxSize，两种情况都有 front == rear。
3. 增设 tag 数据成员：tag == 0 时若因删除导致 front == rear 则为队空；tag == 1 时若因插入导致 front == rear 则为队满。

链队列

队列的链式表示称为链队列，它实际上是一个同时有队头指针和队尾指针的单链表。头指针指向队头结点，尾指针指向队尾结点。

typedef struct LinkNode {
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {
    LinkNode *front, *rear;    // 队头和队尾指针
} LinkQueue;

void EnQueue(LinkQueue &Q, ElemType x) {          // 带头结点
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x; s->next = NULL;
    Q.rear->next = s;          // 插到队尾
    Q.rear = s;
}
bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false;          // 空队
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)           // 若原队列只有一个结点，删除后变空
        Q.rear = Q.front;
    free(p);
    return true;
}

双端队列

双端队列是指允许两端都可以进行插入和删除操作的线性表。

• 输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入；
• 输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除。

即时练习