从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,