C++
数据结构——队列(Queue)
admin SU @ 2025-8-16 11:28:51

数据结构——队列(Queue)详解

https://blog.csdn.net/Yuan_o_/article/details/139681449

admin SU @ 2025-8-16 11:37:42

下面为你介绍 C++ STL 中队列（queue）的使用方法，包括基本概念、常用操作以及实际示例。

队列（queue）基本概念

队列是一种先进先出（FIFO，First In First Out）的数据结构，元素从队尾入队，从队头出队，就像日常生活中排队一样。

C++ STL 中的 queue 容器适配器提供了队列的功能，它默认基于 deque 容器实现，也可以指定其他底层容器（如 list）。

使用前的准备

使用 queue 需要包含头文件：

#include <queue>

队列的基本操作

创建队列

// 创建一个存储int类型的队列
std::queue<int> q;

// 创建一个基于list的队列
std::queue<int, std::list<int>> q_list;

入队操作（push） 向队尾添加元素：
```
q.push(10);
q.push(20);
q.push(30);
```
出队操作（pop） 移除队头元素（注意：pop() 没有返回值）：
```
q.pop(); // 移除队头元素10
```

访问队头元素（front） 获取队头元素的值：

int front_val = q.front(); // 获取当前队头元素20

访问队尾元素（back） 获取队尾元素的值：

int back_val = q.back(); // 获取当前队尾元素30

判断队列是否为空（empty） 若队列为空返回 true，否则返回 false：

if (q.empty()) {
    std::cout << "队列为空" << std::endl;
} else {
    std::cout << "队列不为空" << std::endl;
}

获取队列大小（size） 返回队列中元素的个数：
```
int size = q.size(); // 获取队列元素个数
```

完整示例

下面是一个展示队列各种操作的完整程序：

#include <iostream>
#include <queue>

int main() {
    // 创建一个int类型的队列
    std::queue<int> q;

    // 入队操作
    q.push(10);
    q.push(20);
    q.push(30);
    std::cout << "入队3个元素：10, 20, 30" << std::endl;

    // 查看队列大小
    std::cout << "当前队列大小：" << q.size() << std::endl;

    // 访问队头和队尾元素
    std::cout << "队头元素：" << q.front() << std::endl;
    std::cout << "队尾元素：" << q.back() << std::endl;

    // 出队操作
    q.pop();
    std::cout << "出队一个元素后，队头元素：" << q.front() << std::endl;

    // 循环出队所有元素
    std::cout << "依次出队剩余元素：";
    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;

    // 检查队列是否为空
    if (q.empty()) {
        std::cout << "所有元素已出队，队列现在为空" << std::endl;
    }

    return 0;
}

示例输出

上述程序的运行结果如下：

入队3个元素：10, 20, 30
当前队列大小：3
队头元素：10
队尾元素：30
出队一个元素后，队头元素：20
依次出队剩余元素：20 30 
所有元素已出队，队列现在为空

队列的应用场景

队列在很多场景中都有应用，例如：

广度优先搜索（BFS）算法
任务调度系统
打印队列
缓存机制

通过上述内容，你可以掌握 C++ STL 队列的基本使用方法。在实际编程中，根据具体需求选择合适的操作即可。

admin SU @ 2025-8-16 11:30:35

数据结构——队列（Queue）理论教程

一、队列的基本概念

队列是一种先进先出（First In First Out, FIFO） 的线性数据结构，它只允许在一端进行插入操作，在另一端进行删除操作。

队尾（Rear）：允许插入元素的一端。
队头（Front）：允许删除元素的一端。
例如：日常生活中的排队现象就是典型的队列应用，先到的人先接受服务。

二、队列的基本操作

队列的核心操作围绕元素的插入和删除展开，常见操作如下：

入队（Enqueue）：在队尾插入一个新元素。
- 若队列已满，会出现“上溢”（Overflow）现象。
出队（Dequeue）：从队头删除并返回一个元素。
- 若队列为空，会出现“下溢”（Underflow）现象。
查看队头元素（Front/Peek）：返回队头元素，但不删除它。
判断队列是否为空（IsEmpty）：检查队列中是否没有元素。
判断队列是否已满（IsFull）：在有固定容量的队列中，检查是否无法再插入元素。
获取队列长度（Size）：返回队列中元素的个数。

三、队列的存储结构

1. 顺序队列（基于数组）

使用一维数组存储队列元素，同时设置两个指针：front（指向队头元素）和rear（指向队尾元素的下一个位置）。
初始状态：front = rear = 0（队列为空）。
入队操作：rear指针后移，rear = (rear + 1) % maxSize（循环队列的处理方式）。
出队操作：front指针后移，front = (front + 1) % maxSize。

问题与解决：

普通顺序队列存在“假溢出”问题：即队列实际未满，但rear已达到数组末尾。
解决方法：采用循环队列（将数组视为环形），通过取模运算实现指针的循环移动。

2. 链式队列（基于链表）

用链表存储队列元素，队头指针指向链表的头节点，队尾指针指向链表的尾节点。
入队：在链表尾部插入新节点，更新队尾指针。
出队：删除链表头节点，更新队头指针。
优势：无需预先确定容量，避免了溢出问题，内存利用率更高。

四、循环队列详解

循环队列是顺序队列的优化形式，通过以下方式判断状态：

队空：front == rear。
队满：(rear + 1) % maxSize == front（牺牲一个位置来区分队空和队满）。
队列长度计算公式：(rear - front + maxSize) % maxSize。

示例：假设队列最大容量maxSize = 5，初始front = rear = 0。

入队元素A、B、C：rear = 3，front = 0。
出队元素A：front = 1。
入队元素D、E：rear = (3 + 2) % 5 = 0，此时(rear + 1) % 5 = 1 == front，队列已满。

五、队列的应用场景

队列在计算机科学和日常生活中应用广泛，典型场景包括：

操作系统中的进程调度：多个进程按顺序等待CPU处理，遵循FIFO原则。
缓冲处理：如打印机的打印队列、网络数据的接收缓冲区，先到达的数据先处理。
广度优先搜索（BFS）：在图和树的遍历中，队列用于存储待访问的节点。
消息队列：在分布式系统中，用于不同组件间的异步通信，如消息中间件（RabbitMQ、Kafka）。

六、队列与栈的对比

特性	队列（Queue）	栈（Stack）
操作原则	先进先出（FIFO）	后进先出（LIFO）
插入删除端	队尾插入，队头删除	栈顶插入和删除
典型应用	进程调度、BFS、缓冲	表达式求值、DFS、递归

通过以上内容，我们对队列的理论知识有了全面的了解，包括概念、操作、存储结构、应用等方面。在实际编程中，可根据具体需求选择合适的队列实现方式（顺序队列或链式队列）。