【c++】深入剖析与动手实践：C++中Stack与Queue的艺术

1. stack的介绍与使用
- `函数介绍`
- `例题一：最小栈`
- `例题二：栈的压入、弹出队列`
- `栈的模拟实现`
- 2.queue的介绍和使用
- - `deque的介绍`
  - - `deque的缺陷`
    - `queue的模拟实现`
      1. stack的介绍与使用
      $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第3张$
      1. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
        empty：判空操作
        back：获取尾部元素操作
        push_back：尾部插入元素操作
        pop_back：尾部删除元素操作
        标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。
      $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第4张$
      函数介绍
      🔥构造函数
      $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第5张$
```
explicit stack (const container_type& ctnr = container_type());
```
      这个构造函数定义的是 std::stack 类模板的一个构造函数，它接受一个参数，类型是 container_type。这里的 container_type 是 std::stack 的成员类型，它表示用于内部存储的容器类型，通常是某种顺序容器比如 std::deque、std::list 或 std::vector。
      关键字 explicit 表示这个构造函数禁止隐式类型转换。换句话说，你不能隐式地从 container_type 赋值给 std::stack 对象，而必须显式地调用构造函数：
```
std::deque mydeque(3,100);          // deque with 3 elements
std::stack first (mydeque);          // stack initialized to copy of deque
```
      上面的代码中，我们创建了一个 std::deque 对象 mydeque，然后使用它显式地构造一个 std::stack 对象 first。如果没有 explicit 关键字，下面的代码也是有效的：
```
std::stack myStack = mydeque; // 这一行在 explicit 关键字存在时是不合法的
```
      但有 explicit 关键字时，这种隐式转换就会产生编译错误。
      构造函数的参数 ctnr 还有一个默认值 container_type()。这表示如果在构造 std::stack 对象时没有提供参数，将会使用 container_type 的默认构造函数创建一个新的空容器作为 std::stack 的内部存储。这允许你像下面这样简单地创建一个空栈：
```
std::stack myStack; // 空栈，使用默认的底层容器（通常是 std::deque）
```
      在这种情况下，myStack 是空的，因为没有向构造函数传递任何参数，它会使用底层容器类型的默认构造函数创建一个空的内部容器
      🔥empty()
      $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第6张$
      检测stack是否为空
      🔥size()
      返回stack中元素的个数
      🔥top()
      $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第7张$
      返回栈顶元素的引用
      🔥push()
      $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第8张$
      将元素val压入stack中
      🔥pop()
      $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第9张$
      将stack中尾部的元素弹出
      例题一：最小栈
      题目链接：155.最小栈
      题目描述： $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第10张$
      为了实现上面这个栈，我们需要使用两个栈
```
stack s1;
stack s2;
```
      1. s1 是一个标准的栈，它用于按照后进先出的顺序存储所有推入的元素
      2. s2 是一个辅助栈，它用于跟踪 s1 中所有元素的最小值
      - MinStack()：构造函数，初始化两个空栈 s1 和 s2
      - void push(int val)：在 s1 中推入 val。如果 s2 为空或者 val 小于等于 s2 的栈顶元素，也将 val 推入 s2。这保证 s2 的栈顶元素始终是 s1 中当前所有元素的最小值
      - void pop()：从 s1 中弹出一个元素。如果 s1 的栈顶元素与 s2 的栈顶元素相等，说明 s1 弹出的元素是当前的最小值，因此也需要在 s2 中弹出栈顶元素
      - int top()：返回 s1 的栈顶元素，即 MinStack 的栈顶元素
      - int getMin()：返回 s2 的栈顶元素，即 s1 中当前所有元素的最小值
        代码实现如下：
        
        class MinStack { public: MinStack() { } void push(int val) { s1.push(val); if(s2.empty()||s2.top()>=val) { s2.push(val); } } void pop() { if(s1.top()==s2.top()) { s2.pop(); } s1.pop(); } int top() { return s1.top(); } int getMin() { return s2.top(); } private: stack s1; stack s2; };
        
        例题二：栈的压入、弹出队列
        题目链接：牛客
        题目描述： $【c++】深入剖析与动手实践：C++中Stack与Queue的艺术,在这里插入图片描述,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,操作,没有,li,第11张$
        该函数的目的是检查给定的出栈顺序 popV 是否能由相应的入栈顺序 pushV 实现。换句话说，函数判断是否存在某种方式，使得按 pushV 指定的顺序入栈后，能够按 popV 指定的顺序出栈
        代码实现如下：
        
        class Solution { public: bool IsPopOrder(vector& pushV, vector& popV) { int pushi=0,popi=0; stack s; while(pushi s.push(pushV[pushi]); while(!s.empty()&&s.top()==popV[popi]) { s.pop(); popi++; } pushi++; } return s.empty(); } }; // 设计模式 // 适配器模式 -- 转换 // stack public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_back(); } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } const T& top() { return _con.back(); } private: Container _con; }; } template 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: Con _c; }; }