企业官网建设流程全解析

🎈主页传送门:良木生香
🔥个人专栏:《C语言》《数据结构-初阶》《鼠鼠的C++学习之路》《Linux系统编程》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离

一、前言

在 C++ STL 中，stack和queue是非常常用的容器。但很多人只停留在"会用"的层面，对其底层实现、设计思想以及经典应用场景并不熟悉。那么今天就从容器适配器的设计思想出发，深入讲解stack和queue的底层原理，并配合经典面试题，帮助大家彻底掌握这部分知识。

二、Stack 与 Queue 的本质：容器适配器

2.1 什么是容器适配器？

适配器（Adapter）是一种设计模式：将一个类的接口转换成用户期望的另一个接口。

stack和queue本质上不是独立的容器，而是在已有容器基础上封装的适配器。它们不自己管理数据，而是复用底层容器的接口，只暴露栈/队列特有的操作。

// stack 的声明：底层默认用 dequetemplate<classT,classContainer=deque<T>>classstack;// queue 的声明：底层默认也用 dequetemplate<classT,classContainer=deque<T>>classqueue;

2.2 为什么叫"适配器"？

底层容器（Vector/List/Deque） ┌─────────────────────────────┐ │ push_back() pop_back() │ │ push_front() pop_front()│ │ insert() erase() │ │ operator[] front() │ │ ... │ └──────────┬──────────────────┘ │ 适配（限制接口） ↓ 栈接口（只暴露这几个） ┌─────────────┐ │ push() │ ← 底层调用 push_back │ pop() │ ← 底层调用 pop_back │ top() │ ← 底层调用 back │ size() │ │ empty() │ └─────────────┘

2.3 底层容器的选择

⚠️队列不能用 vector 的pop_front()，因为 vector 头删需要 O(n) 移动所有元素。

三、Stack：后进先出（LIFO）

3.1 核心特性

push(5) ↓ ┌─────────┐ │ 5 │ ← 栈顶（最后入栈，最先出栈） ├─────────┤ │ 4 │ ├─────────┤ │ 3 │ ├─────────┤ │ 2 │ ├─────────┤ │ 1 │ ← 栈底（最先入栈，最后出栈） └─────────┘

3.2 模拟实现（基于 Vector）

