当前位置:   article > 正文

【数据结构—栈】用四道力扣原题帮你彻底搞懂“栈”(详细)_栈的基本运算例题讲解

栈的基本运算例题讲解

目录

1.栈的概念及使用(Stack)

1.1概念

1.2 栈的使用

2.四道栈的相关OJ题

2.1逆波兰表达式求值

2.2括号匹配

2.3验证栈序列

2.4最小栈


1.栈的概念及使用(Stack)

1.1概念

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

出栈:栈的删除操作叫做出栈。出数据在栈顶

栈在现实生活中的例子:

1.2 栈的使用

方法功能

Stack()

构造一个空的栈
E push(E e)将e入栈,并返回e
E pop()将栈顶元素出栈并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()检测栈是否为空
  1. public static void main(String[] args) {
  2. Stack<Integer> s = new Stack();
  3. s.push(1);
  4. s.push(2);
  5. s.push(3);
  6. s.push(4);
  7. System.out.println(s.size()); // 获取栈中有效元素个数---> 4
  8. System.out.println(s.peek()); // 获取栈顶元素---> 4
  9. s.pop(); // 4出栈,栈中剩余1 2 3,栈顶元素为3
  10. System.out.println(s.pop()); // 3出栈,栈中剩余1 2 栈顶元素为3
  11. if(s.empty()){
  12. System.out.println("栈空");
  13. }
  14. else{
  15. System.out.println(s.size());
  16. }
  17. }

2.四道栈的相关OJ题

2.1逆波兰表达式求值

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 <= 104
  • tokens[i] 是一个算符("+""-""*" 或 "/"),或是在范围 [-200, 200] 内的一个整数

逆波兰表达式:

 

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

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

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

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

解题思路:

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下主要操作

如果遇到操作数,则将操作数入栈

如果遇到运算符,则将两个操作数出栈,其中出栈的是操作数出栈的是操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈

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

例如:1 3 + 4 -

按照上图过程,我们可以得出以下Java题解代码

  1. class Solution {
  2. public int evalRPN(String[] tokens) {
  3. Deque<Integer> stack = new LinkedList<Integer>();
  4. int n = tokens.length;
  5. for (int i = 0; i < n; i++) { //遍历字符数组
  6. String token = tokens[i];
  7. if (isNumber(token)) { //判断数组元素是否为操作数
  8. stack.push(Integer.parseInt(token));//是操作数则将其转为int类型
  9. } else { //如果是运算符则进行运算
  10. int num2 = stack.pop();//先弹出一个操作数作为右操作数
  11. int num1 = stack.pop();//后弹出一个操作数作为左操作数
  12. switch (token) { //将运算符与两个操作数进行运算
  13. case "+":
  14. stack.push(num1 + num2);
  15. break;
  16. case "-":
  17. stack.push(num1 - num2);
  18. break;
  19. case "*":
  20. stack.push(num1 * num2);
  21. break;
  22. case "/":
  23. stack.push(num1 / num2);
  24. break;
  25. default:
  26. }
  27. }
  28. }
  29. return stack.pop(); //弹出栈中最后也是唯一一个数,即为答案
  30. }
  31. public boolean isNumber(String token) { //判断是否为操作数
  32. return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
  33. }
  34. }

2.2括号匹配

leetcode原题链接:括号匹配

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

解题思路:

我们可以遍历字符串,遇到左括号就入栈,遇到右括号就与栈顶元素匹配(判断),看是否匹配,如果不匹配则不是有效括号,匹配则弹出栈顶元素(此时消除一对括号)

注意“ )) ”这个用例,我们遇到右括号需要判断栈是否为空,如果栈已经为,此时字符串是右括号也不是有效括号。

因此,我们只需要解决三种情况:

①不匹配 ②左括号多③右括号多

那什么时候才算匹配呢?

当栈当中的元素为空并且字符串也遍历完成的时候

(  i 指的是遍历字符数组时的指向下标)

