[特殊字符] 栈与队列基础知识全面解析

一、栈（Stack）理论基础

1.1 栈的基本特性

栈是一种后进先出（LIFO, Last In First Out）的数据结构，操作只在栈顶进行。

// 栈的基本操作stack<int>st;st.push(1);// 入栈st.push(2);inttop=st.top();// 查看栈顶元素：2st.pop();// 出栈，移除2boolempty=st.empty();// 判断栈是否为空

1.2 C++中栈的实现原理

重要概念：栈在C++中不是容器，而是容器适配器（container adapter）

// C++中栈的底层实现std::stack<int>st1;// 默认使用deque作为底层容器std::stack<int,std::vector<int>>st2;// 指定vector作为底层容器std::stack<int,std::list<int>>st3;// 指定list作为底层容器

栈的底层容器选择：

• deque（默认）：双向队列，内存非连续
• vector：动态数组，内存连续
• list：双向链表，内存非连续

1.3 STL栈的实现版本

SGI STL中栈的关键特性：

• 不提供迭代器（不能遍历）
• 不支持随机访问
• 对外提供统一接口，底层可插拔

二、队列（Queue）理论基础

2.1 队列的基本特性

队列是一种先进先出（FIFO, First In First Out）的数据结构。

// 队列的基本操作queue<int>q;q.push(1);// 入队q.push(2);intfront=q.front();// 查看队首元素：1q.pop();// 出队，移除1boolempty=q.empty();// 判断队列是否为空

2.2 C++中队列的实现原理

队列也是容器适配器

// C++中队列的底层实现std::queue<int>q1;// 默认使用deque作为底层容器std::queue<int,std::list<int>>q2;// 指定list作为底层容器

队列的底层容器要求：

• 必须支持push_back()（入队）
• 必须支持pop_front()（出队）
• 必须支持front()（查看队首）

2.3 常见问题解答

Q1：栈/队列是容器吗？
A：不是。它们是容器适配器，底层使用其他容器实现。

Q2：栈/队列支持遍历吗？
A：不支持。它们不提供迭代器，只能通过pop()逐个访问。

Q3：栈/队列在内存中连续吗？
A：取决于底层容器。默认用deque，内存不连续；如果用vector则连续。

三、栈与队列的相互实现

3.1 用栈实现队列（LeetCode 232）

classMyQueue{private:stack<int>stIn;// 输入栈stack<int>stOut;// 输出栈public:MyQueue(){}// 入队：直接压入输入栈voidpush(intx){stIn.push(x);}// 出队intpop(){// 如果输出栈为空，把输入栈所有元素导入if(stOut.empty()){while(!stIn.empty()){stOut.push(stIn.top(