【十六】【C++】stack的常见用法和练习

stack的常见用法

C++标准库中的stack是一种容器适配器，它提供了后进先出（Last In First Out, LIFO）的数据结构。stack使用一个底层容器进行封装，如deque、vector或list，但只允许从一端（顶部）进行添加或移除元素的操作。stack不提供迭代器，因为它不支持遍历操作。

包含头文件

要使用stack，需要包含头文件<stack>：

#include <stack>

创建stack

创建一个stack实例：

std::stack<int> myStack;

这里创建了一个整数类型的stack。默认情况下，stack使用deque作为其底层容器。

常见操作

push()向栈顶添加一个元素。

pop()移除栈顶元素，不返回被移除的元素。

top()返回栈顶元素的引用，但不移除它。

empty()检查栈是否为空。

size()返回栈中元素的数量。

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;

    // 向栈中添加元素
    stack.push(10);
    stack.push(20);
    stack.push(30);

    // 显示栈顶元素
    std::cout << "Top element: " << stack.top() << std::endl;

    // 移除栈顶元素
    stack.pop();

    // 再次显示栈顶元素
    std::cout << "Top element after pop: " << stack.top() << std::endl;

    // 检查栈是否为空
    if (!stack.empty()) {
        std::cout << "Stack is not empty." << std::endl;
    }

    // 显示栈的大小
    std::cout << "Stack size: " << stack.size() << std::endl;

    return 0;
}

stack的练习

155. 最小栈

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

实现 MinStack 类:

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(31) <= val <= 2(31)1

pop、top 和 getMin 操作总是在 非空栈 上调用

push, pop, top, and getMin最多被调用 3 * 10(4) 次

class MinStack {
public:
    MinStack() {}

    void push(int val) {
        _elem.push(val);
        if (_min.empty() || val <= _min.top()) {
            _min.push(val);
        } else {
            _min.push(_min.top());
        }
    }

    void pop() {
        _min.pop();
        _elem.pop();
    }

    int top() { return _elem.top(); }

    int getMin() { return _min.top(); }

private:
    std::stack<int> _elem;
    std::stack<int> _min;
};

代码思路

我们需要实现每一个时期，都能找到对应的栈内最小的值。那么我们就需要记录每一个时期的栈内最小的值。对于每一个时期我们都可以进行push和pop操作，对应存储的每一个时期的栈内最小值也应该是可以进行push和pop操作。即定义两个栈，一个用来存储每一个时期的栈内元素，一个用来对应不同时期的栈内最小值。

对于每一个元素，每当我们把它入栈，此时我们就更新这个时期对应的栈内最小值，每当我们出栈一个元素，对应的栈内最小值也进行出栈。

代码解析

这段代码定义了一个特殊的栈类MinStack，它能在常数时间内返回栈中的最小元素。为了达到这个目的，MinStack在内部使用了两个标准栈：_elem和_min。_elem栈用于存储所有的元素，而_min栈用于存储每次元素入栈操作后栈中的最小元素。这样，无论何时调用getMin方法，都能立即返回当前栈中的最小元素。

构造函数 MinStack()

构造函数初始化MinStack对象。由于使用的是内置的栈，这里不需要特殊的初始化代码。

方法 void push(int val)

向栈中添加一个元素。这个方法同时更新了两个栈：

_elem栈直接将新元素val压入栈顶。

_min栈的更新逻辑如下：

如果_min为空，或者val小于等于_min的栈顶元素，val也被压入_min栈。这确保了_min的栈顶始终是所有元素中的最小值。

如果val大于_min的栈顶元素，则再次将_min的栈顶元素压入_min栈。这一步是关键，它确保了_min栈的大小和_elem栈的大小始终保持一致，且_min栈顶元素反映了当前栈中的最小值。

方法 void pop()

从栈中移除顶部元素。这个方法同时从两个栈中移除栈顶元素，以保持它们的同步。由于每次push操作都确保了_min和_elem栈的同步，因此在执行pop操作时，两个栈的栈顶元素都可以安全移除，同时保持_min栈顶元素是剩余元素中的最小值。

方法 int top()

返回栈顶元素的值，但不从栈中移除它。这个方法仅查看_elem栈的栈顶元素。

方法 int getMin()

返回栈中的最小元素。由于_min栈的栈顶元素始终是当前所有元素中的最小值，这个方法可以在常数时间内完成。

私有成员

std::stack<int> _elem：用于存储栈中的所有元素。

std::stack<int> _min：用于存储每个状态下栈中的最小元素。

栈的压入、弹出序列_牛客题霸_牛客网

描述

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

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

class Solution {
  public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        if (pushV.size() != popV.size()) {
            return false;
        }