而考虑到字符串匹配是一对一对的,符号数肯定是偶数,所以我们可以得出以下Java题解代码

  1. class Solution {
  2. public boolean isValid(String s) {
  3. if (s.length() % 2 != 0) {return false;}//字符串匹配是一对一对的,如果是奇数则证明有多余符号
  4. Stack<Character> stack = new Stack<>();
  5. for (int i = 0; i < s.length(); i++) {
  6. char c = s.charAt(i);
  7. if (c == '{' || c == '(' || c == '[') {
  8. stack.push(c);
  9. } else {
  10. if (stack.isEmpty()) {return false;}
  11. if ((c == '}' && stack.peek() == '{')
  12. || (c == ')' && stack.peek() == '(')
  13. || (c == ']' && stack.peek() == '[')) {
  14. stack.pop();
  15. } else {
  16. return false;
  17. }
  18. }
  19. }
  20. return stack.isEmpty();//数组遍历结束后,如果栈中还有多余符号,则匹配失败
  21. }
  22. }

2.3验证栈序列

leetcode原题链接:验证栈序列

给定 pushed 和 popped 两个序列,每个序列中的值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。

示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:

输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。

提示:

  • 1 <= pushed.length <= 1000
  • 0 <= pushed[i] <= 1000
  • pushed 的所有元素互不相同
  • popped.length == pushed.length
  • popped 是 pushed 的一个排列

解题思路:

题目要我们判断两个序列是否符合入栈出栈的次序,我们就可以定义一个辅助栈来模拟,再采用双指针i,j来实现。对于入栈序列,只要栈为空,序列肯定要依次入栈。那什么时候出来呢?自然是遇到一个元素等于当前的出栈序列的元素,那我们就放弃入栈,让它先出来。

1.因为弹出序列是要依据压入序列来判断的,所以首先要遍历压入序列数组;
2.在遍历压入数组时,每次都需要判断当前数值是否是弹出,即比较pushA[i] == popA[j],相同即弹出,不同则将数据压入栈;
3.不断比较,遍历完成后,判断数据是否全部出栈。如果能按照这个次序将两个序列都访问完,那说明是可以匹配入栈出栈次序的。

Java题解代码:

  1. class Solution {
  2. public boolean validateStackSequences(int[] pushed, int[] popped) {
  3. int n = pushed.length;
  4. //辅助栈
  5. Stack<Integer> s = new Stack<>();
  6. //遍历入栈的下标
  7. int j = 0;
  8. //遍历出栈的数组
  9. for(int i = 0; i < n; i++){
  10. //入栈:栈为空或者栈顶不等于出栈数组
  11. while(j < n && (s.isEmpty() || s.peek() != popped[i])){
  12. s.push(pushed[j]);
  13. j++;
  14. }
  15. //栈顶等于出栈数组
  16. if(s.peek() == popped[i])
  17. s.pop();
  18. //不匹配序列
  19. else
  20. return false;
  21. }
  22. return true;
  23. }
  24. }

2.4最小栈

leetcode原题链接:最小栈

设计一个支持 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.

提示:

  • -231 <= val <= 231 - 1
  • poptop 和 getMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

解题思路:

假设一个辅助栈 minStack,用来存stack中的最小值

入栈(push)过程:

出栈(pop)过程:

Java题解代码:

  1. class MinStack {
  2. private Stack<Integer> stack;
  3. private Stack<Integer> minStack;
  4. public MinStack() {
  5. stack=new Stack<>();
  6. minStack =new Stack<>();
  7. }
  8. public void push(int val) {
  9. stack.push(val);
  10. if(minStack.empty()){
  11. minStack.push(val);
  12. }else{
  13. int peekVal=minStack.peek();
  14. //-1<3
  15. if(val<= peekVal){
  16. minStack.push(val);
  17. }
  18. }
  19. }
  20. public void pop() {
  21. int val= stack.pop();
  22. if(!minStack.empty()){
  23. if (val==minStack.peek()){
  24. minStack.pop();
  25. }
  26. }
  27. }
  28. public int top() {
  29. return stack.peek();
  30. }
  31. public int getMin() {
  32. if(!minStack.empty()){
  33. return minStack.peek();
  34. }
  35. return -1;
  36. }
  37. }
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Guff_9hys/article/detail/796242
推荐阅读
相关标签
  

闽ICP备14008679号