数据结构之——队列

2024-09-29 14:17:45

一、队列概述

队列是一种操作受限的线性表，其限制条件为允许在表的一端进行插入，而在表的另一端进行删除。插入的一端叫做队尾，删除的一端叫做队头。向队列中插入新元素的行为称为进队，从队列中删除元素的行为称为出队。例如军训的时候，都排成一列，有头有尾。假设你迟到了，只能站到最后面一个，退场的时候，都是由第一个先走的。迟到相当于对垒的入队，退场相当于队列出队。

队列具有先进先出（FIFO）的特点，即先进队列的元素先出队列。这一特点使得队列在很多场景中都有广泛的应用。比如在计算机系统中，任务调度可以使用队列来管理待执行的任务，按照任务提交的先后顺序进行处理；在网络通信中，数据包的传输也可以使用队列来缓存待发送的数据，保证数据的有序传输。

队列的头和尾相等表示队列为空，队列的头和尾相差 N - 1 表示队列为满。其中 N 通常是队列的容量大小。在实际应用中，需要根据具体情况合理设置队列的容量，以避免队列溢出或浪费空间。

队列的存储结构可以是数组或者链表。数组实现的队列通常称为顺序队列，链表实现的队列通常称为链队列。顺序队列的优点是随机访问速度快，但是在队列满或者队列为空的判断上需要特殊处理，以避免出现错误。链队列的优点是动态分配内存，不会出现队列满的情况，但是在插入和删除操作时需要进行指针的调整，相对比较复杂。

二、队列的特点

（一）先进先出特性

队列的先进先出特性是其最为显著的特点之一。当数据依次进入队列时，就如同人们排队等待服务一样，先进入队列的元素会先被处理。例如，假设有一个任务队列，任务按照提交的时间顺序依次进入队列。当系统开始处理任务时，最先提交的任务会首先被执行，然后是第二个提交的任务，以此类推。这种特性在很多场景中都非常有用。比如在操作系统中，多个进程请求资源时，可以将这些请求放入队列中，按照请求的先后顺序进行分配。在网络通信中，数据包的传输也遵循先进先出的原则，保证数据的有序到达。

入队操作是将新元素添加到队尾。例如在一个顺序队列中，当有新元素要入队时，首先判断队列是否已满。如果未满，则将新元素放置在队尾的位置，并更新队尾指针。在链队列中，入队操作则是创建一个新的节点，将新元素存入该节点的数据域，然后将该节点插入到队尾，并更新队尾指针。

出队操作是从队头删除元素。在顺序队列中，当进行出队操作时，将队头元素取出，并将队头指针向后移动一位。在链队列中，出队操作是将队头节点删除，并更新队头指针。

（二）队头和队尾的特殊性质

队头在队列中主要用于删除元素。当需要从队列中取出一个元素时，总是从队头开始操作。这是因为队列遵循先进先出的原则，最先进入队列的元素应该最先被处理。例如在一个银行排队系统中，客户按照到达的先后顺序排队，当柜台有空位时，排在队头的客户首先得到服务，即从队头删除该客户。

队尾则用于插入元素。当有新的元素要加入队列时，将其放置在队尾的位置。这样可以保证新加入的元素在队列中的位置符合先进先出的原则。例如在一个生产线上，产品按照生产的顺序进入队列，新生产出来的产品总是添加到队尾，等待后续的加工或处理。

当队头和队尾相等时，表示队列为空。这是因为在初始状态下，队列中没有任何元素，队头和队尾指针都指向同一个位置。当进行入队操作时，队尾指针会向后移动；进行出队操作时，队头指针会向后移动。只有当队列中没有任何元素时，队头和队尾指针才会再次相等。例如在一个用数组实现的顺序队列中，如果队头指针和队尾指针的值相同，且都为 0，表示队列中没有元素。在链队列中，如果队头指针和队尾指针都指向同一个空节点，表示队列为空。

三、队列的实现方式

（一）顺序存储

1.循环队列的概念和优势，包括节省空间、高效利用存储单元等。

