#创作计划# 栈和队列精讲
2025-08-27 22:23:05
发布于：北京
在 C++ 中，栈（Stack） 和 队列（Queue） 是两种重要的线性数据结构，它们遵循特定的元素访问规则，广泛应用于算法设计和问题求解中。下面详细讲解这两种数据结构：
1.栈（Stack）：
栈是一种遵循后进先出原则的线性数据结构。想象成一叠盘子，最后放上去的盘子最先被取走。
1.1栈的基本操作
push()：向栈顶添加元素
pop()：移除栈顶元素（不返回值）
top()：返回栈顶元素（不移除）
empty()：判断栈是否为空
size()：返回栈中元素的个数
1.2 C++ 中的栈实现
C++ 标准库提供了std::stack容器适配器，它默认基于std::deque实现，也可以指定其他底层容器（如std::vector或std::list）。
#include <iostream>
#include <stack>
#include <vector>
int main() {
// 创建栈，默认使用deque作为底层容器
std::stack<int> s1;
// 入栈操作
s1.push(10);
s1.push(20);
s1.push(30);
std::cout << "栈的大小: " << s1.size() << std::endl; // 输出: 3
// 访问栈顶元素
std::cout << "栈顶元素: " << s1.top() << std::endl; // 输出: 30
// 出栈操作
s1.pop();
std::cout << "出栈后栈顶元素: " << s1.top() << std::endl; // 输出: 20
// 遍历栈（需要注意栈没有迭代器，必须通过出栈操作）
while (!s1.empty()) {
std::cout << s1.top() << " ";
s1.pop();
}
// 输出: 20 10
return 0;
}
1.3栈的应用场景
函数调用栈：程序执行时的函数调用和返回
表达式求值：中缀表达式转后缀表达式
括号匹配问题
深度优先搜索（DFS）
撤销操作（如文本编辑器的 Ctrl+Z）
2.队列（Queue）
队列是一种遵循先进先出原则的线性数据结构。类似于现实生活中的排队，先来的人先得到服务。
2.1队列的基本操作
push()：向队尾添加元素
pop()：移除队头元素（不返回值）
front()：返回队头元素（不移除）
back()：返回队尾元素（不移除）
empty()：判断队列是否为空
size()：返回队列中元素的个数
C++ 中的队列实现
C++ 标准库提供了std::queue容器适配器，默认同样基于std::deque实现，也可以指定其他底层容器。
#include <iostream>
#include <queue>
#include <list>
int main() {
// 创建队列，默认使用deque作为底层容器
std::queue<int> q1;
// 入队操作
q1.push(10);
q1.push(20);
q1.push(30);
std::cout << "队列的大小: " << q1.size() << std::endl; // 输出: 3
// 访问队头和队尾元素
std::cout << "队头元素: " << q1.front() << std::endl; // 输出: 10
std::cout << "队尾元素: " << q1.back() << std::endl; // 输出: 30
// 出队操作
q1.pop();
std::cout << "出队后队头元素: " << q1.front() << std::endl; // 输出: 20
// 遍历队列（需要注意队列没有迭代器，必须通过出队操作）
while (!q1.empty()) {
std::cout << q1.front() << " ";
q1.pop();
}
// 输出: 20 30
return 0;
}
2.2 队列的应用场景
广度优先搜索（BFS）
任务调度：如操作系统中的进程调度
缓冲机制：如打印机的任务队列
消息队列：处理异步通信
2.3双端队列（Deque）
C++ 还提供了std::deque（double-ended queue），它允许在两端高效地插入和删除元素，结合了栈和队列的特性。
#include <iostream>
#include <deque>
int main() {
std::deque<int> dq;
dq.push_back(10); // 从尾部添加
dq.push_front(20); // 从头部添加
std::cout << dq.front() << " " << dq.back() << std::endl; // 输出: 20 10
dq.pop_front(); // 从头部移除
dq.pop_back(); // 从尾部移除
return 0;
}
2.4 优先队列（Priority Queue）
std::priority_queue是一种特殊的队列，它总是将优先级最高的元素放在队头（默认是大跟堆，即最大的元素；而小跟堆需要自己定义）。
#include <iostream>
#include <queue>
int main() {
// 默认是最大堆，队头是最大元素
std::priority_queue<int> pq;
pq.push(30);
pq.push(10);
pq.push(50);
while (!pq.empty()) {
std::cout << pq.top() << " "; // 依次输出: 50 30 10
pq.pop();
}
// 创建最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
return 0;
}
优先队列有些时候在贪心时会被用到。
3. 栈与队列的选择
当需要后进先出的特性时，选择栈
当需要先进先出的特性时，选择队列
当需要在两端操作元素时，选择双端队列
当需要按优先级处理元素时，选择优先队列
理解这些数据结构的特性和适用场景，会有助于在解决实际问题时选择合适的工具，提高代码效率和可读性。
全部评论 1
顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶顶
21小时前 来自 北京
0
有帮助，赞一个