深入理解Java中的棧從入門到精通(超詳細)新手必看
在Java編程語言中，棧（Stack）是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它在方法調(diào)用和變量存儲中扮演著關(guān)鍵的角色。了解Java中的棧對于程序員來說至關(guān)重要，本篇博客將詳細介紹Java中的棧的知識，并結(jié)合一些例子來幫助讀者更好地理解。
一、什么是棧？
棧（Stack）是一種常見的數(shù)據(jù)結(jié)構(gòu)，具有后進先出（LIFO，Last In First Out）的特性，即最后入棧的元素最先出棧。棧通常用于存儲臨時性的數(shù)據(jù)，如方法調(diào)用過程中的局部變量、操作數(shù)棧等。在計算機科學(xué)中，棧的應(yīng)用非常廣泛，包括編程語言中的函數(shù)調(diào)用、內(nèi)存分配以及表達式求值等領(lǐng)域。在Java編程語言中，棧也被廣泛應(yīng)用于方法調(diào)用和內(nèi)存管理的過程中。
二、Java中的棧幀
在Java虛擬機（JVM）中，每個方法在運行時都會創(chuàng)建一個對應(yīng)的棧幀（Stack Frame），棧幀用于存儲方法的局部變量、操作數(shù)棧、動態(tài)鏈接、返回地址等信息。
棧幀的結(jié)構(gòu)如下：
- 局部變量表（Local Variable Table）：局部變量表用于存儲方法參數(shù)和方法內(nèi)部定義的局部變量。局部變量表中的每個槽位可以存儲一個基本類型的值或?qū)ο笠?。在方法調(diào)用時，參數(shù)和本地變量的值會被壓入局部變量表；在方法執(zhí)行期間，可以通過索引來訪問局部變量表中的值。
- 操作數(shù)棧（Operand Stack）：操作數(shù)棧是用于執(zhí)行方法時進行計算的臨時數(shù)據(jù)存儲區(qū)域。操作數(shù)棧的元素可以是任意的Java數(shù)據(jù)類型，包括基本類型和對象引用。在方法執(zhí)行過程中，操作數(shù)棧用于存儲方法執(zhí)行過程中的計算結(jié)果、方法參數(shù)以及臨時變量等數(shù)據(jù)。
- 動態(tài)鏈接（Dynamic Linking）：動態(tài)鏈接指向運行時常量池中該方法的符號引用的指針。在Java中，動態(tài)鏈接主要用于解析方法調(diào)用的目標地址，以便在運行時能夠正確調(diào)用方法。
- 方法返回地址：方法返回地址是指向方法調(diào)用者的指令地址。當方法執(zhí)行完畢后，JVM會使用返回地址恢復(fù)執(zhí)行方法調(diào)用者的指令。
棧幀的創(chuàng)建和銷毀是在方法調(diào)用和返回過程中自動進行的。每當發(fā)生方法調(diào)用時，JVM會為該方法創(chuàng)建一個新的棧幀并將其推入調(diào)用棧（Call Stack），當方法返回時，對應(yīng)的棧幀會被銷毀，棧頂指針會回到前一個方法的棧幀。棧幀的動態(tài)創(chuàng)建和銷毀確保了方法的獨立性和互相調(diào)用的正確性。
三、棧的應(yīng)用
- 符號匹配
- HTML和XML文件中的標簽匹配（實質(zhì)還是符號匹配）
- 實現(xiàn)函數(shù)調(diào)用
- 文本編輯器中的撤銷
- 網(wǎng)頁瀏覽器中已訪問頁面的歷史記錄
- 作為一個算法的輔助數(shù)據(jù)結(jié)構(gòu)
四、棧的基本方法
- push(Object item)：將元素item壓入棧頂。
- pop()：彈出棧頂元素，并將其從棧中刪除。
- peek()：返回棧頂元素，但不刪除它。
- isEmpty()：判斷棧是否為空，返回布爾值。
- search(Object item)：搜索元素item在棧中的位置（從棧頂開始），如果找到則返回其距離棧頂?shù)奈恢茫ｍ敒?），如果未找到則返回-1。
- clear()：對當前棧進行清空。
下面是一個示例代碼，演示了如何使用Stack類進行棧的基本操作：
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> 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);
}
}執(zhí)行以上代碼，輸出結(jié)果為：
Popped element: 30 Peeked element: 20 Is the stack empty? false Position of 20 in the stack: 1
通過使用Stack類提供的基本方法，我們可以方便地對棧進行操作，包括壓入、彈出、查看棧頂元素、判斷棧是否為空以及搜索元素在棧中的位置。
五、棧的幾種實現(xiàn)方式
1、基于簡單數(shù)組的實現(xiàn)方式：
使用簡單數(shù)組作為底層數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)棧，通過將棧頂元素的索引存儲在變量中，實現(xiàn)壓棧和彈棧操作，每次壓棧時將元素添加到數(shù)組末尾，每次彈棧時將棧頂元素從數(shù)組中刪除。由于數(shù)組的長度是固定的，需要提前定義棧的最大容量。
示例：
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、基于動態(tài)數(shù)組的實現(xiàn)方式：
使用動態(tài)數(shù)組（如ArrayList）作為底層數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)棧，通過在動態(tài)數(shù)組的尾部進行插入和刪除操作來實現(xiàn)棧的功能。當棧容量不足時，動態(tài)數(shù)組可以自動進行擴容，當棧元素減少時，動態(tài)數(shù)組可以自動進行縮容。這種實現(xiàn)方式提供了動態(tài)調(diào)整容量的特性。
示例：
import java.util.ArrayList;
public class DynamicArrayStack {
private ArrayList<Integer> 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、基于鏈表的實現(xiàn)方式：
使用鏈表作為底層數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)棧，鏈表的頭部或尾部作為棧頂，每次插入和刪除操作都在鏈表的頭部進行，通過修改引用來實現(xiàn)棧的操作。鏈表實現(xiàn)的?？梢詣討B(tài)增加和縮小容量，不需要提前定義棧的最大容量，但相對于數(shù)組實現(xiàn)，需要更多的空間開銷。
示例：
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;
}
}基于數(shù)組實現(xiàn)和基于鏈表實現(xiàn)的比較
（1）基于數(shù)組實現(xiàn)的棧：
- 各個操作都是常數(shù)時間開銷
- 每隔一段時間進行的倍增操作的時間開銷較大
（2）基于鏈表實現(xiàn)的棧：
- 棧規(guī)模的增加和減小都很容易
- 各個操作都是常數(shù)時間開銷
- 每個操作都需要使用額外的空間和時間開銷來處理指針
4、基于隊列的實現(xiàn)方式：
使用隊列作為底層數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)棧，可以使用兩個隊列來模擬棧的操作。當壓棧時，將元素添加到非空隊列中；當彈棧時，將非空隊列中的元素依次彈出并放入另一個空隊列中，直到剩下最后一個元素，即棧頂元素，然后彈出。這種實現(xiàn)方式可以保持棧頂元素總是在隊列的尾部，模擬了棧的后進先出（LIFO）特性。
示例：
import java.util.LinkedList;
import java.util.Queue;
public class QueueBasedStack {
private Queue<Integer> queue1;
private Queue<Integer> 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<Integer> 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），是一種支持在兩端進行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)。它可以在棧頂和棧底執(zhí)行壓棧和彈棧操作，因此既能模擬棧的后進先出（LIFO）特性，又可以模擬隊列的先進先出（FIFO）特性。
雙端棧是線性表的一種,更是棧的一個特殊分類，可用借用動態(tài)數(shù)組+棧的組合實現(xiàn)。
2、特點
雙端棧的特點是可以從兩個方向進行操作，即從左側(cè)插入和刪除元素，也可以從右側(cè)插入和刪除元素。這使得雙端棧在某些場景下可以提供更靈活的操作和更高的效率。
3、示例
下面是一個使用Java的Deque實現(xiàn)雙端棧的示例代碼：
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeStack {
private Deque<Integer> 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實現(xiàn)類。ArrayDeque是基于可調(diào)整大小的數(shù)組實現(xiàn)的雙端隊列，可以在隊列的兩端進行插入和刪除操作。我們將其作為雙端棧的底層數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。
通過雙端棧，我們可以在棧頂和棧底進行元素的插入和刪除操作。例如：
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方法查看棧頂元素。隨后，我們連續(xù)進行了三次彈棧操作，可以看到棧的后進先出特性。最后，我們通過isEmpty方法驗證棧是否為空。
通過雙端棧，我們可以自由地在棧頂和棧底進行操作，根據(jù)具體的需求實現(xiàn)不同的功能。
七、關(guān)于棧的習(xí)題應(yīng)用
1、括號匹配
給定一個包含括號字符的字符串，判斷括號是否匹配，例如 “((()))” 是匹配的，而 “(()” 則不匹配。可以使用棧來實現(xiàn)括號匹配的算法。
import java.util.Stack;
public class BracketMatching {
public static boolean isBracketMatch(String input) {
Stack<Character> 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<Character>來存儲左括號，遍歷輸入字符串，遇到左括號就入棧，遇到右括號就出棧并匹配。最后檢查棧是否為空來判斷括號是否完全匹配。
在main方法中我們則可以測試該方法的使用，可以看到input1是匹配的，而input2則不匹配。
2、逆波蘭表達式求值
給定一個逆波蘭表達式，計算其值。逆波蘭表達式是一種通過后綴表達式來進行計算的算法，可以使用棧來實現(xiàn)逆波蘭表達式的求值。
import java.util.Stack;
public class ReversePolishNotation {
public static int evalRPN(String[] tokens) {
Stack<Integer> 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<Integer>來存儲操作數(shù)，遍歷逆波蘭表達式，當遇到操作數(shù)時入棧，當遇到運算符時從棧中彈出相應(yīng)數(shù)量的操作數(shù)進行計算后將結(jié)果入棧。最終棧中剩下的元素即為逆波蘭表達式的計算結(jié)果。
在main方法中我們則可以測試該方法的使用，可以看到給定逆波蘭表達式 {“2”, “1”, “+”, “3”, “*”} 的值為9。
3、表達式求值
給定一個中綴表達式（如 3 * (4 + 5) - 2），計算其值?？梢允褂脳韺⒅芯Y表達式轉(zhuǎn)換為后綴表達式，然后使用棧來求解后綴表達式。
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<Character> 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) <= precedence(stack.peek())) {
postfix.append(stack.pop());
}
stack.push(ch);
}
}
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
return postfix.toString();
}
public static int evaluatePostfixExpression(String expression) {
Stack<Integer> stack = new Stack<>();
for (char ch : expression.toCharArray()) {
if (Character.isDigit(ch)) {
stack.push(Character.getNumericValue(ch));
} else {
int operand2 = stack.pop();
int operand1 = stack.pop();
switch (ch) {
case '+':
stack.push(operand1 + operand2);
break;
case '-':
stack.push(operand1 - operand2);
break;
case '*':
stack.push(operand1 * operand2);
break;
case '/':
stack.push(operand1 / operand2);
break;
}
}
}
return stack.pop();
}
public static int precedence(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
return 0;
}
}
public static void main(String[] args) {
String expression = "3 * (4 + 5) - 2";
int result = evaluateInfixExpression(expression);
System.out.println(expression + " = " + result); // 輸出：3 * (4 + 5) - 2 = 25
}
}在以上示例代碼中，我們定義了三個方法：
- evaluateInfixExpression：用于計算給定中綴表達式的值。這個方法首先將中綴表達式轉(zhuǎn)換為后綴表達式，然后再調(diào)用evaluatePostfixExpression方法對后綴表達式求值。
- infixToPostfix：用于將中綴表達式轉(zhuǎn)換為后綴表達式。這個方法使用一個StringBuilder來構(gòu)建后綴表達式，同時使用一個棧來輔助轉(zhuǎn)換。遍歷中綴表達式的字符，遇到數(shù)字直接添加到后綴表達式中，遇到左括號入棧，遇到右括號則將棧頂?shù)倪\算符全部彈出并添加到后綴表達式中，直到遇到左括號，括號不添加到最終結(jié)果中；遇到運算符時，如果棧頂?shù)倪\算符的優(yōu)先級高于或等于當前運算符，則將棧頂?shù)倪\算符彈出并添加到后綴表達式中，然后將當前運算符入棧。
- evaluatePostfixExpression：用于對后綴表達式進行求值。這個方法使用一個棧來存儲操作數(shù)，遍歷后綴表達式的字符，遇到數(shù)字就入棧，遇到運算符就從棧中彈出相應(yīng)數(shù)量的操作數(shù)進行計算后將結(jié)果入棧。返回棧中剩下的元素即為后綴表達式的計算結(jié)果。
在main方法中我們則可以測試該方法的使用，可以看到給定中綴表達式 “3 * (4 + 5) - 2” 的值為25。
4、函數(shù)調(diào)用堆棧
理解函數(shù)調(diào)用時棧的使用情況，包括函數(shù)調(diào)用、參數(shù)傳遞、局部變量的存儲等，可以通過手動模擬函數(shù)調(diào)用過程并使用棧來實現(xiàn)。
import java.util.Stack;
public class FunctionCallStack {
public static void main(String[] args) {
// 創(chuàng)建棧幀
Stack<StackFrame> stack = new Stack<>();
// 函數(shù)調(diào)用順序：func1 -> func2 -> func3 -> func4
// 函數(shù)返回順序：func4 -> func3 -> func2 -> func1
// 調(diào)用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<StackFrame> stack = new Stack<>();
stack.push(new StackFrame("func1", "n=" + n));
// 調(diào)用func2
int result2 = func2(n + 1);
// 出棧棧幀
stack.pop();
// 返回結(jié)果
return result2;
}
public static int func2(int m) {
Stack<StackFrame> stack = new Stack<>();
stack.push(new StackFrame("func2", "m=" + m));
// 調(diào)用func3
int result3 = func3(m * 2);
// 出棧棧幀
stack.pop();
// 返回結(jié)果
return result3;
}
public static int func3(int x) {
Stack<StackFrame> stack = new Stack<>();
stack.push(new StackFrame("func3", "x=" + x));
// 調(diào)用func4
int result4 = func4(x - 3);
// 出棧棧幀
stack.pop();
// 返回結(jié)果
return result4;
}
public static int func4(int y) {
Stack<StackFrame> stack = new Stack<>();
stack.push(new StackFrame("func4", "y=" + y));
// 出棧棧幀
stack.pop();
// 返回結(jié)果
return y;
}
// 定義棧幀結(jié)構(gòu)體
static class StackFrame {
String functionName; // 函數(shù)名
String variables; // 局部變量
public StackFrame(String functionName, String variables) {
this.functionName = functionName;
this.variables = variables;
}
@Override
public String toString() {
return functionName + ": " + variables;
}
}
}在以上示例代碼中，我們定義了四個函數(shù)：func1、func2、func3和func4。這些函數(shù)之間通過函數(shù)調(diào)用進行嵌套調(diào)用。
在main方法中，我們手動創(chuàng)建了一個棧幀棧stack，并在每個函數(shù)中使用stack來保存函數(shù)調(diào)用過程中的棧幀信息。在每個函數(shù)開始時，我們使用stack.push()來將當前函數(shù)的棧幀入棧；在每個函數(shù)結(jié)束時，我們使用stack.pop()來將當前函數(shù)的棧幀出棧。
最后，在main方法中，我們輸出了棧幀信息，可以看到函數(shù)調(diào)用的順序和棧幀的變化情況。
5、漢諾塔問題
使用棧來求解經(jīng)典的漢諾塔問題，將 n 個盤子從一個柱子移動到另一個柱子，需要借助第三個柱子作為中轉(zhuǎn)。
import java.util.Stack;
public class HanoiTower {
public static void main(String[] args) {
int n = 3; // 漢諾塔的盤子數(shù)
hanoi(n, 'A', 'B', 'C');
}
public static void hanoi(int n, char from, char temp, char to) {
Stack<HanoiStep> 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; // 當前盤子數(shù)
char from, temp, to; // 起始柱子、中轉(zhuǎn)柱子、目標柱子
public HanoiStep(int n, char from, char temp, char to) {
this.n = n;
this.from = from;
this.temp = temp;
this.to = to;
}
}
}在以上示例代碼中，我們使用棧來模擬漢諾塔問題的求解過程。首先我們定義了一個HanoiStep類來表示漢諾塔問題的每一步移動，包括盤子數(shù)n以及起始柱子、中轉(zhuǎn)柱子、目標柱子的信息。然后我們使用棧stack來記錄每一步的移動過程，初始時將整個問題壓入棧中，然后在循環(huán)中彈出棧頂?shù)囊苿硬襟E，直到棧中的步驟全部完成。
通過這種方式，我們可以使用棧來求解經(jīng)典的漢諾塔問題，將n個盤子從一個柱子移動到另一個柱子，并借助第三個柱子作為中轉(zhuǎn)。
6、迷宮求解
使用棧來搜索迷宮路徑，深度優(yōu)先搜索算法可以使用棧來實現(xiàn)，通過回溯法找出迷宮的所有路徑。
import java.util.*;
public class MazeSolver {
static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向數(shù)組，表示上、右、下、左四個方向
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<List<int[]>> paths = findPaths(maze, new int[]{1, 1}, new int[]{3, 3});
for (List<int[]> path : paths) {
System.out.println("Path: " + path);
}
}
public static List<List<int[]>> findPaths(int[][] maze, int[] start, int[] end) {
List<List<int[]>> paths = new ArrayList<>(); // 用于存儲所有路徑
Stack<int[]> stack = new Stack<>(); // 用棧記錄搜索過程中的路徑
stack.push(start); // 將起始點入棧
while (!stack.isEmpty()) {
int[] current = stack.pop();
if (Arrays.equals(current, end)) { // 到達終點
List<int[]> 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; // 標記該點已經(jīng)訪問過
stack.push(current); // 將當前點入棧
stack.push(new int[]{x, y}); // 將新點入棧
}
}
}
}
return paths;
}
}在以上示例代碼中，我們定義了一個MazeSolver類來表示迷宮求解的過程。在findPaths方法中，我們使用棧stack來記錄搜索過程中的路徑信息，初始時將起始點入棧，然后在循環(huán)中不斷彈出棧頂?shù)狞c進行搜索，直到棧為空。在搜索過程中，我們通過遍歷四個方向來擴展搜索空間，將有效的下一步點入棧，并且對訪問過的點進行標記，防止重復(fù)訪問。
通過這種方式，我們可以使用棧來實現(xiàn)深度優(yōu)先搜索算法，通過回溯法找出迷宮的所有路徑。這樣可以得出迷宮中從起點到終點的所有可能路徑。
總結(jié)：
本篇博客詳細介紹了Java中棧的知識，包括棧的基本概念、棧幀的結(jié)構(gòu)、Java中的棧幀、棧的應(yīng)用、棧的基本方法、棧的幾種實現(xiàn)方式、雙端棧以及關(guān)于棧的習(xí)題應(yīng)用。希望讀者能通過本文更加深入地理解Java中棧的相關(guān)知識，并在實際編程中靈活運用。
通過學(xué)習(xí)本篇博客，相信讀者對Java中的棧有了更清晰的認識，也能更加熟練地運用棧來解決實際的編程問題。感謝閱讀！
到此這篇關(guān)于深入理解Java中的棧（超詳細）新手必看的文章就介紹到這了,更多相關(guān)Java中的棧內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java Lambda在JVM中是如何實現(xiàn)的，感興趣的小伙伴一起來了解了解2021-08-08
這篇文章主要介紹了Mybatis如何使用注解優(yōu)化代碼,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-11-11
下面小編就為大家?guī)硪黄獪\談Java double 相乘的結(jié)果偏差小問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
Java中的stream流的概念解析及實際運用總結(jié)
流是指傳輸時的數(shù)據(jù),Java為流準備了很多內(nèi)置類,尤其是IO輸入輸出流非常常用,這里我們來看一下Java中的stream流的概念解析及實際運用總結(jié)2016-06-06
在java平臺，實現(xiàn)異步調(diào)用的角色主要三種角色：調(diào)用者、取貨憑證、真實數(shù)據(jù)。本篇文章給大家介紹java實現(xiàn)異步調(diào)用實例代碼，需要的朋友可以參考下2015-09-09
這篇文章主要介紹了java為什么不允許類多重繼承卻允許接口多重繼承，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
這篇文章主要介紹了Spring全局懶加載的優(yōu)劣及使用方法詳解,Spring 懶加載是一種延遲加載的機制,它允許在需要時才創(chuàng)建和初始化對象,而不是在應(yīng)用程序啟動時就立即加載所有對象,通過懶加載,可以提高應(yīng)用程序的性能和資源利用率,需要的朋友可以參考下2023-10-10
Spring事務(wù)處理Transactional,鎖同步和并發(fā)線程
本文詳細講解了Spring事務(wù)處理Transactional,鎖同步和并發(fā)線程。對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
Java前端實現(xiàn)發(fā)送date類型的參數(shù)給后端
這篇文章主要介紹了Java前端實現(xiàn)發(fā)送date類型的參數(shù)給后端方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-06-06
java中LinkedList使用迭代器優(yōu)化移除批量元素原理
本文主要介紹了java中LinkedList使用迭代器優(yōu)化移除批量元素原理，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10