数据结构第5问：什么是队列？

队列

是一种先进先出（FIFO，First In First Out） 的数据结构。意思是：最先进入队列的元素，会最先被取出。队列其实就是一种操作收到限制的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

队列的基本特点

• 插入操作（入队 enqueue） 发生在队列的一端，称为“队尾”。
• 删除操作（出队 dequeue） 发生在另一端，称为“队头”。
• 元素入队按顺序排在队尾，出队则从队头按先后顺序依次取出。
• 队列结构适合排队、缓冲区等场景。

队列的典型操作

队列的顺序存储结构

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并设置2个指针：队首指针和队尾指针。

1. 队首指针（front） ：指向队列中第一个有效元素在数组中的位置，也就是当前队头元素的位置。
2. 队尾指针（rear） ：指向队列中最后一个有效元素后面的位置（即下一个可以插入元素的位置）。

• 如果队列为空，通常定义 front == rear。
• 当插入（入队）元素时，把元素放在 rear 指向的位置，然后 rear 向后移动。
• 当删除（出队）元素时，从 front 指向的位置取元素，然后 front 向后移动。
• 即出队从队首出，入队从队尾入。

静态分配内存空间的队列实例

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

#define MaxSize 100

typedef struct
{
    int data[MaxSize]; // 数据存放空间
    int front;         // 队首指针
    int rear;          // 队尾指针
} Queue;

// 初始化队列
bool init_queue(Queue *Q)
{
    Q->front = -1;
    Q->rear = -1;
    return true;
}

// 入队
bool enqueue(Queue *Q, int data)
{
    // 判断队列是否已满，满了就直接退出来
    if (Q->rear + 1 == MaxSize)
        return false;
    // 如果是第一次入队，front和rear都为-1，需要初始化front为0
    if (Q->front == -1)
        Q->front = 0;
    Q->rear++;
    Q->data[Q->rear] = data;
    return true;
}

// 出队
bool dequeue(Queue *Q, int *data)
{
    if (Q->front == -1)
        return false;
    *data = Q->data[Q->front];
    if (Q->front == Q->rear)
    {
        Q->front = -1;
        Q->rear = -1;
    }
    else
        Q->front++;
    return true;
}

// 查看队首元素
bool peek(Queue Q, int *data)
{
    if (Q.front == -1)
        return false;
    *data = Q.data[Q.front];
    return true;
}

// 判断队列是否为空
bool isEmpty(Queue Q)
{
    return (Q.front == -1 || Q.front > Q.rear);
}

// 判断队列是否已满
bool isFull(Queue Q)
{
    if (Q.rear == MaxSize - 1)
        return true;
    else
        return false;
}

注意：队列的顺序实现会造成假溢出。即顺序队列中因队头指针向后移动导致数组尾部空间被占满，虽然数组前部还有空闲空间，但是无法利用，从而认为队列已满，不能再入队的情况。

顺序队列假溢出的典型场景

假设队列容量是 MaxSize，入队和出队序列如下：

1. 初始化：front = -1, rear = -1，队空。
2. 依次入队一批元素，rear 指针从 -1 逐渐增加到 MaxSize - 1。此时，数组被填满，队列满。
3. 依次出队一部分元素，front 指针从 0 向后移动，出队后 front > 0，前面的空间空出来了。
4. 此时如果尝试继续入队：
   • 因为 rear == MaxSize -1（数组尾部），虽然数组前面（0 到 front -1）空间空闲，
   • 但你的入队函数只能在 rear + 1 的位置插入，越界，不能插入元素，
   • 队列“假满”了，实际还有空余空间无法利用。

举例说明

假设 MaxSize = 5：

• 一开始 front = -1, rear = -1
• 入队 5 个元素后：front = 0, rear = 4, 队列满
• 出队 3 个元素后：front = 3, rear = 4，现在数组下标0、1、2已空
• 再入队时，rear + 1 == 5 == MaxSize，判定队满，拒绝入队
• 实际底层数组0、1、2的空间空闲，但没有被利用，导致“假溢出”。

为了避免顺序队列中出现“假溢出”的情况，提高队列空间的利用率，我们可以采用循环队列结构。循环队列把顺序队列结构逻辑上看作一个环形缓冲区，实现指针在数组尾部达到最大索引时自动回绕到数组头部，从而复用空闲空间。

循环队列关键实现手段是：

• 利用模运算(% MaxSize)实现指针环绕。
• 当入队时，队尾指针 rear 达到数组尾部（MaxSize - 1）时，执行 rear = (rear + 1) % MaxSize 使其回到数组头位置0，继续插入。
• 同理，出队时队首指针 front 也执行类似的模运算操作。

这样，实现了指针的循环移动，数组空间就像是首尾相接的环状空间。

循环队列（顺序存储结构）

特点

循环队列的优势

