devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之探索“栈”的奥秘

作者：我家自动化 | 2024-07-21 05:55:12

赞

踩

数据结构之探索“栈”的奥秘

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

目录

栈的有关概念

栈的使用 

栈的模拟实现

栈的应用场景

改变元素的序列

将递归转化为循环 

栈的相关刷题 

20. 有效的括号

150. 逆波兰表达式求值

牛客网——JZ31 栈的压入、弹出序列

155. 最小栈

栈的有关概念

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

压栈：栈的插入操作叫做进栈/压栈/入栈。 出栈：栈的删除操作叫做出栈。

下面是栈以及其有关操作的图示：

栈的使用 

栈的基本方法
方法功能
Stack()构造一个空的栈
E push(E e)将e入栈，并返回e
E pop()得到并删除栈顶元素
E peek()获取栈顶元素
int size()获取栈中有效元素的个数
boolean empty()检测栈是否为空

下面是上面方法的使用：

  1. public class Test {
  2.     public static void main(String[] args) {
  3.         // 构造方法：构造一个空栈
  4.         Stack<Integer> stack = new Stack<>();
  5.         // 判断栈是否为空
  6.         System.out.println(stack.empty());
  7.         // 开始往栈区增加元素：压栈/入栈
  8.         stack.push(1);
  9.         stack.push(2);
  10.         stack.push(3);
  11.         stack.push(4);
  12.         stack.push(5);
  13.         // 获取栈顶元素
  14.         System.out.println(stack.peek());
  15.         // 得到并删除栈顶元素
  16.         System.out.println(stack.pop());
  17.         // 获取栈中有效的元素个数
  18.         int size = stack.size();
  19.         System.out.println(size);
  20.         // 开始利用pop方法遍历栈
  21.         for (int i = 0; i < size; i++) {
  22.             // 得到并删除栈顶元素
  23.             System.out.println(stack.pop());
  24.         }
  25.         // 判断栈是否为空
  26.         System.out.println(stack.empty());
  27.     }
  28. }

运行结果：

栈的模拟实现

模拟栈，就只需要实现模拟我们上面使用的那几种方法即可。

下面是用数组模拟栈的实现：

  1. // 用数组模拟实现栈
  2. public class MyStack {
  3.    public int[] elem;
  4.    public int usedSzie;
  5.  
  6.    public MyStack() {
  7.        // 为了方便测试给三个空间
  8.        this.elem = new int[3];
  9.    }
  10.  
  11.    // 入栈
  12.    public boolean push(int val) {
  13.        // 先判断栈空间是否满了
  14.        if (this.usedSzie == this.elem.length) {
  15.            return false;
  16.        }
  17.        this.elem[(this.usedSzie)++] = val;
  18.        return true;
  19.    }
  20.  
  21.    // 出栈
  22.    public int pop() throws StackIsEmptyException {
  23.        // 先判断栈是否为空
  24.        if (empty()) {
  25.            throw new StackIsEmptyException("栈为空异常!");
  26.        } else {
  27.           this.usedSzie--;
  28.           return this.elem[this.usedSzie];
  29.        }
  30.    }
  31.  
  32.    // 获取栈顶元素
  33.    public int peek() {
  34.        // 先判断栈是否为空
  35.        if (empty()) {
  36.            throw new StackIsEmptyException("栈为空异常!");
  37.        } else {
  38.            return this.elem[this.usedSzie-1];
  39.        }
  40.    }
  41.  
  42.    public int size() {
  43.        return this.usedSzie;
  44.    }
  45.  
  46.    public boolean empty() {
  47.        return this.usedSzie == 0;
  48.    }
  49. }

异常代码：

  1. public class MyStackIsEmptyException extends RuntimeException {
  2.     public MyStackIsEmptyException(String msg) {
  3.         super(msg);
  4.     }
  5.     public MyStackIsEmptyException() {
  6.         super();
  7.     }
  8. }

