数据结构：队列

和栈类似，队列也是一个特殊的线性表。队列在计算机系统中也有着广泛的应用。例如，在操作系统中，队列可以用于进程调度，确保按照先来先服务的原则进行任务分配。在网络通信中，队列可以用于缓存数据包，以平衡发送和接收之间的速度差异。在计算机算法中，队列可以用于广度优先搜索等算法的实现。

队列是一个很基础的数据结构，因此也需掌握。

一、简介

队列（Queue）是限定在表头删除、表尾插入的线性表。对于队列来说，允许删除的一端称为队头（front），允许插入的一端称为队尾（rear）。

队列的操作具有先进先出的特点。因此，队列又被称作FIFO（First In First Out）表。假设队列Q=(a1a_1, a2a_2, …, ana_n)，若队列中元素是按a1a_1, a2a_2, …, ana_n的顺序依次入队的，则称a1a_1为队头元素，ana_n为队尾元素。其出队次序只能按a1a_1, a2a_2, …, ana_n的次序进行，也就是说，只有在a1a_1, a2a_2, …, an−1a_{n-1}都离开队列之后，ana_n才能出队。队列的这个特点，和日常生活中的排队场景是一致的，最早进入队的最先离开。

img

同样地，队列也有两种存储结构，分别是顺序队列和链式队列。

二、顺序队列

顺序队列，是指采用顺序存储结构实现的队列。

在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队头到队尾的元素之外，还需附设两个整型变量front和rear分别指示队头元素及队尾元素的位置。通常，front被称为头指针，rear被称为尾指针。

在C语言中，顺序队列的类型描述如下：

1
2
3
4
5
6
7
8
9
10
11
// 队列可能达到的最大长度
#define MAXQSIZE

typedef struct {
    // 存储空间的基地址
    QElemType *base;
    // 头指针
    int front;
    // 尾指针
    int rear;
}SqQueue;

为了描述方便起见，在此约定：初始化创建空队列时，令front=rear=0，每当插入新的队尾元素时，尾指针rear增1；每当删除队头元素时，头指针front增1。因此，在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置，其结构如下图所示：

image-20231223175506541

假设当前队列的最大空间为6，则当队列处于上图（d）所示的状态时，就不可再继续插入新的队尾元素，否则会出现溢出现象，即因数组越界而导致程序的非法操作错误。事实上，此时队列的实际可用空间并未占满，所以这种现象称为“假溢出”。这是由“队尾入队，队头出队”这种受限制的操作造成的。

那么，如何解决这种“假溢出”问题呢？一个较巧妙的办法是将顺序队列变为一个环状的空间，使之成为一个循环队列。

img

和顺序队列一样，在循环队列中，头、尾指针以及队列元素之间的关系不变。只是，头、尾指针增1的操作用“模”运算来实现。通过取模，头指针和尾指针就可以在顺序表空间内以头尾衔接的方式“循环”移动。

例如，在下图（a）中，队头元素是J5，在元素J6入队之前，Q.rear的值为5，而当元素J6入队之后，通过“模”运算Q.rear=(Q.rear+1)%6，得到Q.rear的值为0。这样就不会出现“假溢出”现象。

image-20231223180634481

上图（b）是J1、J2、J3、J4相继进入图（a）所示队列后的状态：队列空间被占满，此时头、尾指针相同。上图（c）则是J5、J6相继从图（a）所示的队列中出队后的状态：队列为空，头、尾指针的值也是相同的。

由此可见，对于循环队列不能以头、尾指针的值是否相同来判别队列空间是“满”还是“空”。在这种情况下，如何区别队满还是队空呢？通常有以下两种处理方法：

  • 少用一个元素空间。当队列空间大小为m时，有m-1个元素就认为是队满。这样判断队空的条件不变，即当头、尾指针的值相同时，则认为队空；而当尾指针在循环意义上加1后是等于头指针，则认为队满。因此，在循环队列中队空和队满的条件是：
    • 队空的条件：Q.rear==Q.front
    • 队满的条件：(Q.rear+1)%MAXQSIZE==Q.front。如上图（d）是J7、J8、J9进入图（a）所示的队列后d的状态，(Q.rear+1)%MAXQSIZE的值等于Q.front，此时认为队满。
  • 另设一个标志位。就是单独设置一个区别队列是“空”还是“满”的标志位。

一般情况下，实际使用的顺序队列是循环队列。循环队列的类型定义和顺序队列的类型定义是相同的。下面，以“少用一个元素空间”的方法为例，实现循环队列的一些操作。

2.1、初始化

循环队列的初始化操作就是动态分配一个预定义大小为MAXQSIZE的数组空间。该算法步骤为：

  • 为队列分配一个最大容量为MAXQSIZE的数组空间，base指向数组空间的首地址。
  • 头指针和尾指针置为零，表示队列为空。

相应的算法描述为：

1
2
3
4
5
6
Status InitQueue(SqQueue &Q) {
    Q.base=new QElemType[MAXQSIZE];
    if(!Q.base) exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}

2.2、求队列长度

对于非循环队列，尾指针和头指针的差值便是队列长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXQSIZE，然后与MAXQSIZE求余。相应的算法描述为：

