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

个人主页：Quitecoder

专栏：c++笔记仓

朋友们大家好，本篇文章我们来到STL新的内容，stack和queue

目录

• 1. stack的介绍与使用
• • `函数介绍`
  • `例题一：最小栈`
  • `例题二：栈的压入、弹出队列`
  • `栈的模拟实现`
  • 2.queue的介绍和使用
  • • `deque的介绍`
    • • `deque的缺陷`
      • `queue的模拟实现`

        1. stack的介绍与使用

        1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
        2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
        3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
           • empty：判空操作
           • back：获取尾部元素操作
           • push_back：尾部插入元素操作
           • pop_back：尾部删除元素操作
           • 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

        函数介绍

        构造函数

        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 elementsstd::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()

        检测stack是否为空

        size()

        返回stack中元素的个数

        top()

        返回栈顶元素的引用

        push()

        将元素val压入stack中

        pop()

        将stack中尾部的元素弹出

        例题一：最小栈

        题目链接：155.最小栈

        题目描述：

        为了实现上面这个栈，我们需要使用两个栈

        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;};

          例题二：栈的压入、弹出队列

          题目链接：牛客

          题目描述：

          该函数的目的是检查给定的出栈顺序 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();    }};// 设计模式// 适配器模式 -- 转换// stackpublic: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;    };}