| 深入理解Java中的栈（超详细）新手必看 | 您所在的位置：网站首页 › 计算机中的栈是啥 › 深入理解Java中的栈（超详细）新手必看 |
深入理解Java中的栈（超详细）新手必看
|
目录 一、什么是栈？ 二、Java中的栈帧 三、栈的应用 四、栈的基本方法 五、栈的几种实现方式 1、基于简单数组的实现方式： 2、基于动态数组的实现方式： 3、基于链表的实现方式： 基于数组实现和基于链表实现的比较 （1）基于数组实现的栈： （2）基于链表实现的栈： 4、基于队列的实现方式： 六、双端栈 1、定义 2、特点 3、示例 七、关于栈的习题应用 1、括号匹配 2、逆波兰表达式求值 3、表达式求值 4、函数调用堆栈 5、汉诺塔问题 6、迷宫求解 引言： 在Java编程语言中，栈（Stack）是一种非常重要的数据结构，它在方法调用和变量存储中扮演着关键的角色。了解Java中的栈对于程序员来说至关重要，本篇博客将详细介绍Java中的栈的知识，并结合一些例子来帮助读者更好地理解。 一、什么是栈？栈（Stack）是一种常见的数据结构，具有后进先出（LIFO，Last In First Out）的特性，即最后入栈的元素最先出栈。栈通常用于存储临时性的数据，如方法调用过程中的局部变量、操作数栈等。在计算机科学中，栈的应用非常广泛，包括编程语言中的函数调用、内存分配以及表达式求值等领域。在Java编程语言中，栈也被广泛应用于方法调用和内存管理的过程中。
在Java虚拟机（JVM）中，每个方法在运行时都会创建一个对应的栈帧（Stack Frame），栈帧用于存储方法的局部变量、操作数栈、动态链接、返回地址等信息。 栈帧的结构如下： 局部变量表（Local Variable Table）：局部变量表用于存储方法参数和方法内部定义的局部变量。局部变量表中的每个槽位可以存储一个基本类型的值或对象引用。在方法调用时，参数和本地变量的值会被压入局部变量表；在方法执行期间，可以通过索引来访问局部变量表中的值。 操作数栈（Operand Stack）：操作数栈是用于执行方法时进行计算的临时数据存储区域。操作数栈的元素可以是任意的Java数据类型，包括基本类型和对象引用。在方法执行过程中，操作数栈用于存储方法执行过程中的计算结果、方法参数以及临时变量等数据。 动态链接（Dynamic Linking）：动态链接指向运行时常量池中该方法的符号引用的指针。在Java中，动态链接主要用于解析方法调用的目标地址，以便在运行时能够正确调用方法。 方法返回地址：方法返回地址是指向方法调用者的指令地址。当方法执行完毕后，JVM会使用返回地址恢复执行方法调用者的指令。 栈帧的创建和销毁是在方法调用和返回过程中自动进行的。每当发生方法调用时，JVM会为该方法创建一个新的栈帧并将其推入调用栈（Call Stack），当方法返回时，对应的栈帧会被销毁，栈顶指针会回到前一个方法的栈帧。栈帧的动态创建和销毁确保了方法的独立性和互相调用的正确性。 三、栈的应用 符号匹配HTML和XML文件中的标签匹配（实质还是符号匹配）实现函数调用文本编辑器中的撤销网页浏览器中已访问页面的历史记录作为一个算法的辅助数据结构 四、栈的基本方法 push(Object item)：将元素item压入栈顶。pop()：弹出栈顶元素，并将其从栈中删除。peek()：返回栈顶元素，但不删除它。isEmpty()：判断栈是否为空，返回布尔值。search(Object item)：搜索元素item在栈中的位置（从栈顶开始），如果找到则返回其距离栈顶的位置（栈顶为1），如果未找到则返回-1。clear()：对当前栈进行清空。下面是一个示例代码，演示了如何使用Stack类进行栈的基本操作： import java.util.Stack; public class StackExample { public static void main(String[] args) { Stack stack = new Stack(); // 压入元素到栈中 stack.push(10); stack.push(20); stack.push(30); // 弹出栈顶元素，并删除 int poppedElement = stack.pop(); System.out.println("Popped element: " + poppedElement); // 查看栈顶元素，但不删除 int peekedElement = stack.peek(); System.out.println("Peeked element: " + peekedElement); // 判断栈是否为空 boolean empty = stack.isEmpty(); System.out.println("Is the stack empty? " + empty); // 搜索元素在栈中的位置 int position = stack.search(20); System.out.println("Position of 20 in the stack: " + position); } }执行以上代码，输出结果为： Popped element: 30 Peeked element: 20 Is the stack empty? false Position of 20 in the stack: 2通过使用Stack类提供的基本方法，我们可以方便地对栈进行操作，包括压入、弹出、查看栈顶元素、判断栈是否为空以及搜索元素在栈中的位置。 五、栈的几种实现方式 1、基于简单数组的实现方式：
使用简单数组作为底层数据结构来实现栈，通过将栈顶元素的索引存储在变量中，实现压栈和弹栈操作，每次压栈时将元素添加到数组末尾，每次弹栈时将栈顶元素从数组中删除。由于数组的长度是固定的，需要提前定义栈的最大容量。 示例： public class ArrayStack { private int[] stack; private int top; public ArrayStack(int capacity) { stack = new int[capacity]; top = -1; } public void push(int item) { if (top == stack.length - 1) { throw new IllegalStateException("Stack is full"); } stack[++top] = item; } public int pop() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return stack[top--]; } public int peek() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return stack[top]; } public boolean isEmpty() { return top == -1; } } 2、基于动态数组的实现方式：使用动态数组（如ArrayList）作为底层数据结构来实现栈，通过在动态数组的尾部进行插入和删除操作来实现栈的功能。当栈容量不足时，动态数组可以自动进行扩容，当栈元素减少时，动态数组可以自动进行缩容。这种实现方式提供了动态调整容量的特性。 示例： import java.util.ArrayList; public class DynamicArrayStack { private ArrayList stack; public DynamicArrayStack() { stack = new ArrayList(); } public void push(int item) { stack.add(item); } public int pop() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return stack.remove(stack.size() - 1); } public int peek() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return stack.get(stack.size() - 1); } public boolean isEmpty() { return stack.isEmpty(); } } 3、基于链表的实现方式：使用链表作为底层数据结构来实现栈，链表的头部或尾部作为栈顶，每次插入和删除操作都在链表的头部进行，通过修改引用来实现栈的操作。链表实现的栈可以动态增加和缩小容量，不需要提前定义栈的最大容量，但相对于数组实现，需要更多的空间开销。 示例： public class LinkedListStack { private Node top; private class Node { int data; Node next; public Node(int data) { this.data = data; this.next = null; } } public LinkedListStack() { top = null; } public void push(int item) { Node newNode = new Node(item); if (isEmpty()) { top = newNode; } else { newNode.next = top; top = newNode; } } public int pop() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } int item = top.data; top = top.next; return item; } public int peek() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return top.data; } public boolean isEmpty() { return top == null; } } 基于数组实现和基于链表实现的比较 （1）基于数组实现的栈： 各个操作都是常数时间开销每隔一段时间进行的倍增操作的时间开销较大 （2）基于链表实现的栈： 栈规模的增加和减小都很容易各个操作都是常数时间开销每个操作都需要使用额外的空间和时间开销来处理指针 4、基于队列的实现方式：使用队列作为底层数据结构来实现栈，可以使用两个队列来模拟栈的操作。当压栈时，将元素添加到非空队列中；当弹栈时，将非空队列中的元素依次弹出并放入另一个空队列中，直到剩下最后一个元素，即栈顶元素，然后弹出。这种实现方式可以保持栈顶元素总是在队列的尾部，模拟了栈的后进先出（LIFO）特性。 示例： import java.util.LinkedList; import java.util.Queue; public class QueueBasedStack { private Queue queue1; private Queue queue2; private int top; public QueueBasedStack() { queue1 = new LinkedList(); queue2 = new LinkedList(); } public void push(int item) { queue1.add(item); top = item; } public int pop() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } while (queue1.size() > 1) { top = queue1.remove(); queue2.add(top); } int item = queue1.remove(); Queue tempQueue = queue1; queue1 = queue2; queue2 = tempQueue; return item; } public int peek() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return top; } public boolean isEmpty() { return queue1.isEmpty(); } } 六、双端栈 1、定义双端栈（Double Ended Stack），也被称为双端队列（Deque），是一种支持在两端进行插入和删除操作的数据结构。它可以在栈顶和栈底执行压栈和弹栈操作，因此既能模拟栈的后进先出（LIFO）特性，又可以模拟队列的先进先出（FIFO）特性。
双端栈是线性表的一种,更是栈的一个特殊分类，可用借用动态数组+栈的组合实现。
双端栈的特点是可以从两个方向进行操作，即从左侧插入和删除元素，也可以从右侧插入和删除元素。这使得双端栈在某些场景下可以提供更灵活的操作和更高的效率。 3、示例下面是一个使用Java的Deque实现双端栈的示例代码： import java.util.ArrayDeque; import java.util.Deque; public class DequeStack { private Deque deque; public DequeStack() { deque = new ArrayDeque(); } public void push(int item) { deque.push(item); } public int pop() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return deque.pop(); } public int peek() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return deque.peek(); } public boolean isEmpty() { return deque.isEmpty(); } public int size() { return deque.size(); } }在这个示例中，我们使用了Java的Deque，具体是ArrayDeque实现类。ArrayDeque是基于可调整大小的数组实现的双端队列，可以在队列的两端进行插入和删除操作。我们将其作为双端栈的底层数据结构来实现。 通过双端栈，我们可以在栈顶和栈底进行元素的插入和删除操作。例如： DequeStack stack = new DequeStack(); stack.push(1); stack.push(2); System.out.println(stack.peek()); // 输出：2 stack.push(3); stack.push(4); System.out.println(stack.pop()); // 输出：4 stack.push(5); System.out.println(stack.pop()); // 输出：5 System.out.println(stack.pop()); // 输出：3 System.out.println(stack.pop()); // 输出：2 System.out.println(stack.isEmpty()); // 输出：true在这个例子中，我们将元素依次压栈，并使用peek方法查看栈顶元素。随后，我们连续进行了三次弹栈操作，可以看到栈的后进先出特性。最后，我们通过isEmpty方法验证栈是否为空。 通过双端栈，我们可以自由地在栈顶和栈底进行操作，根据具体的需求实现不同的功能。 七、关于栈的习题应用 1、括号匹配给定一个包含括号字符的字符串，判断括号是否匹配，例如 “((()))” 是匹配的，而 “(()” 则不匹配。可以使用栈来实现括号匹配的算法。 import java.util.Stack; public class BracketMatching { public static boolean isBracketMatch(String input) { Stack stack = new Stack(); for (int i = 0; i < input.length(); i++) { char ch = input.charAt(i); if (ch == '(' || ch == '[' || ch == '{') { stack.push(ch); } else if (ch == ')' || ch == ']' || ch == '}') { if (stack.isEmpty()) { return false; } char top = stack.pop(); if ((ch == ')' && top != '(') || (ch == ']' && top != '[') || (ch == '}' && top != '{')) { return false; } } } return stack.isEmpty(); } public static void main(String[] args) { String input1 = "((()))"; String input2 = "(()"; System.out.println(input1 + " is matched: " + isBracketMatch(input1)); System.out.println(input2 + " is matched: " + isBracketMatch(input2)); } }在上面的示例代码中，我们定义了一个isBracketMatch方法来判断输入的字符串中的括号是否匹配。我们使用一个Stack来存储左括号，遍历输入字符串，遇到左括号就入栈，遇到右括号就出栈并匹配。最后检查栈是否为空来判断括号是否完全匹配。 在main方法中我们则可以测试该方法的使用，可以看到input1是匹配的，而input2则不匹配。 2、逆波兰表达式求值给定一个逆波兰表达式，计算其值。逆波兰表达式是一种通过后缀表达式来进行计算的算法，可以使用栈来实现逆波兰表达式的求值。 import java.util.Stack; public class ReversePolishNotation { public static int evalRPN(String[] tokens) { Stack stack = new Stack(); for (String token : tokens) { if (token.equals("+")) { int operand2 = stack.pop(); int operand1 = stack.pop(); stack.push(operand1 + operand2); } else if (token.equals("-")) { int operand2 = stack.pop(); int operand1 = stack.pop(); stack.push(operand1 - operand2); } else if (token.equals("*")) { int operand2 = stack.pop(); int operand1 = stack.pop(); stack.push(operand1 * operand2); } else if (token.equals("/")) { int operand2 = stack.pop(); int operand1 = stack.pop(); stack.push(operand1 / operand2); } else { stack.push(Integer.parseInt(token)); } } return stack.pop(); } public static void main(String[] args) { String[] tokens = {"2", "1", "+", "3", "*"}; System.out.println("逆波兰表达式的值为: " + evalRPN(tokens)); // 输出：9 } }在以上示例代码中，我们定义了一个evalRPN方法，用于计算给定的逆波兰表达式的值。我们使用一个Stack来存储操作数，遍历逆波兰表达式，当遇到操作数时入栈，当遇到运算符时从栈中弹出相应数量的操作数进行计算后将结果入栈。最终栈中剩下的元素即为逆波兰表达式的计算结果。 在main方法中我们则可以测试该方法的使用，可以看到给定逆波兰表达式 {“2”, “1”, “+”, “3”, “*”} 的值为9。 3、表达式求值给定一个中缀表达式（如 3 * (4 + 5) - 2），计算其值。可以使用栈来将中缀表达式转换为后缀表达式，然后使用栈来求解后缀表达式。 import java.util.Stack; public class InfixExpressionEvaluation { public static int evaluateInfixExpression(String expression) { String postfixExpression = infixToPostfix(expression); return evaluatePostfixExpression(postfixExpression); } public static String infixToPostfix(String expression) { StringBuilder postfix = new StringBuilder(); Stack stack = new Stack(); for (char ch : expression.toCharArray()) { if (Character.isDigit(ch)) { postfix.append(ch); } else if (ch == '(') { stack.push(ch); } else if (ch == ')') { while (!stack.isEmpty() && stack.peek() != '(') { postfix.append(stack.pop()); } stack.pop(); // 出栈 '(' } else { while (!stack.isEmpty() && precedence(ch) func2 -> func3 -> func4 // 函数返回顺序：func4 -> func3 -> func2 -> func1 // 调用func1 int result1 = func1(2); System.out.println("Result 1: " + result1); // 输出栈帧信息 System.out.println("Stack Frames:"); for (int i = stack.size() - 1; i >= 0; i--) { StackFrame frame = stack.get(i); System.out.println(frame); } } public static int func1(int n) { Stack stack = new Stack(); stack.push(new StackFrame("func1", "n=" + n)); // 调用func2 int result2 = func2(n + 1); // 出栈栈帧 stack.pop(); // 返回结果 return result2; } public static int func2(int m) { Stack stack = new Stack(); stack.push(new StackFrame("func2", "m=" + m)); // 调用func3 int result3 = func3(m * 2); // 出栈栈帧 stack.pop(); // 返回结果 return result3; } public static int func3(int x) { Stack stack = new Stack(); stack.push(new StackFrame("func3", "x=" + x)); // 调用func4 int result4 = func4(x - 3); // 出栈栈帧 stack.pop(); // 返回结果 return result4; } public static int func4(int y) { Stack stack = new Stack(); stack.push(new StackFrame("func4", "y=" + y)); // 出栈栈帧 stack.pop(); // 返回结果 return y; } // 定义栈帧结构体 static class StackFrame { String functionName; // 函数名 String variables; // 局部变量 public StackFrame(String functionName, String variables) { this.functionName = functionName; this.variables = variables; } @Override public String toString() { return functionName + ": " + variables; } } }在以上示例代码中，我们定义了四个函数：func1、func2、func3和func4。这些函数之间通过函数调用进行嵌套调用。 在main方法中，我们手动创建了一个栈帧栈stack，并在每个函数中使用stack来保存函数调用过程中的栈帧信息。在每个函数开始时，我们使用stack.push()来将当前函数的栈帧入栈；在每个函数结束时，我们使用stack.pop()来将当前函数的栈帧出栈。 最后，在main方法中，我们输出了栈帧信息，可以看到函数调用的顺序和栈帧的变化情况。 5、汉诺塔问题使用栈来求解经典的汉诺塔问题，将 n 个盘子从一个柱子移动到另一个柱子，需要借助第三个柱子作为中转。 import java.util.Stack; public class HanoiTower { public static void main(String[] args) { int n = 3; // 汉诺塔的盘子数 hanoi(n, 'A', 'B', 'C'); } public static void hanoi(int n, char from, char temp, char to) { Stack stack = new Stack(); // 用栈来模拟汉诺塔的移动步骤 // 先将初始问题压入栈中 stack.push(new HanoiStep(n, from, temp, to)); while (!stack.isEmpty()) { HanoiStep step = stack.pop(); if (step.n == 1) { System.out.println("Move disk 1 from " + step.from + " to " + step.to); // 将盘子直接从起始柱子移动到目标柱子 } else { // 将大问题分解为三个子问题，并依次压入栈中 stack.push(new HanoiStep(step.n - 1, step.temp, step.from, step.to)); // 将n-1个盘子从temp柱子移动到to柱子 stack.push(new HanoiStep(1, step.from, step.temp, step.to)); // 将最后一个盘子从起始柱子移动到目标柱子 stack.push(new HanoiStep(step.n - 1, step.from, step.to, step.temp)); // 将n-1个盘子从from柱子移动到temp柱子 } } } static class HanoiStep { int n; // 当前盘子数 char from, temp, to; // 起始柱子、中转柱子、目标柱子 public HanoiStep(int n, char from, char temp, char to) { this.n = n; this.from = from; this.temp = temp; this.to = to; } } }在以上示例代码中，我们使用栈来模拟汉诺塔问题的求解过程。首先我们定义了一个HanoiStep类来表示汉诺塔问题的每一步移动，包括盘子数n以及起始柱子、中转柱子、目标柱子的信息。然后我们使用栈stack来记录每一步的移动过程，初始时将整个问题压入栈中，然后在循环中弹出栈顶的移动步骤，直到栈中的步骤全部完成。 通过这种方式，我们可以使用栈来求解经典的汉诺塔问题，将n个盘子从一个柱子移动到另一个柱子，并借助第三个柱子作为中转。 6、迷宫求解使用栈来搜索迷宫路径，深度优先搜索算法可以使用栈来实现，通过回溯法找出迷宫的所有路径。 import java.util.*; public class MazeSolver { static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向数组，表示上、右、下、左四个方向 public static void main(String[] args) { int[][] maze = { {1, 1, 1, 1, 1}, {1, 0, 0, 1, 1}, {1, 1, 0, 0, 1}, {1, 1, 0, 1, 1}, {1, 1, 1, 1, 1} }; List paths = findPaths(maze, new int[]{1, 1}, new int[]{3, 3}); for (List path : paths) { System.out.println("Path: " + path); } } public static List findPaths(int[][] maze, int[] start, int[] end) { List paths = new ArrayList(); // 用于存储所有路径 Stack stack = new Stack(); // 用栈记录搜索过程中的路径 stack.push(start); // 将起始点入栈 while (!stack.isEmpty()) { int[] current = stack.pop(); if (Arrays.equals(current, end)) { // 到达终点 List path = new ArrayList(stack); // 将栈中的路径信息存入List path.add(end); paths.add(path); } else { for (int[] dir : DIRECTIONS) { int x = current[0] + dir[0]; int y = current[1] + dir[1]; if (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0) { maze[x][y] = 2; // 标记该点已经访问过 stack.push(current); // 将当前点入栈 stack.push(new int[]{x, y}); // 将新点入栈 } } } } return paths; } }在以上示例代码中，我们定义了一个MazeSolver类来表示迷宫求解的过程。在findPaths方法中，我们使用栈stack来记录搜索过程中的路径信息，初始时将起始点入栈，然后在循环中不断弹出栈顶的点进行搜索，直到栈为空。在搜索过程中，我们通过遍历四个方向来扩展搜索空间，将有效的下一步点入栈，并且对访问过的点进行标记，防止重复访问。 通过这种方式，我们可以使用栈来实现深度优先搜索算法，通过回溯法找出迷宫的所有路径。这样可以得出迷宫中从起点到终点的所有可能路径。 总结： 本篇博客详细介绍了Java中栈的知识，包括栈的基本概念、栈帧的结构、Java中的栈帧、栈的应用、栈的基本方法、栈的几种实现方式、双端栈以及关于栈的习题应用。希望读者能通过本文更加深入地理解Java中栈的相关知识，并在实际编程中灵活运用。 通过学习本篇博客，相信读者对Java中的栈有了更清晰的认识，也能更加熟练地运用栈来解决实际的编程问题。感谢阅读！
|
【本文地址】