当前位置：首页 > news >正文

数据结构之栈

news 2025/7/1 9:00:57

系列文章目录

数据结构之ArrayList-CSDN博客

数据结构之LinkedList-CSDN博客

系列文章目录

前言

一、栈的常用方法

二、栈的模拟实现

三、栈的应用场景

1. 将递归转化为循环，例如链表的逆序打印：

2. 括号匹配

3. 逆波兰表达式

4. 判断栈的序列

5. 模拟实现最小栈

四、虚拟机栈，栈，栈帧的区别

前言

本文介绍了栈的常用方法，栈的模拟实现以及栈的典型应用场景。

一、栈的常用方法

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除操作。先进栈的元素后出栈，后进栈的元素先出栈。常用方法如下：

Stack(): 构造方法；

push(E): E 在栈顶新增一个元素；

pop(): E 取出栈顶元素；

peek(): E 看一下栈顶元素；

empty() 判断栈是否为空；

size(): int 返回栈中元素的个数；

二、栈的模拟实现

栈的底层是一个数组，与顺序表的实现方法类似。

import java.util.Arrays;public class MyStack {private int[] elem;private int usedSize;private static final int DEFAULT_CAPACITY = 10;public MyStack(){this.elem = new int[DEFAULT_CAPACITY];}public void push(int val){if(isFull()){this.elem = Arrays.copyOf(this.elem, this.elem.length * 2);}this.elem[usedSize++] = val;}private boolean isFull(){return this.usedSize == this.elem.length;}public int pop(){if(isEmpty()) {throw new RuntimeException("栈为空");}this.usedSize--;return this.elem[usedSize];}public boolean isEmpty(){return this.usedSize == 0;}public int peek(){return this.elem[usedSize - 1];}public int size(){return this.usedSize;}
}

三、栈的应用场景

1. 将递归转化为循环，例如链表的逆序打印：

递归方式：

    public void reversePrint(ListNode head){if(head != null){reversePrint(head.next);System.out.print(head.val + " ");}}

栈方式：

    public void reversePrintByStack(ListNode head){ListNode cur = head;Stack<ListNode> stack = new Stack<>();while(cur != null){stack.push(cur);cur = cur.next;}while(!stack.isEmpty()){ListNode top = stack.pop();System.out.print(top.val + " ");}System.out.println();}

2. 括号匹配

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

有效字符串需满足：

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

    public boolean isValid(String s) {char[] sArr = s.toCharArray();Stack<Character> stack = new Stack<>();for(char ch : sArr){if(ch == '(' || ch == '[' || ch == '{'){stack.push(ch);}else{if(stack.isEmpty()) return false;else{char c = stack.pop();if((c == '(' && ch != ')') || (c == '[' && ch != ']') || (c == '{' && ch != '}')) {return false;}}}}return stack.isEmpty();}

3. 逆波兰表达式

以如下表达式为例：

中缀表达式，即符合我们习惯的表达式，例如：a + b * c + (d * e + f) * g

后缀表达式，即逆波兰表达式，计算机实际运算时采用的表达式，是没有括号的；

中缀表达式转后缀表达式的方法：

先按照运算顺序加括号，例如：((a + (b * c)) + (((d * e) + f) * g))；

再将运算符移到括号后面，去掉所有括号，例如：a b c * + d e * f + g * +；

计算后缀表达式：遍历后续表达式

遇到数字：加入到栈中；

遇到运算符：以 * 为例，弹出栈顶元素存到 right 中，再弹出栈顶元素存到 left 中，运算 left * right，将计算的结果再存到栈中；

最终栈中存的元素就是表达式的结果；

    public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String s : tokens){if("+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s)){int right = stack.pop();int left = stack.pop();switch(s){case "+":{stack.push(left + right); break;}case "-":{stack.push(left - right); break;}case "*":{stack.push(left * right); break;}case "/":{stack.push(left / right); break;}}}else{int t = Integer.parseInt(s);stack.push(t);}}return stack.peek();}

4. 判断栈的序列

描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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 的所有数字均不相同

    public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int n = pushV.length;int j = 0;for(int i = 0; i < n; i++){stack.push(pushV[i]);while(!stack.isEmpty() && popV[j] == stack.peek()){stack.pop();j++;}}return stack.isEmpty();}

5. 模拟实现最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内（O(1)时间复杂度）检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.isEmpty()){minStack.push(val);}else{int top = minStack.peek();if(top >= val){minStack.push(val);}}}public void pop() {int val = 0;if(!stack.isEmpty()){val = stack.pop();if(minStack.peek() == val){minStack.pop();}}}public int top() {if(stack.isEmpty()){return -1;}return stack.peek();}public int getMin() {if(minStack.isEmpty()){return -1;}return minStack.peek();}
}