一. Stack & Queue
常用成员函数：
简单使用一下栈，先进先出
#include<iostream> #include<stack> using namespace std; int main() { stack<int> st; st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << endl; st.pop(); } }
💥经典题目
🥑最小栈
题目链接：155. 最小栈
🌍思路：
辅助栈，以空间换时间，st.push()时同时比较，把较小值也压入 minst中，pop时 st和 minST同时弹栈，这样取 minST栈顶元素即最小值 ——
st尽管可能存储了很多相同的数据，但对于minst，我们只在< = 时入栈，st和 minST相同再一起出栈
class MinStack { public: MinStack() { //默认的即可：自定义类型自动调用它的构造函数 } void push(int val) { _st.push(val); if(_minst.empty() || val <= _minst.top())//顺序不能互换 // 出现<=前面的值，则插入新的最小数据 _minst.push(val); } void pop() { if(_minst.top() == _st.top()) _minst.pop();//minst和st删除顺序不能换，先st删了，top数据就出错了 _st.pop(); } int top() { return _st.top(); } int getMin() { return _minst.top(); } private: stack<int> _st; stack<int> _minst; };
🔥题目升级：如果插入大量重复数据（插入10w个1），怎么办？
minst里面就存一个结构体，遇到相等就计数++
🥑栈的压入、弹出序列
题目链接：JZ31 栈的压入、弹出序列
🌍入栈顺序来模拟出栈顺序
首先对入栈序列进行遍历，对栈进行操作
入栈数据与出栈数据不相同 —>入栈
入栈数据与出栈数据相同 ——> 出栈，也就是刚进栈就出去了
不断重复，直到栈为空/栈顶元素和出栈序列的值不匹配就结束了
画图分析：
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { stack<int> st; int popi = 0; for(auto e:pushV) { st.push(e); //匹配后要持续比较，可能有多个匹配 while(!st.empty() && st.top() == popV[popi]) { st.pop(); popi++; } } return st.empty(); } };
🥑逆波兰表达式求值
题目链接：150. 逆波兰表达式求值
后缀表达式转成中缀表达式
🌍思路：
操作数入栈
操作符，连续取两个栈顶元素进行计算(先出的是右操作数，后出的的是左操作数)，运算结果继续入栈
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for(auto& str : tokens) { if(str== "+" || str== "-" || str== "*" ||str== "/") { int right = st.top(); st.pop(); int left = st.top(); st.pop(); switch(str[0])//取str[0]就是char { case '+': st.push(left+right); break; case '-': st.push(left-right); break; case '*': st.push((long long)left*right); break; case '/': st.push(left/right); break; } } //操作数 else { st.push(stoll(str)); } } return st.top(); } };
吐槽:有一个奇葩的测试用例是 long long，最后还要转成int（无语）
🔥升级：对于计算机而言，中缀表达式有优先级问题，而后缀表达式操作符都按优先级排列好了，如何将中缀表达式转化为后缀表达式呢？（和上面恰恰相反）
遇到操作数，直接输出
操作符
若栈为空，直接入栈
栈不为空，跟栈顶的操作符比较（每次和前一个操作符比较）
若优先级更高，不能运算，因为可能有更高的 → 入栈
相反，优先级低/相等 → 此时栈顶的操作符出栈，表示此时可以进行运算
再升级：带（）的优先级：1 +（ 2 + 3 ）* 4 - 5
用flag代表括号，临时升高优先级
🥑两个栈实现队列
题目链接：232. 用栈实现队列
思路可参考：此文章——>【数据结构】栈实现队列 & 队列实现栈🥑
class MyQueue { public: MyQueue() { //不用写，用系统自动生成的即可 } void push(int x) { pushst.push(x); } int pop() { if(popst.empty()) { while(!pushst.empty()) { popst.push(pushst.top()); pushst.pop(); } } int top = popst.top(); popst.pop(); return top; } int peek() { if(popst.empty()) { while(!pushst.empty()) { popst.push(pushst.top()); pushst.pop(); } } return popst.top(); } bool empty() { return pushst.empty() && popst.empty(); } private: stack<int> pushst; stack<int> popst; };
🥑两个队列实现栈
题目链接：225. 用队列实现栈
详细思路：详细看上面的链接,就是_q2完全用作辅助队列，出入数据都在 _q1
class MyStack { public: MyStack() { //用系统自动生成的 } void push(int x) { _q1.push(x); } int pop() { while(_q1.size()>1) { _q2.push(_q1.front()); _q1.pop(); } int top = _q1.front(); _q1.pop(); //数据倒回给_q1 while(_q2.size()) { _q1.push(_q2.front()); _q2.pop(); } return top; } int top() { return _q1.back(); } bool empty() { return _q1.empty(); } private: queue<int> _q1; queue<int> _q2; };
二. 容器适配器
🌈什么是适配器
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口，说白了就是：不是写死的，谁只要合适就可以来用
🌈STL标准库中stack和queue的底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：
三. 栈和队列的模拟实现
💥stack的模拟实现
#pragma once #include<deque> namespace ljj { //适配器 template<class T, class Container = deque<T>>//deque后面细说 class Stack { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } T& top()//使用通用的接口，不要用[] { return _con.back(); } const T& top() const { return _con.back(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); }
private:
//封装一个容器vector //vector<T> _con; 不够灵活 //只要Container满足上面的接口都可以 Container _con; }; } void test_stack() { //底层大有不同，但是表面我们看不出来 //ljj::Stack<int , vector<int>> st; //ljj::Stack<int , list<int>> st; ljj::Stack<int> st;//deque适配出来的 st.push(1); st.push(2); st.push(3); st.push(4); while (!st.empty()) { cout << st.top() << endl; st.pop(); } }
💥Queue的模拟实现
#pragma once #include<deque> namespace ljj { //适配器 template<class T, class Container = deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } T& top() { return _con.back(); } T& front() { return _con.front(); } T& top() const { return _con.back(); } T& front() const { return _con.front(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; } void test_queue() { //ljj:queue<int> q; //不想用默认的deque可以用其他 ljj:queue<int, list<int>> q; q.push(1); q.push(2); q.push(3); q.push(4); while (!q.empty()) { cout << q.front() << endl; q.pop(); } }
四. deque: stack和queue的底层结构（了解）
deque强烈的勾起了我们的好奇心。
众所周知，vector连续的物理空间带来了优点，它支持随机访问，CPU高速缓存命中率高，另外尾插尾删效率高；但也同时带来了缺点，不适合头插头删，另外扩容效率较低，也会造成一定的空间浪费。list按需申请释放空间，支持任意位置的 O(1) 插入删除；但不支持下标随机访问。
而双端队列deque就是为了融合二者优点而产生的 ~ 比如詹姆斯（进攻防守都厉害）（有伏笔）
它支持随机迭代器、下标访问、任意位置的插入和删除 ——
⚡底层原理
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高
🎨deque并不是真正连续的空间，而是由一段段连续的小空间buffer拼接而成的，其底层结构如下 ——
这样，与vector相比，deque头插头删不需要挪动数据，且扩容时的代价也大大降低；与list相比，deque高速缓存命中率高，且不需要频繁的申请释放空间，且可以“随机访问”
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示
那deque是如何借助其迭代器维护其假想连续的结构呢？
insert和erase也比较复杂。所以要高频随机访问还得是vector，要任意位置插入删除还得是list。它没能取代list和vector的宝座，但它很适合头尾的插入删除(双端)
⚡缺点
operator[]计算稍显复杂，大量使用，性能下降（不如vector的[]）
中间插入删除效率不高（要么挪动数据，要么改buffer的空间，都不好）
底层角度迭代器很复杂
所以要高频随机访问还得是vector，要任意位置插入删除还得是list。它没能取代list和vector的宝座，但它很适合头尾的插入删除(双端)
⚡为什么
为什么选deque来作为stack和list的底层默认容器?
stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
在stack中元素增长时，deque比vector的效率高；queue中的元素增长时，deque不仅效率高，而且内存使用率高。vector当容量不够时，会开更大的空间，拷数据然后释放原来的空间，操作复杂。而deque会找另一块内存继续存放数据，效率高。
相比较list，deque的插入操作会更加的高效，而且内存的使用率高，list会导致更多的内存碎片。
刚好都避开了deque的缺点
所以，deque作为stack和queue的默认容器是完胜的，不能独挡一面，但是是一个好用的二把手（暗指谁哈哈哈）