1
2
3
int QueueLength(SqQueue Q) {
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

2.3、入队

入队操作是指在队尾插入一个新的元素。该算法步骤为：

  • 判断队列是否满，若满则返回ERROR。
  • 将新元素插入队尾。
  • 队尾指针加1。

相应的算法描述为：

1
2
3
4
5
6
7
8
9
10
11
// 插入元素e为Q的新的队尾元素
Status EnQueue(SqQueue &Q, QElemType e) {
    // 尾指针在循环意义上加1后等于头指针，表明队满
    if((Q.rear+1)%MAXQSIZE==Q.front)
        return ERROR;
    // 新元素插入队尾
    Q.base[Q.rear]=e;
    // 队尾指针加1
    Q.rear=(Q.rear+1)%MAXQSIZE;
    return OK;
}

2.4、出队

出队操作是将队头元素删除。该算法步骤为：

  • 判断队列是否为空，若空则返回ERROR。
  • 保存队头元素。
  • 队头指针加1。

相应的算法描述为：

1
2
3
4
5
6
7
8
9
10
11
Status DeQueue(SqQueue &Q, QElemType &e) {
    // 队空
    if(Q.front==Q.rear) return ERROR;
    
    // 保存队头元素
    e=Q.base[Q.front];
    // 队头指针加1
    Q.front=(Q.front+1)%MAXQSIZE;
    
    return OK;
}

2.5、取队头元素

当队列非空时，返回当前队头元素的值，队头指针保持不变。相应的算法描述为：

1
2
3
4
SElemType GetHead(SqQueue Q) {
    if(Q.front!=Q.rear)
        return Q.base[Q.front]
}

三、链式队列

链式队列，是指采用链式存储结构实现的队列。

链式队列通常用单链表来表示。一个链式队列需要两个指针，分别指示队头和队尾才能唯一确定。其中，指向队头的指针称为头指针，指向队尾的指针称为尾指针。

和单链表类似，为了简化边界条件的处理，会给链式队列添加一个头结点，并使头指针指向该结点。

image-20231223171616439

在C语言中，链式队列的类型描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 链式队列的结点
typedef struct Qnode {
    QElemType data;
    struct Qnode *next;
}QNode, *QueuePtr;

// 链式队列
typdef struct {
    // 队头指针
    QueuePtr front;
    // 队尾指针
    QueuePtr rear;
}LinkQueue;

链式队列的操作是单链表插入和删除操作的特殊情况。下面给出链队初始化、入队、出队操作的实现。

3.1、初始化

链队的初始化操作就是构造一个只有头结点的空队列。

image-20231230153915116

该算法步骤为：

  • 生成新结点作为头结点，队头和队尾指针指向此结点。
  • 头结点的指针域置空。

相应的算法描述为：

1
2
3
4
5
Status InitQueue(LinkQueue &Q) {
    Q.front=Q.rear=new QNode;
    Q.front->next=NULL;
    return OK;
}

3.2、入队

和循环队列的入队操作不同，链队在入队前不需要判断队是否满，仅需为入队元素动态分配一个结点空间。

image-20231230160822345

该算法步骤为：

  • 为入队元素分配结点空间，用指针p指向。
  • 将新结点数据域置为e。
  • 将新结点插入到队尾。
  • 修改队尾指针为p。

相应的算法描述为：

1
2
3
4
5
6
7
8
Status EnQueue(LinkQueue &Q, QElemType e) {
    p=new QNode;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

3.3、出队

和循环队列一样，链队在出队前也需要判断队列是否为空，不同的是，链队在出队后需要释放队头元素的所占空间。

image-20231230162124519

该算法步骤为：

  • 判断队列是否为空，若空则返回ERROR。
  • 临时保存队头元素的空间，以备释放。
  • 修改头结点的指针域，使其指向下一个结点。
  • 判断出队元素是否为最后一个元素，若是，则将队尾指针指向头结点。
  • 释放原队头元素的空间。

相应的算法描述为：

1
2
3
4
5
6
7
8
9
10
11
12
13
Status DeQueue(LinkQueue &Q, QElemType &e) {
    if(Q.front==Q.rear) return ERROR;
    
    p=Q.front->next;
    e=p->data;
    
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
    
    free(p);
    
    return OK;
}

3.4、取队头元素

与循环队列一样，当队列非空时，此操作返回当前队头元素的值，队头指针保持不变。相应的算法描述为：

1
2
3
4
SElemType GetHead(LinkQueue Q) {
    if(Q.front!=Q.rear)
        return Q.front->next->data;
}

四、小结

队列也是一种操作受限的线性表，它只允许在表头进行删除操作、在表尾进行插入操作。队列最大的特点是先进先出，因此也被称为FIFO表。队列有两种存储结构，分别是顺序队列和链式队列。队列的主要操作是进队和出队，对于顺序队列（更准确地来说是循环队列）的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXQSIZE求模。

image-20231231102950568

五、参考

《数据结构（C语言版 第2版）》

《数据结构 自考02331》

《数据结构与算法之美》

数据结构
#数据结构
数据结构：队列
https://kuberxy.github.io/2023/12/17/数据结构04：队列/
作者
Mr.x
发布于
2023年12月17日
许可协议