除了用数组之外，还可以用链表来模拟实现：

  1. // 用链表来模拟实现栈
  2. public class MyStack {
  3.     public LinkedList<Integer> linkedList;
  4.  
  5.     public MyStack () {
  6.         this.linkedList = new LinkedList<>();
  7.     }
  8.  
  9.     // 入栈
  10.     public void push(int val) {
  11.         // 直接尾插就行
  12.         this.linkedList.addLast(val);
  13.     }
  14.  
  15.     // 出栈
  16.     public int pop() throws MyStackIsEmptyException {
  17.         // 先判断链表是否为空
  18.         if (empty()) {
  19.             throw new MyStackIsEmptyException("栈为空异常！");
  20.         }
  21.         // 移除最后一个节点
  22.         int ret = this.linkedList.getLast(); // 得到最后一个元素
  23.         this.linkedList.removeLast();
  24.         return ret;
  25.     }
  26.  
  27.     // 获取栈顶元素
  28.     public int peek() throws MyStackIsEmptyException {
  29.         // 先判断链表是否为空
  30.         if (empty()) {
  31.             throw new MyStackIsEmptyException("栈为空异常！");
  32.         }
  33.         return this.linkedList.getLast();
  34.     }
  35.  
  36.     public int size() {
  37.         return this.linkedList.size();
  38.     }
  39.  
  40.     public boolean empty() {
  41.         return this.linkedList.size() == 0;
  42.     }
  43. }

当然，这里的链表没有自己实现，而是用的Java自身提供的。那么也意味着上面的数组实现，可以用顺序表来模拟，也是一样的。 

栈的应用场景

改变元素的序列

例1： 

我们知道栈要遵循一个规律：先进后出，后进先出。那么只要 先进去的 在 后进去的 前面出来，则肯定是错误的。

A选项，正确。当1进去栈，接着再出来，后面的接着全部进去，再一个一个的出来，那么结果就是 1、4、3、2。

B选项，正确。1进去，接着2进去，再出来，一直循环这个过程到全部元素进去，最后1再出来，那么结果就是2、3、4、1。 

C选项，错误。3 要出来，说明1 和 2肯定已经进去了。既然3出去了，栈中就只有1和2了，并且2在栈顶，那么就不可能出现1 比 2先出去的情况。

D选项，正确。3 要出来，肯定 1 和 2 进去了。接着 4再进去、出来。最后就是2 出来，1出来。那么结果就是3、4、2、1。

例2：

这个答案就很明显了是B。

将递归转化为循环 

例如：逆序打印单链表。

正常打印单链表是从头节点开始一直遍历到 null 就停下。但是现在要逆序打印，就是从尾节点开始打印这个单链表。

方式一，递归：

  1.     // 逆序打印节点的值
  2.     public void printList(ListNode head) {
  3.         //if (head == null) {
  4.         //    // 抛异常
  5.         //}
  6.         // 找到尾节点就停止
  7.         if (head.next != null) {
  8.             printList(head.next);
  9.         }
  10.         System.out.print(head.val+" ");
  11.     }

方式二，栈：

要逆序打印单链表，就是从尾节点开始打印，而尾节点是后面进来的。即后面来的先打印，前面的后打印。这个就可以用栈来实现。

  1.     public void printList(ListNode head) {
  2.         /*if (head == null) {
  3.             // 抛异常
  4.         }*/
  5.         // 创建一个栈
  6.         Stack<Integer> stack = new Stack<>();
  7.         // 遍历链表，把链表的节点放到栈中
  8.         while (head != null) {
  9.             stack.push(head.val);
  10.             head = head.next;
  11.         }
  12.         // 开始用栈来打印
  13.         while (!stack.empty()) {
  14.             System.out.print(stack.pop()+" ");
  15.         }
  16.     }

栈的相关刷题 

20. 有效的括号

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

有效字符串需满足：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

括号不匹配有三种情况：

1、左括号比右括号多

2、右括号比左括号多

3、左右括号不匹配 

当我们去遍历这个字符串时，会发现一个规律：后遇到的左括号 会比 前遇到的左括号 先匹配。

