Skip to content

队列

队列与队列的应用 | 知乎@柠檬沙棘1996

定义

与栈类似，队列（queue）也是一种限定插入与删除操作的线性表，但与栈不同的是，其插入和删除操作被分别限制在表的两端。其特点是先进先出（FIFO），插入操作被限制在队尾，而删除操作被限制在队头。

队列的顺序存储结构

与栈同理，队列也可以基于顺序存储结构与链式存储结构两种方式实现。

顺序队列的实现

#define MaxSize 100
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

使用顺序存储结构，我们可以使得队列的队首对应数组的第一个元素，即下标为 \(0\) 的元素，删除操作就在该位置上进行。但这会导致出队效率较低，因为每次出队后都需要将后面的元素向前移动一位，时间复杂度为 \(O(n)\)。

队尾对应数组的最后一个元素，插入操作只需在该元素后追加元素，无需移动任何元素，时间复杂度为 \(O(1)\)。

出队优化与假溢出

针对出队效率低的问题，我们可以通过指针来定义队首与队尾，从而避免每次出队后都需要将后面的元素向前移动；简单来说，队首不一定对应数组的第一个元素:

出队优化[^1]

实现上，我们可以使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。

基于此设计，数组中包含元素的有效区间为 [front, rear - 1]，此时:

  • 入队操作：将输入元素赋值给 rear 索引处，并将 size 增加 1 。

  • 出队操作：只需将 front 增加 1，size 减少 1 。

出队优化
出队优化

但是仅仅是这样的优化在不断进行入队与出队的过程中可能会遇到所谓的假溢出（false overflow）问题。

假溢出

在顺序存储结构中，假溢出是指队列虽然还有空闲空间，但由于队首元素指针已经出队，导致无法再进行入队操作:

假溢出
假溢出

将队列比作一辆公交车，假溢出现象就可比作是车的前面有位置，但后排位置却是满的；然而没有人会因为后排没位置了就选择等下班公交。

循环队列

利用取模运算，可以在逻辑上将顺序队列视为一个环，从而解决假溢出的问题:

当 rear 指针到达数组末尾时，如果还有空闲空间，就将其移动到数组开头:

循环队列
循环队列

结合上面的概念，就可以将 \(a_5\) 所在的位置，即数组下标为 \(4\) 的位置想象成是接在下标为 \(0\) 空位前的一个“连接位”。这样就利用指针将一个“条形”的线性表连接成了一个“环形”的线性表，即循环队列。

但这样还会有一个问题：

在“首尾相接”前，队尾指针rear永远位于队首指针front的右侧，我们可以通过首尾指针的相对位置差直接判断队列是否已经处于队列满或队列空的状态；但在首尾相接后，rear有可能从右侧靠近front，也有可能从左侧靠近front。这种情况下，当rear == front时，究竟是队列满还是队列空呢？

解决方法有两种：

  • 一是设置一个标志变量来区分空与满两种情况，这种方法相对简单——可以通过判断队列中是否有元素来改变flag的值:

    队列空
    队列空

    队列满
    队列满

  • 二是为队列满的情况设置一种有别于队列空的形式:

    • 当队列空时，rear == front

    • 当队列满时，rear从左侧靠近front，但不会等于front，即在front左侧保留一个空位:

      队列满-无标识值
      队列满-无标识值

    队列满判断公式

    在这种方法中，若队列的最大容量为capacity，则队列满的判断条件为(rear + 1) % capacity == front，其中取余是为了整合rear与front的位置问题。

    队列长度计算公式

    • 当队尾指针rear位于队首指针front的右侧时，队列长度可通过二者相减直接得出，即 rear - front；

    • 当rear位于front左侧时，队列即可分为两部分：

      • 数组首元素至rear的前半部分，即 0 + rear

      • front至数组末元素的后半部分==，即 capacity - front

      二者相加，即为 rear - front + capacity

    整合考虑两种情况，在溢出时取余，即可得出通用计算公式：(rear - front + capacity) % capacity

    第一种解决方法的长度计算在该计算公式的基础上设置flag值为 \(1\) 时直接返回队列最大容量即可。

循环队列的操作

初始化
void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;
}
判空
bool IsEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}
入队
bool EnQueue(SqQueue *Q, ElemType x) {
    if ((Q->rear + 1) % MaxSize == Q->front) {
        return false; // 队满
    }
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize; // 队尾指针加1，取模运算保证循环
    return true;
}
出队
bool DeQueue(SqQueue *Q, ElemType *x) {
    if (Q->front == Q->rear) {
        return false; // 队空
    }
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize; // 队头指针加1，取模运算保证循环
    return true;
}

队列的链式存储结构

链式队列的实现

typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

链式队列的操作

初始化
void InitQueue(LinkQueue *Q) {
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); // 分配头节点空间
    if (!Q->front) {
        exit(OVERFLOW); // 分配失败
    }
    Q->front->next = NULL; // 初始头节点指针域为空
}
判空
bool IsEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}
入队
bool EnQueue(LinkQueue *Q, ElemType x) {
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) {
        exit(OVERFLOW);
    }
    s->data = x;
    s->next = NULL;
    Q->rear->next = s; // 将新节点插入到队尾
    Q->rear = s; // 队尾指针指向新节点
    return true;
出队
bool DeQueue(LinkQueue *Q, ElemType *x) {
    if (Q->front == Q->rear) {
        return false; // 队空
    }
    QueuePtr p = Q->front->next;
    *x = p->data;
    Q->front->next = p->next;
    if (Q->rear == p) {
        Q->rear = Q->front; // 如果队列中只有一个元素，则将队尾指针指向头节点
    }
    free(p);
    return true;
}

顺序队列与链式队列的实现对比

  • 从时间上来看，二者常用操作的时间复杂度都是 \(O(1)\)。

  • 从空间上来看:

    • 循环队列基于定长数组实现，空间是实现分配好的，使用期间不释放，因此无论队列本身的长度多大，实际的空间占用仍是固定的，这就会造成空间浪费

    • 链队列尽管需要一个额外的指针域，但总体上更加灵活

总的来说，可以确定队列长度最大值的情况下，建议使用循环队列；否则使用链队列。

双端队列

相较于普通队列，双端队列（Double-ended Queue）不再将删除和插入操作分别限制在表的头尾，而是允许表的两端均可执行插入与删除操作，看起来就像是将两个相反方向上的队列结合成了一个。

双端队列的引入使得队列的插入与删除操作更加灵活，可以快速实现队列两端的元素访问与删除。

Tip

由于双端队列两端均可插入与删除元素，因此它还可以用于实现栈，即双端队列作为栈使用时，仅使用一端进行插入与删除操作。