【C++初阶：STL —— stack and queue】stack/queue的介绍及使用 | stack/queue/priority_queue的深度剖析及模拟实现 | 适配器模式

文章目录

【写在前面】

虽然 cplusplus 把 stack 和 queue 归类到了 Containers 下，但是严格来说 stack and queue 不再是容器了，而属于容器适配器 or 容器配接器，适配器做的功能是转换 —— 它不是直接实现的，而是由其它容器封装转换实现的，在下面的模拟实现我们会细谈。

它做为容器适配器，它与容器有一个具大的差别之一就是它没有迭代器，不是说它不能实现迭代器，而是没有必要实现迭代器，因为它如果实现了迭代器，就没法保障 stack “Last In First Out” 和 queue “First In First Out” 的原则。

其次对于 stack 和 queue 的使用比较简单，我们大概过一下，以 OJ 的形式来了解它们。

一、stack的介绍及使用

💦 stack的介绍

stack文档介绍

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

💦 stack的使用

函数声明	接口说明
stack()	构造空的栈
empty()	检测 stack 是否为空
size()	返回 stack 中元素的个数
top()	返回栈顶元素的引用
push()	将元素 val 压入 stack 中
pop()	将 stack 中尾部的元素弹出

#include<iostream>
#include<stack>
using namespace std;
void test_stack()
{
  stack<int> st;
  st.push(1);
  st.push(2);
  st.push(3);
  while(!st.empty())
  {
    cout << st.top() << " ";
    st.pop();
  }
  cout << endl;
}
int main()
{
  test_stack();
  return 0;
}

💦 stack的OJ

1、最小栈＜难度系数⭐＞

📝 题述：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类(要求以下接口的时间复杂度都是 O(1))：

MinStack() 初始化堆栈对象。
void push(int val) 将元素 val 推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

💨示例1：

输入：

[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]

[[],[-2],[0],[-3],[],[],[],[]]

输出：

[null,null,null,null,-3,null,0,-2]

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); -> 返回 -3.

minStack.pop();

minStack.top(); -> 返回 0.

minStack.getMin(); -> 返回 -2.

⚠ 提示：

-2³¹ <= val <= 2³¹ - 1
pop、top 和 getMin 操作总是在非空栈上调用
push、pop、top、and getMin 最多被调用 3 * 10⁴ 次

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：这里它并没有要求我们使用数组或链表去原生实现，我们这里使用库里的栈，实现接口功能即可。

比如【3, 8, 5, 0 (这里先 push 4 个数据，再 pop 一个数据)】，其次定义 _min 去记录最小值，每次 push 满足条件时就更新 _min，但是当 pop 时就会把 _min 的值删除掉，这时的最小值是 3，但是你怎么写才能知道是 3，你必须得遍历一遍栈里的所有数据，才能知道最小值是 3，而此时的 pop 就不再是 O(1) 了。

所以我们正确的操作应该给两个栈，一个栈存正常值，另一个栈存最小值(注意这里的最小值存多个)，比如【3, 8, 5, 0 (这里先 push 4 个数据，再 pop 一个数据)】，这里在往第一个栈 push 时就记录最小值到第二个栈【3, 0】，如果两个栈里的值 pop 是一样的，那就都 pop，【3】，否则就只 pop 第一个栈。这就是经典的以空间换时间的思想。

边缘问题，比如【3, 8, 5, 0 (这里先 push 4 个数据，再 pop 一个数据，再 push 0，4，0)】，最后一个 0 需要 push 吗 ? 答案是需要的，如果不 push，再 pop 的话就会把最小值给删除(因为这里栈顶的数据是相同的)，此时 getMin 就是 5，但是其实不是。

leetcode原题

class MinStack {
public:
    //这里其实可以不用写它的构造函数(把它删了也ok),因为_st and _minst都是自定义类型(调用默认构造初始化),同时也不需要实现析构函数(调用默认析构(栈的析构)),同理拷贝构造和赋值也不需要。
    MinStack() {
    }
    void push(int val) {
        _st.push(val);
        //更新栈
        if(_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }
    void pop() {
        //_st必须pop,相同就都pop
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    int top() {
        return _st.top();
    }
    int getMin() {
        //_minist的栈顶就是当前_st的最小值 
        return _minst.top();
    }
    stack<int> _st;
    stack<int> _minst;
};
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

2、栈的弹出压入序列＜难度系数⭐⭐＞

📝 题述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1，2，3，4，5 是某栈的压入顺序，序列 4，5，3，2，1 是该压栈序列对应的一个弹出序列，但 4，5，3，2，1 就不可能是该压栈序列的弹出序列。

⚠ 提示：

0 <= pushV.length == popV.length <= 1000
-1000 <= pushV[i] <= 1000
pushV 的所有数字均不相同

💨示例1：

输入：

[1,2,3,4,5],[4,5,3,2,1]

返回值：

true

说明:

可以通过

push(1) => push(2) => push(3) => push(4) => pop() => push(5) => pop() => pop() => pop() => pop()

这样的顺序得到 [4,5,3,2,1] 这个序列，返回 true。

💨示例2：

输入：

[1,2,3,4,5],[4,3,5,1,2]

返回值：

false

说明：

由于是 [1,2,3,4,5] 的压入顺序，[4,3,5,1,2] 的弹出顺序，要求 4，3，5 必须在 1，2 前压入，且 1，2 不能弹出，但是这样压入的顺序，1 又不能在 2 之前弹出，所以无法形成，返回 false。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：这道题之前我们有碰到过选择题。这道题本质就是模拟栈的特性 “Last In First Out”。

这里定义了一个栈来模拟，不管三七二十一，pushi 先入栈，随后 ++，出栈的顺序一定是入栈后再出的，所以每次入栈后都需要判断 pushi and popi 是否相等，相等就出(且要循环着出)，否则就入，它们两个都能走到最后，就说明是匹配的。

nowcoder原题

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        size_t pushi = 0, popi = 0;
        //压入顺序结束就必须出结果
        while(pushi < pushV.size())
        { 
            //先入一个数据,然后++
            st.push(pushV[pushi++]);
            //循环出栈
            while(!st.empty() && st.top() == popV[popi])
            {
                ++popi;
                st.pop();
            }
        }
        //st为空,说明匹配
        return st.empty();
        //同上
        //return popi == popV.size();
    }
};