• 高效利用数组空间：避免了顺序队列因前端出队导致空间浪费的问题。
• 简单灵活：通过模运算实现指针环绕，逻辑清晰。
• 常用数据结构：广泛用于系统缓冲区、消息队列等场景。

动态分配内存空间的循环队列实例1

front 和 rear 从 0 开始

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#define MaxSize 100
typedef struct
{
    int data[MaxSize]; // 数据存放空间
    int front;         // 队首指针
    int rear;          // 队尾指针
} LoopQueue;

// 初始化循环队列
bool init_Loop_queue(LoopQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return true;
}

// 入队
bool enloopQueue(LoopQueue *Q, int data)
{
    // 如果队列为满
    if ((Q->rear + 1) % MaxSize == Q->front)
        return false;

    // 队列有位置
    Q->data[Q->rear] = data;
    // 循环递增rear指针，rear指向下一个空位置
    Q->rear = (Q->rear + 1) % MaxSize;  
    return true;
}

// 出队
bool deloopQueue(LoopQueue *Q, int *data)
{
    // 如果队列为空
    if (Q->front == Q->rear)
        return false;
    
    *data = Q->data[Q->front];

    // 只有一个元素，出队后置空
    if (Q->front == Q->rear)
    {
        Q->front = 0;
        Q->rear = 0;
    }
    // 还有很多元素
    else
        Q->front = (Q->front + 1) % MaxSize;

    return true;
}

// 查看队首元素
bool peek(LoopQueue *Q, int *data)
{
    if (Q->front == Q->rear)
        return false;
    *data = Q->data[Q->front];
    return true;
}

// 判断队列是否为空
bool isEmpty(LoopQueue Q)
{
    return Q.front == Q.rear;
}

// 判断队列是否已满
bool isFull(LoopQueue Q)
{
    if ((Q.rear + 1) % MaxSize == Q.front)
        return true;
    else
        return false;
}

动态分配内存空间的循环队列实例2

front 和 rear 从 -1 开始

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#define MaxSize 100
typedef struct
{
    int data[MaxSize]; // 数据存放空间
    int front;         // 队首指针
    int rear;          // 队尾指针
} LoopQueue;

// 初始化循环队列
bool init_Loop_queue(LoopQueue *Q)
{
    Q->front = -1;
    Q->rear = -1;
    return true;
}

// 入队
bool enloopQueue(LoopQueue *Q, int data)
{
    // 如果队列为满
    if ((Q->rear + 1) % MaxSize == Q->front)
        return false;

    // 如果队列为空
    if (Q->front == -1)
    {
        Q->front = 0;
        Q->rear = 0;
        Q->data[Q->rear] = data;
        return true;
    }
    
    // 队列有位置
    // 循环递增rear指针，指向队列中最后一个有效元素所在的位置
    Q->rear = (Q->rear + 1) % MaxSize;  
    Q->data[Q->rear] = data;

    return true;
}

// 出队
bool deloopQueue(LoopQueue *Q, int *data)
{
    // 如果队列为空
    if (Q->front == -1)
        return false;
    
    *data = Q->data[Q->front];

    // 只有一个元素，出队后置空
    if (Q->front == Q->rear)
    {
        Q->front = -1;
        Q->rear = -1;
    }
    // 还有很多元素
    else
        Q->front = (Q->front + 1) % MaxSize;

    return true;
}

// 查看队首元素
bool peek(LoopQueue *Q, int *data)
{
    if (Q->front == -1)
        return false;
    *data = Q->data[Q->front];
    return true;
}

// 判断队列是否为空
bool isEmpty(LoopQueue Q)
{
    return Q.front == -1;
}

// 判断队列是否已满
bool isFull(LoopQueue Q)
{
    if ((Q.rear + 1) % MaxSize == Q.front)
        return true;
    else
        return false;
}

队列的链式存储结构

链式存储结构的队列是用链表来实现的队列数据结构，利用链表节点的动态分配，能够解决顺序队列容量固定和假溢出的问题。

链式队列的基本结构

链式队列通过一组结点动态连接起来，通常包含以下两个指针：

• front（头指针）：指向队首结点（第一个元素）
• rear（尾指针）：指向队尾结点（最后一个元素）

每个结点包含：数据部分和指向下一个结点的指针（next）

链队列的优点

1. 动态内存分配，容量灵活
   链队列不需要预先分配固定大小的数组空间，结点是根据需要动态申请的，因此可以支持任意长度的队列，避免了顺序队列容量固定或假溢出的问题。
2. 无假溢出问题
   由于空间动态分配，没有固定上限，队列入队只要内存允许就能继续，不会像顺序队列那样出现“假溢出”（即数组前部有空闲空间但队尾指针无法继续入队）。
3. 入队和出队操作均为 O(1) 时间复杂度
   通过维护指向队首和队尾的指针，入队时直接在尾部插入结点，出队时从头部删除结点，无需移动数据，效率高。