        int pushIndex = 0;
        int popIndex = 0;

        stack<int> s;

        while (popIndex < popV.size()) {
            while (s.empty() || s.top() != popV[popIndex]) {
                if (pushIndex < pushV.size()) {
                    s.push(pushV[pushIndex++]);
                } else {
                    return false;
                }
            }
            s.pop();
            popIndex++;
        }

        return true;
    }
};

代码思路

如果IsPopOrder返回值是true，对于popV中的每一个元素，都必须在栈内pop对应的元素。因此我们需要不断的检测栈顶的元素是否与popV中下标为popIndex的元素是否匹配，如果匹配就对栈进行pop操作，popIndex++。如果不匹配，说明对应的元素还没有入栈，那么pushIndex指向的元素进行入栈操作，接着pushIndex++。继续判断栈顶的元素是否与popV中下标为popIndex的元素是否匹配。

根据这个思路书写代码，需要注意的细节是，我们不断的检测栈顶元素的前提是栈不为空，如果栈为空，对pushIndex元素直接入栈。如果不匹配对pushIndex元素进行入栈操作的前提是pushIndex不越界。

思考如果IsPopOrder返回值是false的情况，对于某一个popIndex元素，在栈内的所有元素都找不到对应的元素，即pushIndex已经越界，依旧不能匹配popIndex元素。

函数参数

vector<int>& pushV：一个整数向量，表示所有元素按顺序入栈的序列。

vector<int>& popV：一个整数向量，表示一个可能的出栈序列。

函数返回值

返回一个布尔值，如果popV是pushV的一个可能的出栈序列，则返回true；否则返回false。

函数逻辑

大小不等判断：首先检查pushV和popV的大小是否相等。如果不相等，则popV不可能是pushV的一个出栈序列，直接返回false。

初始化索引和栈：使用两个整数pushIndex和popIndex分别跟踪pushV和popV的当前索引位置，以及一个stack<int> s来模拟入栈和出栈的过程。

模拟出栈入栈过程：

使用一个外层while循环，条件是popIndex < popV.size()，遍历popV中的每个元素。

对于popV的每个元素，使用一个内层while循环，条件是栈s为空或栈顶元素不等于popV[popIndex]。在这个循环中，如果pushIndex小于pushV.size()，则将pushV[pushIndex]压入栈s并递增pushIndex。如果pushIndex等于pushV.size()但栈顶元素仍不等于popV[popIndex]，说明无法通过合法的栈操作达到popV序列，返回false。

当栈顶元素等于popV[popIndex]时，从栈中弹出该元素并递增popIndex，以匹配popV的下一个待弹出元素。

返回值：如果能够通过上述过程完整遍历popV，说明popV是一个可能的出栈序列，函数返回true。

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。

每个操作数（运算对象）都可以是一个整数或者另一个表达式。

两个整数之间的除法总是 向零截断 。

表达式中不含除零运算。

输入是一个根据逆波兰表示法表示的算术表达式。

答案及所有中间计算结果可以用 32 位 整数表示。

示例 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(4)

tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;

        for (size_t i = 0; i < tokens.size(); i++) {
            string& str = tokens[i];

            if (str != "+" && str != "-" && str != "*" && str != "/") {
                s.push(atoi(str.c_str()));
            } else {
                int right = s.top();
                s.pop();
                int left = s.top();
                s.pop();

                switch (str[0]) {
                case '+':
                    s.push(left + right);
                    break;
                case '-':
                    s.push(left - right);
                    break;
                case '*':
                    s.push(left * right);
                    break;
                case '/':
                    s.push(left / right);
                    break;
                }
            }
        }
        return s.top();
    }
};

逆波兰表达式的计算

逆波兰表达式（Reverse Polish Notation, RPN），也称为后缀表达式，是一种数学表达式的书写方式，在这种表达式中，操作符置于其操作数的后面，如表达式3 4 +等价于中缀表达式3 + 4。逆波兰表达式的一个主要优点是它不需要括号来表示操作的优先级，使得表达式的计算过程变得相对简单直观。

计算逆波兰表达式的步骤

逆波兰表达式的计算通常使用一个栈（Stack）来进行，计算过程遵循以下步骤：

创建一个空栈：用于存储操作数。
从左到右扫描逆波兰表达式：逐个处理表达式中的元素（操作数和操作符）。
处理操作数：如果遇到操作数（数字），就将其压入栈中。
处理操作符：如果遇到操作符，从栈中弹出所需数量的操作数（对于二元操作符是两个，对于一元操作符是一个），对弹出的操作数执行操作，然后将操作结果压入栈中。
重复步骤2-4：直到整个表达式被处理完毕。
得到结果：表达式处理完毕后，栈顶元素即为表达式的结果。

