C++标准库中的Stack(堆栈)和Queue(队列)详解

目录

• 1. stack（栈）
• 核心概念
• 头文件
• 底层容器
• 主要成员函数
• 基本用法示例
• 2. queue（队列）
• 核心概念
• 头文件
• 底层容器
• 主要成员函数
• 基本用法示例
• 关键区别总结
• 进阶：自定义底层容器与使用场景
• 为什么 stack 可以用 vector，而 queue 不行？
• 如何选择底层容器？
• 总结

1. stack（栈）

核心概念

栈是一种 LIFO 的数据结构。

• LIFO: Last-In, First-Out，即后进先出。

• 想象一叠盘子：你总是从最上面取走盘子，新盘子也总是放在最上面。

头文件

cpp

#include <stack>

底层容器

默认情况下，stack 使用 deque 作为其底层容器。但你也可以显式指定使用 vector 或 list。

cpp

stack<int> s1; // 默认使用 deque
stack<int, vector<int>> s2; // 使用 vector 作为底层容器
stack<int, list<int>> s3; // 使用 list 作为底层容器

主要成员函数

注意：stack 没有提供 begin() 和 end() 方法，因此不能使用范围 for 循环来遍历。遍历栈的唯一方式是不断弹出其元素。

基本用法示例

cpp

#include <IOStream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    // 压入元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 查看栈顶元素
    cout << "Top element: " << s.top() << endl; // 输出 30

    // 弹出栈顶元素
    s.pop(); // 弹出 30
    cout << "Top after pop: " << s.top() << endl; // 输出 20

    // 遍历栈 (会销毁栈)
    cout << "Stack elements: ";
    while (!s.empty()php) {
        cout << s.top() << " ";
        s.pop();

    }
    // 输出：Stack elements: 20 10
    cout << endl;

    return 0;
}

2. queue（队列）

核心概念

队列是一种 FIFO 的数据结构。

• FIFO: First-In, First-Out，即先进先出。

• 想象排队买票：先来的人先买到票离开，新来的人排在队伍末尾。

头文件

cpp

#include <queue>

底层容器

默认情况下，queue 使用 deque 作为其底层容器。你也可以指定使用 list（但不能用 vector，因为 vector 没有 pop_front 方法）。

cpp

queue<int> q1; // 默认使用 deque
queue<int, list&androidlt;int>> q2; // 使用 list 作为底层容器

主要成员函数

注意：和 stack 一样，queue 也没有迭代器，不能使用范围 for 循环遍历。

基本用法示例

cpp

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    // 添加元素到队尾
    q.push(10);
    q.push(20);
    q.push(30);

    // 查看队首和队尾元素
    cout << "Front element: " << q.fandroidront() << endl; // 输出 10
    cout << "Back element: " << q.back() << endl;  // 输出 30

    // 移除队首元素
    q.pop(); // 移除 10
    cout << "Front after pop: " << q.front() << endl; // 输出 20

    // 遍历队列 (会销毁队列)
    cout << "Queue elements: ";
    while (!q.eandroidmpty()) {
        cout << q.front() << " ";
        q.pop();

    }
    // 输出：Queue elements: 20 30
    cout << endl;

    return 0;
}

关键区别总结

进阶：自定义底层容器与使用场景

为什么 stack 可以用 vector，而 queue 不行？

• stack 只需要在一端进行操作（push_back, pop_back），vector 完美支持，且效率很高。

• queue 需要在两端进行操作（push_back, pop_front）。vector 没有 pop_front() 方法，如果用它会导致效率极低的 O(n) 操作（需要移动所有元素），所以标准库禁止了这种用法。

如何选择底层容器？

• 默认 deque：在大多数情况下是最平衡的选择，两端操作效率都高。

• stack 用 vector：如果你确定你的栈操作非常密集，且内存分配性能至关重要，vector 可能稍快一些，因为它使用连续内存。

• list：如果你需要稳定的迭代器（在元素插入删除时不会失效），或者你的元素非常大，移动成本高，可以考虑 list。

cpp

// 一个使用 vector 作为底层容器的栈
stack<int, vector<int>> my_stack;

// 一个使用 list 作为底层容器的队列
queue<int, list<int>> my_queue;

总结

stack 和 queue 是 C++ 中两个简单而强大的容器适配器，它们通过限制对底层数据的访问方式，强制实现了特定的数据管理规则。理解它们的 LIFO 和 FIFO 原则是正确使用的关键。它们被广泛应用于各种算法和系统设计中。

到此这篇关于C++标准库中的Stack(堆栈)和Queue(队列)的文章就介绍到这了,更多相关C++标准库stack和queue内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文php章希望大家以后多多支持编程客栈(www.devze.com)！