循环队列是将顺序队列变成环状空间，充分利用数组的存储空间，避免了传统顺序队列在入队和出队操作中可能出现的空间浪费问题。例如，在一个容量为MAXSIZE的循环队列中，当队尾指针指向数组的最后一个位置时，如果再进行入队操作，队尾指针会重新指向数组的第一个位置，继续利用未被占用的空间。这样可以大大提高空间利用率，避免出现队列溢出的情况，同时也减少了内存的浪费。
循环队列的入队和出队操作速度快。在循环队列中，入队时只需要在队尾追加元素，出队时只需要删除队头元素，不需要移动大量元素，因此速度快。例如，在一个有1000个元素的循环队列中，进行入队和出队操作的时间复杂度为，相比传统顺序队列，在处理大量数据时具有明显的优势。

2.判别队列空间 “空” 与 “满” 的方法，如设置标志位、少用一个元素空间、设置计数器等。

设置标志位的方法是预设一个标志tag，初值为0，每当入队成功，tag设为1；每当出队成功，tag设为0。队空时为front==rear &&!tag，表示因删除元素导致队头和队尾指针相等且标志位为0；队满时为front==rear && tag，表示因插入元素导致队头和队尾指针相等且标志位为1。
少用一个元素空间的方法是约定以 “队列头指针在队列尾指针的下一个位置上” 作为队列 “满” 的标志。即队空时：rear==front；队满时：(rear + 1) % maxsize == front。这样可以通过判断队头和队尾指针的相对位置来确定队列的状态。
设置计数器的方法是设置一个计数器count，初始值为0，入队成功时count加1，出队成功时count减1。队空时count == 0；队满时count > 0 && rear == front。通过计数器可以准确地记录队列中元素的个数，从而判断队列是否已满。

3.队列的顺序存储类型描述，包括结构体定义和基本操作的实现。

结构体定义通常如下：

    #define Maxsize 50
    typedef struct 
    {
        int data[Maxsize];
        int front, rear;
        int tag = 0;
    }SqQueue;

其中data数组用于存储队列元素，front和rear分别表示队头和队尾指针，tag可以用于设置标志位。

基本操作的实现包括初始化、入队、出队等。初始化操作将队头和队尾指针置为0：

    void initqueue(SqQueue &Q)
    {
        Q.rear = Q.front = 0;
    }

入队操作在队不满时，将元素插入队尾，队尾指针加1：

// 入队操作函数
bool enqueue(SqQueue &Q, int e) 
{
    // 判断队列是否已满，如果 rear 指针的下一个位置（循环队列）等于 front 指针，则队满
    if ((Q.rear + 1) % Maxsize == Q.front) 
    {
        return false;
    }
    // 将元素 e 放入 rear 指针所指位置
    Q.data[Q.rear] = e;
    // 更新 rear 指针，指向下一个位置（循环队列方式更新）
    Q.rear = (Q.rear + 1) % Maxsize;
    return true;
}

出队操作在队不空时，取出队头元素，队头指针加1：

// 出队操作函数
bool dequeue(SqQueue &Q, int &e) 
{
    // 判断队列是否为空，如果队尾指针等于队头指针，则队空
    if (Q.rear == Q.front) 
    {
        return false;
    }
    // 将队头元素赋值给变量 e
    e = Q.data[Q.front];
    // 更新队头指针，指向下一个位置（循环队列方式更新）
    Q.front = (Q.front + 1) % Maxsize;
    return true;
}

（二）链式存储

1.链队列的结构和特点，用链表表示队列，有头指针和尾指针。

链队列是用链表表示的队列，一个含有头指针（指向队头结点）和尾指针（指向队尾结点）的单链表。当链队列有头结点时，当尾指针和头指针均指向头结点，则链队列尾空。
链队列的特点是动态扩容，不会出现溢出问题。可以根据实际需求动态分配内存，不需要预先确定队列的最大长度，能够更灵活地处理不确定长度的队列。但是，链队列需要额外的指针空间来存储节点之间的关系，占用了额外的存储空间，并且在插入和删除操作时需要涉及指针的操作，相对比较复杂。

