从C语言到C++_18(stack和queue的常用函数+相关练习)力扣（下）-阿里云开发者社区

从C语言到C++_18(stack和queue的常用函数+相关练习)力扣（中）：https://developer.aliyun.com/article/1521377

150. 逆波兰表达式求值 - 力扣（LeetCode）

难度中等

给你一个字符串数组 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] 内的一个整数

逆波兰表达式：

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

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

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

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

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

解析代码：

思路：逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，

使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

如果遇到操作数，则将操作数入栈；

如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，

后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

简单来说就是：① 操作数入栈

② 遇到操作符就取栈顶两个操作数运算

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& e: tokens)
        {
            if(e == "+" || e == "-" || e == "*" || e == "/")
            {
                int right = st.top();//右操作数先出栈
                st.pop();
                int left = st.top();
                st.pop();
                
                switch(e[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(e));
            }
        }
        return st.top();
    }
};

这题已经简化了，有可能给你一个中缀表达式：

225. 用队列实现栈 - 力扣（LeetCode）

难度简单

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：

["MyStack", "push", "push", "top", "pop", "empty"]

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

输出：

[null, null, null, 2, 2, false]

解释：

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

提示：

1 <= x <= 9

最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

class MyStack {
public:
    MyStack() {
 
    }
    
    void push(int x) {
 
    }
    
    int pop() {
 
    }
    
    int top() {
 
    }
    
    bool empty() {
 
    }
};
 
/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

解析代码：法一（两个队列）

这道题和下面的栈实现队列，以前都用C语言写过了，但现在我们换个思路

以前的思路：（先入先出转为先入后出）

1.入数据，往不为空的队列入，保持另一个队列为空

2.出数据，依次出队头的数据，转移到另一个队列保存，只剩最后一个时Pop掉

数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)_GR C的博客-CSDN博客

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
 
    MyStack() {
 
    }
    
  void push(int x) {
    q2.push(x); // q2入队列
    while (!q1.empty()) // 把q1的元素全入到q2
    {
      q2.push(q1.front());
      q1.pop();
    }
    swap(q1, q2); // 交换q1和q2
  }
    
  int pop() {
    int r = q1.front();
    q1.pop();
    return r;
  }
    
    int top() {
        //题目要求int top() 返回栈顶元素。（队列尾）队列不能删尾，能取尾
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
};

解析代码：法二（一个队列）

使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。

入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。

由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

class MyStack {
public:
    queue<int> q;
 
    MyStack() {
 
    }
    
  void push(int x) {
    q.push(x);
        int n = q.size() - 1;
        while(n--)
        {
            q.push(q.front());
            q.pop();
        }
  }
    
  int pop() {
    int r = q.front();
    q.pop();
    return r;
  }
    
    int top() {
        //题目要求int top() 返回栈顶元素。（队列尾）队列不能删尾，能取尾
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
};

232. 用栈实现队列 - 力扣（LeetCode）

难度简单

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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 {
public:
    MyQueue() {
 
    }
    
    void push(int x) {
 
    }
    
    int pop() {
 
    }
    
    int peek() {
 
    }
    
    bool empty() {
 
    }
};
 
/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

解析代码：

class MyQueue {
public:
    stack<int> inStack, outStack;
 
    MyQueue() {
 
    }
    
    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        if (outStack.empty())
        {
            while (!inStack.empty()) 
            {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }
    
    int peek() {
        if (outStack.empty()) 
        {
            while (!inStack.empty()) 
            {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        return outStack.top();
    }
    
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

本章完。

下一部分先讲讲STL六大组件之一的容器适配器和双端队列deque和优先级队列priority_queue，再模拟实现stack和queue，最后模拟实现优先级队列priority_queue，

从C语言到C++_18(stack和queue的常用函数+相关练习)力扣（下）

150. 逆波兰表达式求值 - 力扣（LeetCode）

解析代码：

225. 用队列实现栈 - 力扣（LeetCode）

解析代码：法一（两个队列）

解析代码：法二（一个队列）

232. 用栈实现队列 - 力扣（LeetCode）

解析代码：

本章完。

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

从C语言到C++_18(stack和queue的常用函数+相关练习)力扣（下）

解析代码：

解析代码：法一（两个队列）

解析代码：法二（一个队列）

解析代码：

本章完。

热门文章

最新文章

相关课程

相关电子书