3、逆波兰表达式求值＜难度系数⭐⭐＞

📝 题述：根据逆波兰表示法，求表达式的值。有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

💨示例1：

输入：tokens = [“2”,“1”,“+”,“3”,“*”]

输出：9

解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

💨示例2：

输入：tokens = [“4”,“13”,“5”,“/”,“+”]

输出：6

解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

💨示例3：

输入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]

输出：22

解释：该算式转化为常见的中缀算术表达式为：

((10 * (6 / ((9 + 3) * -11))) + 17) + 5

= ((10 * (6 / (12 * -11))) + 17) + 5

= ((10 * (6 / -132)) + 17) + 5

= ((10 * 0) + 17) + 5

= (0 + 17) + 5

= 17 + 5

= 22

⚠ 提示：

1 <= tokens.length <= 10⁴
tokens[i] 是一个算符（“+”、“-”、“*” 或 “/”），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
中缀表达式面临的最大问题在于程序不方便运算，因为运算符优先级的问题，所以我们处理这种问题可以先将中缀表达式转换成后缀表达式，然后用后缀表达式进行运算。
大概了解下中缀表达式转后缀表达式，这里需要借助栈
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：在了解完后缀表达式怎么由中缀表达式转换后，这里题目本意是需要我们计算后缀表达式的值。

leetcode原题

🧿 版本一

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(const auto str : tokens)
        {
            //建议不要这样写,因为如果操作数是负数,就会出bug
            /*switch(str[0])
            {
                case: '+':
                //... ...
            }*/
            int left, right;
            //+、-、*、/,就出两个栈顶的元素,top1对应right,top2对应left,再把计算的结果入栈
            if(str == "+")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left + right);
            }
            else if(str == "-")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left - right);
            }
            else if(str == "*")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left * right);
            }
            else if(str == "/")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                st.push(left / right);
            }
            else//操作数
            {
                //入栈前,将字符串转整型 
                st.push(stoi(str));
            }
        }
        //返回此时栈顶的元素
        return st.top();
    }
};

🧿 版本二 (优化版本一)

优化的点在于 “ 在判断操作符时有大量冗余的代码 ”。

解决方案：

封装一个成员函数 (能解决，但还能更好的方法？)。
这道题使用 map 非常简单，但目前我们还没学，就不谈了。
使用逻辑或 “ || ”，这种写法的问题是把运算结果 push 时不知道是什么操作符。解决方法就是定义一个 48 大小的数组建立映射关系，比如在下标 47 的位置存储 “ / ”，然后根据对应的字符就可以取到对应的符号，但是数组里所存储的字符，不是类型，所以没错，~~ 翻车了，连第 2 种方案好像也翻车了，所以这里给成员函数好像是比较好的方案了，或者在 “ || ” 的基础上使用 switch 语句 (这两种方法差不多，只是减少了代码量，本质并没有多少的改进)。无妨，多翻车才能更好的上车嘛！！！
注：其实也有更好的简化的方案的，只不过目前我们玩不了，这里先吊下大家的胃口 —— C++11 的包装器。也欢迎大家有更好的方案可以在评论区留言。