2.链队列的基本操作，如初始化、入队、出队、判断空等操作的实现。

初始化操作创建一个头结点，并将头指针和尾指针都指向头结点：

    void initqueue(Linkqueue &Q)
    {
        Q.front = Q.rear = (Linkqueuenode *)malloc(sizeof(Linkqueuenode));
        Q.front->next = NULL;
    }

入队操作申请一个新结点，将新结点的数据域赋值，插入到队尾，并更新队尾指针：

   // 入队操作函数
    int EnQueue(LinkQueue *Q, DataType x) 
    {
    // 创建新节点
    QNode *p = (QNode *)malloc(sizeof(QNode));
    // 如果内存分配失败，退出程序
    if (!p) exit(-1); 
    // 初始化新节点的数据和指针
    p->data = x;
    p->next = NULL;
    // 将新节点加入队列尾部
    Q->rear->next = p;
    Q->rear = p;
    return 0;
    }

出队操作判断队列是否为空，若为空则不能出队。否则，取出队头元素，修改队头指针指向新元素，如果队中只有一个元素，还需要修改队尾指针指向队头：

// 出队操作函数
int DeQueue(LinkQueue *Q, DataType *x) {
    QNode *p;
    // 如果队列为空
    if (IsEmpty(Q)) {
        printf("队空，不能出队！");
        return -1; // 可根据实际情况定义错误码
    }
    // 获取队头节点的下一个节点，即要出队的节点
    p = Q->front->next;
    // 将出队节点的数据赋值给 x
    *x = p->data;
    // 更新队头节点的 next 指针，指向下一个节点
    Q->front->next = p->next;
    // 如果出队节点是队尾节点，更新队尾指针为队头指针
    if (Q->rear == p)
        Q->rear = Q->front;
    // 释放出队节点的内存
    free(p);
    return 0;
}

判断空操作判断头指针和尾指针是否相等，若相等则队列为空：

    Status IsEmpty(LinkQueue *Q)
    {
        return Q->front == Q->rear;
    }

四、队列的应用场景

队列在现实生活中有广泛的应用场景。例如在医院排号系统中，患者按照到达的先后顺序进行挂号，进入排队队列。医生按照队列的顺序依次为患者看病，先进入队列的患者先得到诊治，体现了队列的先进先出特性。在手机营业厅排号也是类似的原理，顾客到达后领取号码，进入排队队列，等待工作人员按照号码顺序为其提供服务。

在数据结构中，队列也有重要的应用。其中，广度优先遍历就是一个典型的例子。在图的广度优先遍历中，从起始节点开始，将其加入队列，然后依次取出队列中的节点，将其未被访问过的相邻节点加入队列。这样，就可以按照距离起始节点的远近，一层一层地遍历图中的所有节点。这种遍历方式保证了先访问距离起始节点近的节点，后访问距离远的节点，符合队列的先进先出原则。

此外，在操作系统中，任务调度也可以使用队列来管理待执行的任务。新的任务按照提交的时间顺序进入任务队列，操作系统按照队列的顺序依次执行任务，确保任务的执行顺序与提交顺序一致。在网络通信中，数据包的传输也可以使用队列来缓存待发送的数据，保证数据的有序传输。

在文件系统中，队列可以用于按照层级结构遍历文件和目录。从根目录开始，将其下的子目录和文件加入队列，然后依次处理队列中的元素，直到队列为空。这样可以确保按照文件和目录的层级关系进行遍历。

在人工智能领域，搜索算法中也常常使用队列。例如在状态空间的搜索中，队列可以用于存储待搜索的状态，按照搜索的先后顺序进行处理，寻找解决问题的最短路径。

总之，队列的应用场景非常广泛，无论是在现实生活中的排队系统，还是在计算机科学的数据结构和算法中，队列都发挥着重要的作用。

码农公寓