思路： 先遇到的左括号储存到栈中，直至遇到了右括号，再将栈顶元素拿出来和这个右括号进行匹配，看看是否成功。 成功就继续往后走，失败则返回false。直至遍历完成或者栈为空（右括号多于左括号）。

  1. class Solution {
  2.     public boolean isValid(String s) {
  3.         // 创建一个栈
  4.         Stack<Character>  stack = new Stack<>();
  5.         // 遍历字符串
  6.         for (int i = 0; i < s.length(); i++) {
  7.             char ch = s.charAt(i);
  8.             // 如果遇到左括号就入栈，如果遇到右括号就出栈
  9.             if (ch == '(' || ch == '{' || ch == '[') {
  10.                 stack.push(ch);
  11.             }else {
  12.                 // 出栈匹配
  13.                 // 判断栈是否为空
  14.                 if (stack.empty()) {
  15.                     return false;
  16.                 } else {
  17.                     // 开始匹配
  18.                     char x = stack.pop();
  19.                     // 如果匹配说明符合要求，继续往后走
  20.                     if (x == '(' && ch == ')') {
  21.                         continue;
  22.                     } else if (x == '[' && ch == ']') {
  23.                         continue;
  24.                     } else if (x == '{' && ch == '}') {
  25.                         continue;
  26.                     } else {
  27.                         return false;
  28.                     } 
  29.                 }
  30.             }
  31.         }
  32.         // 判断栈是否为空
  33.         if (stack.empty()) {
  34.             // 栈为空说明全部匹配成功了
  35.             return true;
  36.         } else {
  37.             // 还有括号没有匹配
  38.             return false;
  39.         } 
  40.     }
  41. }

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

逆波兰表达式（也称为后缀表达式）的计算通常与栈密切相关，因为栈能够非常自然地处理这种后进先出的操作顺序。不过，理论上讲，不使用栈也可以实现逆波兰表达式的计算，但可能需要更复杂的逻辑和额外的数据结构来模拟栈的功能。

思路：用栈来实现逆波兰表达式。遍历字符串数组，当遇到数字，则入栈；遇到运算符，则将栈顶的元素弹出作为右操作数，再将栈顶的元素弹出作为左操作数，计算完的值再入栈。

  1. class Solution {
  2.     public int evalRPN(String[] tokens) {
  3.         Stack<String> stack = new Stack<>();
  4.         // 遍历字符串数组
  5.         for (int i = 0; i < tokens.length; i++) {
  6.             // 判断这个字符串是否为数字
  7.             // 数字难判断，但运算符很简单，因此可以转换角度来判断运算符
  8.             if (!isOperator(tokens[i])) {
  9.                 // 是数字就入栈
  10.                 stack.push(tokens[i]);
  11.             } else {
  12.                 // 开始运算
  13.                 int y = Integer.parseInt(stack.pop()); // 右操作数
  14.                 int x = Integer.parseInt(stack.pop()); // 左操作数 
  15.                 int result = 0;
  16.                 switch (tokens[i]) {
  17.                     case "+" :
  18.                         result = x+y;
  19.                         break;
  20.                     case "-" :
  21.                         result = x-y;
  22.                         break;
  23.                     case "*" :
  24.                         result = x*y;
  25.                         break;
  26.                     case "/" :
  27.                         result = x/y;
  28.                         break;
  29.                 }
  30.                 // 运算完的结果返回到栈中
  31.                 Integer j = result;
  32.                 stack.push(j.toString());
  33.             }
  34.         }
  35.         // 返回栈中最后剩余的元素
  36.         return Integer.parseInt(stack.pop());
  37.     }
  38.     private boolean isOperator(String s) {
  39.         // 如果不是+、-、*、/，那就是数字字符
  40.         return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
  41.     }
  42. }

注意：我们平常写的运算表达式是属于中缀表达式，即运算符在两个运算数的中间位置，还有前缀表达式和后缀表达式。我们这里的逆波兰表达式就是后缀表达式，即运算符在两个运算数的后面，而前缀表达式就是在两个运算数的前面，也称为波兰表达式。

下面是中缀表达式转后缀表达式的详细过程：

9+(3-1) * 3+8 / 2，这个就是我们平常写的表达式。