//版本二(优化版本一)
class Solution {
public:
    //解决方案一：
    void getnum(stack<int>& st, int& l, int& r)
    {}
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(const auto str : tokens)
        {
            int left, right;
            if(str == "+" || str == "-" || str == "*" || str == "/")
            {
                right = st.top();
                st.pop();
                left = st.top();
                st.pop();
                switch(str[0])
                {
                case '+':
                    st.push(left + right);
                    break;
                case '-':
                    st.push(left - right);
                    break;
                case '*':
                    st.push(left * right);
                    break;
                case '/':
                    st.push(left / right);
                    break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

🧿 版本三 (优化版本二，骚操作)

这里可以先跳过，把后面 C++11 的包装器、map 等，等学了再来看。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        map<string, function<int(int, int)>> opCountMap = 
        {
            {"+", [](int x, int y)->int{return x + y;}},
            {"-", [](int x, int y)->int{return x - y;}},
            {"*", [](int x, int y)->int{return x * y;}},
            {"/", [](int x, int y)->int{return x / y;}}
        };
        stack<int> st;
        for(auto& str : tokens)
        {
            if(str == "+" || str == "-" || str == "*" || str == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                st.push(opCountMap[str] (left, right));
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

4、用栈实现队列＜难度系数⭐＞

📝 题述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作 (push、pop、peek、empty)：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾。
int pop() 从队列的开头移除并返回元素。
int peek() 返回队列开头的元素。
boolean empty() 如果队列为空，返回 true；否则，返回 false。

⚠ 说明：

你只能使用标准的栈操作 —— 也就是只有 push to top、peek/pop from top、size、is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque (双端队列) 来模拟一个栈，只要是标准的栈操作即可。

💨示例1：

输入：

[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 1, 1, false]

解释：

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is [2]

myQueue.empty(); // return false

⚠ 提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 (例如，一个空的队列不会调用 pop 或者 peek 操作)

☣ 进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：我们之前用 C语言写过 “ 两个队列实现栈 ” and “ 两个栈实现队列 ”。用 C++ 实现就很简单了。

leetcode原题

4、用队列实现栈＜难度系数⭐＞

leetcode原题

💦 stack的模拟实现

vector 模拟实现 stack。

#include<vector>
namespace bit
{
  template<class T>
  class stack
  {
  public:
    stack(){}
    //先进
    void push(const T& x){_ve.push_back(x);}
    //后出
    void pop(){_ve.pop_back();}
    const T& top(){return _ve.back();}
    size_t size(){return _ve.size();}
    bool empty(){return _ve.empty();}
  private:
    std::vector<T> _ve;
  };
}

二、queue的介绍及使用

💦 queue的介绍

queue文档介绍

队列是一种容器适配器，专门用于在 FIFO 上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
➡ empty：检测队列是否为空
➡ size：返回队列中有效元素的个数
➡ front：返回队头元素的引用
➡ back：返回队尾元素的引用
➡ push_back：在队列尾部入队列
➡ pop_front：在队列头部出队列
标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。

💦 queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回 true，否则返回 false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素 val 入队列
pop()	将队头元素出队列

#include<iostream>
#include<queue>
using namespace std;
void test_queue()
{
  queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);
  while(!q.empty())
  {
    //queue与stack相同的是入数据都是push,但出数据stack是top,queue是front
    cout << q.front() << " ";
    q.pop();
  }
  cout << endl;
}
int main()
{
  test_queue();
  return 0;
}

💦 queue的模拟实现

list 模拟实现 queue。

#include<list>
namespace bit
{
  template class<T>
  class queue
  {
  public:
    queue(){}
    //先进
    void push(const T& x){_qu.push_back(x);}
    //先出
    void pop(){_qu.pop_front();}
    const T& front(){return _qu.front();}
    size_t size(){return _qu.size();}
    bool empty(){return _qu.empty();}  
  private:  
    std::list<T> _qu;
  };
}

【C++初阶：STL —— stack and queue】stack/queue的介绍及使用 | stack/queue/priority_queue的深度剖析及模拟实现 | 适配器模式 | 仿函数上

文章目录

【写在前面】

一、stack的介绍及使用

💦 stack的介绍

💦 stack的使用

💦 stack的OJ

1、最小栈＜难度系数⭐＞

2、栈的弹出压入序列＜难度系数⭐⭐＞

3、逆波兰表达式求值＜难度系数⭐⭐＞

4、用栈实现队列＜难度系数⭐＞

4、用队列实现栈＜难度系数⭐＞

💦 stack的模拟实现

二、queue的介绍及使用

💦 queue的介绍

💦 queue的使用

💦 queue的模拟实现

热门文章

最新文章

相关课程

相关电子书

【C++初阶：STL —— stack and queue】stack/queue的介绍及使用 | stack/queue/priority_queue的深度剖析及模拟实现 | 适配器模式 | 仿函数 上

文章目录

【写在前面】

一、stack的介绍及使用

💦 stack的介绍

💦 stack的使用

💦 stack的OJ

1、最小栈＜难度系数⭐＞

2、栈的弹出压入序列＜难度系数⭐⭐＞

3、逆波兰表达式求值＜难度系数⭐⭐＞

4、用栈实现队列＜难度系数⭐＞

4、用队列实现栈＜难度系数⭐＞

💦 stack的模拟实现

二、queue的介绍及使用

💦 queue的介绍

💦 queue的使用

💦 queue的模拟实现

热门文章

最新文章

相关课程

相关电子书

【C++初阶：STL —— stack and queue】stack/queue的介绍及使用 | stack/queue/priority_queue的深度剖析及模拟实现 | 适配器模式 | 仿函数上