示例

考虑逆波兰表达式5 1 2 + 4 * + 3 -的计算过程：

5：压入栈中，栈中元素为[5]。

1：压入栈中，栈中元素为[5, 1]。

2：压入栈中，栈中元素为[5, 1, 2]。

+：弹出栈顶的两个元素（1和2），计算1+2=3，将结果3压入栈中，栈中元素为[5, 3]。

4：压入栈中，栈中元素为[5, 3, 4]。

*：弹出栈顶的两个元素（3和4），计算3*4=12，将结果12压入栈中，栈中元素为[5, 12]。

+：弹出栈顶的两个元素（5和12），计算5+12=17，将结果17压入栈中，栈中元素为[17]。

3：压入栈中，栈中元素为[17, 3]。

-：弹出栈顶的两个元素（17和3），计算17-3=14，将结果14压入栈中，栈中元素为[14]。

最终，栈顶元素14即为该逆波兰表达式的计算结果。

代码解释

参数

vector<string>& tokens：一个字符串向量，包含了组成逆波兰表达式的数字和操作符。数字以字符串形式表示，操作符包括"+"、"-"、"*"和"/"。

返回值

函数返回逆波兰表达式的计算结果（一个整数）。

函数逻辑

初始化栈：创建一个整数栈s，用于存放中间计算结果和操作数。

遍历表达式：通过一个循环遍历tokens数组的每一个元素（字符串形式的数字或操作符）。

处理操作数：如果当前字符串是一个数字（即不是操作符"+"、"-"、"*"或"/"），则使用atoi函数将字符串转换为整数，并将该整数压入栈s。atoi函数作用的对象是字符数组，也就是字符指针，将字符数组转化为int类型，而str是string类，所以我们需要先把string类转化为字符数组，才能通过atoi函数转化为int类型。string类通过str.c_str()将str字符串类转化为C语言风味的字符串类型，C语言风味的字符串类型也就是字符数组，即字符指针。

处理操作符：如果当前字符串是一个操作符，则从栈中弹出两个元素作为操作数（注意顺序，先弹出的是右操作数，再弹出的是左操作数），根据操作符对这两个操作数执行相应的运算，然后将运算结果压回栈中。

+：执行加法运算。

-：执行减法运算。

*：执行乘法运算。

/：执行除法运算。注意，这里的除法是整数除法。

返回结果：表达式处理完成后，栈顶元素即为整个逆波兰表达式的计算结果，通过s.top()返回。

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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) ，即使其中一个操作可能花费较长时间。

class MyQueue {
private:
    stack<int> inStack, outStack;

    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

代码思路

我们知道栈的特点是先进后出，而队列的特点是先进先出。如何通过栈，先进后出，封装实现队列，先进先出？我们可以想象一堆数，先被我们存放在一个栈里面，尝试把这堆存放在栈里面的数从栈第元素依次抛出。

这样我们就实现了使得一个栈内部分元素，由先进后出转化为了先进先出。但我们需要实时的把数转化为先进先出。意思是同样是1、2、3三个数字，我先依次入队1、2两个元素，接着出队一个元素，再入队3元素，接着出队两个元素。应该如何实现？

类成员解释

私有成员变量：

stack<int> inStack：用于入队操作的栈。

stack<int> outStack：用于出队操作的栈。

私有成员函数：

void in2out()：当需要进行出队操作，但outStack为空时，将inStack中所有元素逆序转移到outStack中。这个过程保证了最早进入inStack的元素位于outStack的顶部，从而可以实现先进先出的队列行为。

公有成员函数

构造函数 MyQueue()：

初始化一个空的MyQueue对象。

入队函数 void push(int x)：

将元素x压入inStack。这个操作对应队列的入队操作。

出队函数 int pop()：

如果outStack为空，则调用in2out函数将inStack中的元素转移到outStack中。

从outStack中弹出顶部元素并返回。这个操作模拟了队列的出队操作。

获取队首元素函数 int peek()：

如果outStack为空，则调用in2out函数将inStack中的元素转移到outStack中。

返回outStack顶部元素但不弹出。这个操作对应队列的获取队首元素操作。

检查队列是否为空 bool empty()：

如果inStack和outStack都为空，则队列为空，返回true；否则，返回false。

工作原理

入队：所有入队操作都通过向inStack压入元素来完成。

出队：出队操作首先检查outStack是否为空。如果outStack为空，则将inStack中的所有元素逆序转移到outStack中，然后从outStack弹出顶部元素。如果outStack不为空，则直接从outStack弹出顶部元素。这个过程确保了最先进入inStack的元素最后被转移到outStack的顶部，从而实现了队列的FIFO特性。