template<typenameT,typenameContainer=vector<T>>classStack{public:voidpush(constT&x){_con.push_back(x);}voidpop(){_con.pop_back();}T&top(){return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};

3.3 时间复杂度

四、Queue：先进先出（FIFO）

4.1 核心特性

出队（pop） 入队（push） ↓ ↓ ┌───────┬───────┬───────┬───────┐ │ 1 │ 2 │ 3 │ 4 │ └───────┴───────┴───────┴───────┘ ↑ ↑ front back 入队顺序：1 → 2 → 3 → 4 出队顺序：1 → 2 → 3 → 4（完全相同）

4.2 模拟实现（基于 List）

template<typenameT,typenameContainer=list<T>>classQueue{public:voidpush(constT&x){_con.push_back(x);}// 队尾入voidpop(){_con.pop_front();}// 队头出T&front(){return_con.front();}T&back(){return_con.back();}size_tsize()const{return_con.size();}boolempty()const{return_con.empty();}private:Container _con;};

4.3 循环队列（数组实现）

template<typenameT,size_t N>classCircularQueue{T _data[N];size_t _front=0,_rear=0,_size=0;public:boolpush(constT&x){if(_size==N)returnfalse;_data[_rear]=x;_rear=(_rear+1)%N;++_size;returntrue;}boolpop(){if(_size==0)returnfalse;_front=(_front+1)%N;--_size;returntrue;}T&front(){return_data[_front];}boolempty()const{return_size==0;}boolfull()const{return_size==N;}};

五、List 迭代器的operator->重载

5.1 问题场景

当 List 中存储的是结构体时，如何通过迭代器访问成员？

structPoint{int_x,_y;};List<Point>points;points.push_back({1,2});autoit=points.begin();// (*it)._x = 10; // 方式1：先解引用再访问成员// it->_x = 10; // 方式2：更简洁，需要 operator-> 支持

6.2operator->的实现

template<typenameT,typenameRef,typenamePtr>struct__ListIterator{Node*_node;// 解引用，返回 data 的引用Refoperator*(){return_node->_data;}// 返回 data 的指针Ptroperator->(){return&_node->_data;}};// it->x 的调用过程：// it.operator->() → &_node->_data → (&_node->_data)->x// 编译器会自动优化为直接访问成员

六、经典面试题详解

6.1 最小栈（O(1) 获取最小值）

思路：用两个栈，一个存数据，一个存最小值。

classMinStack{stack<int>_data;// 数据栈stack<int>_min;// 辅助栈：存当前最小值public:voidpush(intx){_data.push(x);// 如果 x 比之前的最小值还小（或等于），压入 xif(_min.empty()||x<=_min.top()){_min.push(x);}else{_min.push(_min.top());// 重复压入当前最小值}}voidpop(){_data.pop();_min.pop();}inttop(){return_data.top();}intgetMin(){return_min.top();}};// push 5: _data=[5], _min=[5]// push 2: _data=[5,2], _min=[5,2]// push 7: _data=[5,2,7], _min=[5,2,2]// push 1: _data=[5,2,7,1], _min=[5,2,2,1]// getMin() → 1// pop() → _data=[5,2,7], _min=[5,2,2]// getMin() → 2

⚠️注意：当data > min.top()时，minst不 push。但相同 min 时两边同时进，否则删除后minst不更新！

6.2 栈的压入/弹出序列验证

思路：用辅助栈模拟入栈过程，同时比较出栈序列。

boolvalidateStackSequences(vector<int>&pushed,vector<int>&popped){stack<int>st;intj=0;// 指向 popped 的索引for(intx:pushed){st.push(x);// 入栈序列入栈// 栈顶与出栈序列比较while(!st.empty()&&st.top()==popped[j]){st.pop();++j;// 匹配成功，继续比较下一个}}// 当入栈序列走完，但出栈序列不为空，则为 falsereturnst.empty();}

6.3 逆波兰表达式求解

中缀转后缀示例：

中缀：1 + 2 × (3 + 4) / 5 后缀：1 2 3 4 + × 5 / + 计算过程： 遇到 1：压栈 [1] 遇到 2：压栈 [1, 2] 遇到 3：压栈 [1, 2, 3] 遇到 4：压栈 [1, 2, 3, 4] 遇到 +：弹出 4 和 3，计算 3+4=7，压栈 [1, 2, 7] 遇到 ×：弹出 7 和 2，计算 2×7=14，压栈 [1, 14] 遇到 5：压栈 [1, 14, 5] 遇到 /：弹出 5 和 14，计算 14/5=2，压栈 [1, 2] 遇到 +：弹出 2 和 1，计算 1+2=3，压栈 [3] 结果：3

intevalRPN(vector<string>&tokens){stack<int>st;for(conststring&token:tokens){if(token=="+"||token=="-"||token=="*"||token=="/"){intb=st.top();st.pop();inta=st.top();st.pop();if(token=="+")st.push(a+b);elseif(token=="-")st.push(a-b);elseif(token=="*")st.push(a*b);elseif(token=="/")st.push(a/b);}else{st.push(stoi(token));}}returnst.top();}

6.4 用两个栈实现队列

classMyQueue{stack<int>_in;// 入队栈stack<int>_out;// 出队栈public:voidpush(intx){_in.push(x);}intpop(){peek();intval=_out.top();_out.pop();returnval;}intpeek(){if(_out.empty()){while(!_in.empty()){_out.push(_in.top());_in.pop();}}return_out.top();}boolempty(){return_in.empty()&&_out.empty();}};

6.5 二叉树的层序遍历（队列应用）

vector<vector<int>>levelOrder(TreeNode*root){vector<vector<int>>result;if(!root)returnresult;queue<TreeNode*>q;q.push(root);while(!q.empty()){intlevelSize=q.size();vector<int>level;for(inti=0;i<levelSize;++i){TreeNode*node=q.front();q.pop();level.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}result.push_back(level);}returnresult;}

七、总结

关键要点回顾

1. 容器适配器：stack和queue不是独立容器，而是复用底层容器的适配器
2. 队列不能用 vector：因为 vector 没有高效的pop_front()
3. 默认底层：stack和queue默认用deque
4. 最小栈：双栈实现，辅助栈同步压入当前最小值
5. 逆波兰表达式：遇到数字入栈，遇到运算符弹出两个数计算
6. 栈序列验证：辅助栈模拟入栈，同时比较出栈序列

那么以上就是本次所有的内容了
文章是自己写的哈，有什么描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读~~~~