4. 内存利用效率高，不会浪费固定数组空间
   没有预分配大块数组，内存按需分配，减少了空间浪费。

链队列整体描述

链队列由节点结构体组成的链表和两个节点指针组成，数据元素存放在由节点组成的链表中，节点指针分别为队头指针和队尾指针。两个节点指针都是指向链表的某个节点。初始化的时候，队头指针和队尾指针均指向头节点。入队的时候队尾指针产生偏移，出队的时候队头指针产生偏移。当队头指针便宜到队尾指针时，说明队列内元素全部出队，队列成空队列了。由于使用的是链表，所以链队列不会发生上溢出。

1. 链队列结构
   • 由节点结构体组成的单链表存储数据元素。
   • 有两个指针，分别是队头指针（front）和队尾指针（rear）。
   • 这两个指针都指向链表中的节点，初始化时通常都指向带头节点的头节点（该头节点不存储有效数据）。
2. 入队操作
   • 新节点加入到队尾。
   • 队尾指针（rear）指向新加入的节点，指针发生偏移。
3. 出队操作
   • 删除队头元素，即头节点后面的第一个有效节点。
   • 队头指针（front）向后移一位（实际是其 next 指针的变化），即指向新的头节点后面的第一个元素。
4. 队空判断
   • 当队头指针和队尾指针指向同一个节点时，说明队列为空（所有有效元素均已出队）。
   • 此时链表中只有头节点，且 front->next == NULL。
5. 不存在上溢出
   • 因为链队列是动态链表结构，根据需要动态分配节点内存，可灵活扩展长度，理论上不会发生“满”的情况（除非系统内存耗尽）。

动态分配内存空间的链队列实例

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

typedef struct LinkNode // 链式队列节点
{
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct  // 链式队列
{
    LinkNode *front, *rear; // 队列的队头和队尾指针
}LinkQueue;

// 初始化链队列
void init_link_queue(LinkQueue *Q)
{
    Q->front = Q->rear = malloc(sizeof(LinkNode));
    Q->front->next = NULL;
    Q->rear->next = NULL;   // 可写可不写
}

// 入队
void enqueue(LinkQueue *Q, int data)
{
    LinkNode *new_node = malloc(sizeof(LinkNode));

    new_node->data = data;
    new_node->next = NULL;

    Q->rear->next = new_node;
    Q->rear = new_node;
}

// 出队
bool dequeue(LinkQueue *Q, int* data)
{
    // 如果队列为空，则无法出队，直接返回false
    if(Q->front == Q->rear)
        return false;

    // 用temp暂存头结点之后的第一个有效节点（出队节点）
    LinkNode *temp = Q->front->next;
    *data = temp->data;
    // 将头结点的next指针跳过temp节点，指向temp的下一个节点
    Q->front->next = temp->next;
    
    // 如果出队节点是尾节点，则更新尾指针指向头结点，表示队列为空
    
    // 因为在链式队列中，空队列的定义是 front == rear，且头结点的 next == NULL。
    // 当出队的节点正是尾节点（最后一个有效数据），出队后链表中没有有效节点了，
    // 这时必须更新尾指针指向头结点，否则 rear 会指向刚刚被释放的无效内存，出现悬空指针(指向一个被释放过的内存地址)。
    if (Q->rear == temp)
        Q->rear = Q->front;

    free(temp);
    return true;
}

// 查看队首元素
bool peek(LinkQueue *Q, int *data)
{
    // 如果队列为空，则无法出队，直接返回false
    if(Q->front == Q->rear)
        return false;
    *data = Q->front->next->data;
    return true;
}

// 判断队列是否为空
bool isEmpty(LinkQueue Q)
{
    if(Q.rear == Q.front)
        return true;
    else
        return false;
}

双端队列

双端队列（Deque）：是一种线性数据结构，它允许在队列的两端进行插入和删除操作。也就是说，双端队列既可以像普通队列一样从队尾入队、从队头出队，也可以实现从队头入队或从队尾出队。

双端队列的特点

• 两端插入：可以在队头或队尾插入元素。
• 两端删除：可以从队头或队尾删除元素。
• 结合了栈（LIFO）和队列（FIFO）的特点，既能做先进先出操作，也能做先进后出操作。
• 应用灵活，适合需要双向访问元素的场景。

双端队列的操作

实现方式

• 双端队列可以用数组或链表实现。
• 用链表实现时，常用双向链表，更容易从两端访问和修改节点。
• 用数组实现时，通常使用循环数组来节约空间。

简单例子

假设双端队列初始为空：

• 从队头插入元素 1 后，队列为：[1]
• 从队尾插入元素 2 后，队列为：[1, 2]
• 删除队头元素，队列变为：[2]
• 从队尾插入元素 3，队列为：[2, 3]
• 删除队尾元素，队列为：[2]