转换成后缀表达式：
1、将所有的运算符与运算数之间加上（）。即：((9+((3-1) * 3))+(8 / 2))
2、将所有的运算符提到本级括号的外边去。即：((9((3 1)-  3)*)+(8 2) / )+
3、最后将所有的括号全部去掉，就是后缀表达式。即：9 3 1 -  3 * + 8 2 / +

按照栈的特点去计算这个表达式的过程如下： 

牛客网——JZ31 栈的压入、弹出序列

描述

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

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. 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

思路：模拟第一个数组入栈出栈时的样子，与第二个数组对比，看结果是否一致。

  1. public boolean IsPopOrder (int[] pushV, int[] popV) {
  2.         Stack<Integer> stack = new Stack<>();
  3.         int j = 0;
  4.         // 将第一个数组入栈，与第二个数组进行对比，看是否一致
  5.         for (int i = 0; i < pushV.length; i++) {
  6.             int x = stack.push(pushV[i]);
  7.             if (x != popV[j]) {
  8.                 continue;
  9.             } else {
  10.                 // 一致就继续往后比较，直至栈为空
  11.                 while (!stack.empty()) {
  12.                     if (stack.peek() == popV[j]) {
  13.                         stack.pop();
  14.                         j++;
  15.                     } else {
  16.                         break;
  17.                     }
  18.                 }
  19.             } 
  20.         }
  21.         if (stack.empty()) {
  22.             return true;
  23.         }
  24.         return false;
  25.     }

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.

提示：

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

思路：既想要保持原数据不变，又要时刻维护最小数据，一个栈肯定是做不到的，要两个栈，一个普通栈，来存储元素，一个最小栈，来维护最小元素。

  1. class MinStack {
  2.  
  3.     Stack<Integer> stack; // 普通栈
  4.     Stack<Integer> minStack; // 最小栈
  5.  
  6.     public MinStack() {
  7.        stack = new Stack<>(); // 普通栈
  8.        minStack = new Stack<>(); // 最小栈
  9.     }
  10.     
  11.     public void push(int val) {
  12.         // 首先得判断这个最小栈中是否有元素。
  13.         // 如果啥也没有，那么第一个元素肯定是要入栈的
  14.         // 因为第一个元素肯定既是最大的，也是最小的
  15.         if (minStack.empty()) {
  16.             minStack.push(val);
  17.         } else {
  18.             if (minStack.peek() >= val) {
  19.                 minStack.push(val);
  20.             }
  21.         }
  22.         // 普通栈就无需判断
  23.         stack.push(val);
  24.     }
  25.     
  26.     public void pop() {
  27.         // 这里虽然删除的是普通栈的栈顶元素，
  28.         // 但是如果普通栈的栈顶元素和最小栈一样，
  29.         // 那么两者都得删除
  30.     
  31.         // 注意：这里的比较要用 equals，下面有解释
  32.         if (stack.peek().equals(minStack.peek())) {
  33.             stack.pop();
  34.             minStack.pop();
  35.         } else {
  36.             stack.pop();
  37.         }
  38.     }
  39.     
  40.     public int top() {
  41.         // 这里拿的是普通栈的栈顶元素
  42.         return stack.peek();
  43.     }
  44.     
  45.     public int getMin() {
  46.         // 这里拿的是最小栈的栈顶元素
  47.         return minStack.peek();
  48.     }
  49. }

注意：

1、这里题目明确的说了   pop、top 和 getMin 操作总是在 非空栈 上调用 。

2、这里的比较之所以要用 equals() 方法，是因为当 LeetCode 给的测试用例不在 -128~127 之间时，会分配两个不同的对象。如果我们用 == 去比较的话，肯定是 false ，因此就只有两种解决方法：1、用 equals() 方法进行比较；2、将一方进行拆包的操作之后，再去比较两者之间的关系。

下面这篇文章就讲述了 第二点中的来源：同一个数字，但不同的对象

以上就是关于栈的经典题型了。总体难度虽然用栈来解决不是很大，但是要想到用栈的知识去解决，还是挺难的。所以栈的基本知识不能，但做题想到用栈解决就很难了。

好啦！本期  数据结构之栈  的学习之旅就到此结束了！相信通过这篇文章的学习，你对栈的了解将会更进一步！我们下一期再一起学习吧！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/859769
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号