当前位置：首页 > ds >正文

深入探究C++ 中的stack、queue和deque

ds 2025/7/2 6:26:28

一、stack（栈）

二、queue（队列）

三、deque（双向队列）

四、容器适配器总结

在C++ 的标准模板库（STL）中，stack、queue和priority_queue是非常实用的容器适配器，它们为我们处理数据提供了极大的便利。今天，就让我们深入了解一下它们的原理、使用方法以及相关代码实现。

一、stack（栈）

1. 原理介绍

栈是一种遵循后进先出（LIFO）原则的容器适配器。它的删除操作只能从容器的一端进行，即只能在栈顶插入和提取元素。在STL中，stack默认使用deque作为其底层容器，当然也可以指定vector或list等其他符合要求的容器。

2. 使用方法

- 构造函数： stack<T> s 可以创建一个空栈， T 为栈中元素的类型。

- 判空操作： s.empty() 用于检测栈是否为空，如果为空返回 true ，否则返回 false 。

- 获取元素个数： s.size() 返回栈中元素的个数。

- 获取栈顶元素： s.top() 返回栈顶元素的引用。

- 压栈操作： s.push(x) 将元素 x 压入栈中。

- 弹栈操作： s.pop() 将栈顶元素弹出。

3. 代码示例

cpp#include <iostream>#include <stack>using namespace std;int main() {stack<int> s;s.push(1);s.push(2);s.push(3);while (!s.empty()) {cout << s.top() << " ";s.pop();}return 0;}

1. 模拟实现

cpp#include <vector>namespace bite {template<class T>class stack {public:stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top() const { return _c.back(); }size_t size() const { return _c.size(); }bool empty() const { return _c.empty(); }private:std::vector<T> _c;};}

二、queue（队列）

1. 原理介绍

队列是一种遵循先进先出（FIFO）原则的容器适配器。元素从队尾入队列，从队头出队列。在STL中，queue默认使用deque作为底层容器，也可指定list等符合条件的容器。

2. 使用方法

- 构造函数： queue<T> q 创建一个空队列， T 为队列中元素的类型。

- 判空操作： q.empty() 检测队列是否为空，为空返回 true ，否则返回 false 。

- 获取元素个数： q.size() 返回队列中有效元素的个数。

- 获取队头元素： q.front() 返回队头元素的引用。

- 获取队尾元素： q.back() 返回队尾元素的引用。

- 入队操作： q.push(x) 在队尾将元素 x 入队列。

- 出队操作： q.pop() 将队头元素出队列。

3. 代码示例

cpp#include <iostream>#include <queue>using namespace std;int main() {queue<int> q;q.push(1);q.push(2);q.push(3);while (!q.empty()) {cout << q.front() << " ";q.pop();}return 0;}

1. 模拟实现

cpp#include <list>namespace bite {template<class T>class queue {public:queue() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_front(); }T& back() { return _c.back(); }const T& back() const { return _c.back(); }T& front() { return _c.front(); }const T& front() const { return _c.front(); }size_t size() const { return _c.size(); }bool empty() const { return _c.empty(); }private:std::list<T> _c;};}

三、deque（双向队列）

1. 原理介绍

deque （双端队列）是一种数据结构，通常用连续内存空间存储元素，通过维护头部和尾部指针来实现双端操作。插入和删除元素在两端都能高效进行，时间复杂度通常为O(1)，常用于缓存、广度优先搜索等场景。

2. 使用方法

std::deque<int> d; ；在前端插入

d.push_front(1) ，后端插入

d.push_back(2) ；前端删除

d.pop_front() ，后端删除

d.pop_back() ，访问元素 d[0] 获取首个元素。

3. 代码示例

#include <iostream>
#include <deque>
using namespace std;int main() {// 创建一个空的双端队列deque<int> d;// 在队列后端添加元素d.push_back(1);d.push_back(2);// 在队列前端添加元素d.push_front(3);d.push_front(4);// 输出双端队列的元素cout << "双端队列：";for (int num : d) {cout << num << " ";}cout << endl;// 从后端弹出元素int back_pop = d.back();d.pop_back();cout << "从后端弹出的元素：" << back_pop << endl;// 从前端弹出元素int front_pop = d.front();d.pop_front();cout << "从前端弹出的元素：" << front_pop << endl;// 输出操作后的双端队列的元素cout << "操作后的双端队列：";for (int num : d) {cout << num << " ";}cout << endl;return 0;
}

1. 注意事项

- 默认情况下， deque是大堆。

C++中 deque 的注意事项及示例：

1. 迭代器失效：在 deque 中插入或删除元素后，除了指向被删除元素的迭代器外，其他迭代器可能仍然有效，但可能会导致迭代器重新定位。

cpp#include <iostream>
#include <deque>
using namespace std;int main() {deque<int> d = {1, 2, 3, 4, 5};auto it = d.begin();d.insert(it, 0);  // 插入元素后，迭代器it仍然有效for (int num : d) {cout << num << " ";}cout << endl;return 0;
}

1. 容量和内存管理： deque 的内存管理相对复杂，它通过分段连续内存实现。与 vector 相比， deque 在头部插入和删除元素更高效，因为不需要移动大量元素来调整内存。

cpp#include <iostream>
#include <deque>
using namespace std;int main() {deque<int> d;for (int i = 0; i < 10; ++i) {d.push_front(i);  // 在头部高效插入元素}for (int num : d) {cout << num << " ";}cout << endl;return 0;
}

1. 边界检查：访问 deque 元素时，要确保索引在有效范围内，否则会导致未定义行为。使用 at() 成员函数会进行边界检查并在越界时抛出异常，而使用 [] 操作符不会进行检查。

cpp#include <iostream>
#include <deque>
using namespace std;int main() {deque<int> d = {10, 20, 30};// 使用[]操作符，不进行边界检查cout << d[2] << endl;// 使用at()进行边界检查，越界会抛出异常// cout << d.at(10) << endl;  // 取消注释会抛出异常return 0;
}