Wong Kosheng1. C++中的stack与queue基础解析
作为一名长期使用C++进行开发的工程师，stack和queue是我日常工作中最常用的两种数据结构。它们看似简单，但在实际应用中却有着不可替代的作用。
stack（栈）遵循LIFO（Last In First Out）原则，就像我们平时叠放的一摞盘子，最后放上去的盘子总是最先被取用。这种特性使得stack在函数调用栈、表达式求值、括号匹配等场景中表现出色。在C++标准库中，stack提供了简洁的接口：
cpp复制std::stack<int> s;
s.push(1); // 入栈
int top = s.top(); // 获取栈顶元素
s.pop(); // 出栈
queue（队列）则遵循FIFO（First In First Out）原则，类似于现实生活中的排队场景，先来的人先接受服务。这种特性使得queue在消息队列、任务调度、广度优先搜索等场景中非常有用。C++中的queue接口同样直观：
cpp复制std::queue<int> q;
q.push(1); // 入队
int front = q.front(); // 获取队首元素
q.pop(); // 出队
重要提示：stack和queue都不提供遍历功能，这是由其数据结构的本质特性决定的。如果需要遍历元素，可能需要重新考虑数据结构的选择。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 容器适配器与底层实现
2.1 stack和queue的本质
很多初学者可能会误以为stack和queue是独立的容器，实际上它们是容器适配器（Container Adapter）。这意味着它们是在其他基础容器之上构建的，通过限制基础容器的接口来实现特定的数据结构行为。
在C++标准库中，stack和queue的默认底层容器是deque（双端队列），但我们也可以指定其他容器：
cpp复制std::stack<int, std::vector<int>> vec_stack; // 使用vector作为底层
std::queue<char, std::list<char>> list_queue; // 使用list作为底层
2.2 为什么选择deque作为默认容器
STL选择deque作为stack和queue的默认底层容器，主要基于以下考虑：
- 内存效率：deque的内存分配是分块的，不像vector需要连续内存，也不像list需要为每个元素分配额外空间
- 操作效率：deque在两端插入删除都是O(1)时间复杂度，完美适配stack和queue的操作需求
- 平衡性：deque在内存使用和操作效率之间取得了良好的平衡