深入理解Java中的棧從入門到精通(超詳細(xì))新手必看
在Java編程語言中，棧（Stack）是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，它在方法調(diào)用和變量存儲(chǔ)中扮演著關(guān)鍵的角色。了解Java中的棧對(duì)于程序員來說至關(guān)重要，本篇博客將詳細(xì)介紹Java中的棧的知識(shí)，并結(jié)合一些例子來幫助讀者更好地理解。
一、什么是棧？
棧（Stack）是一種常見的數(shù)據(jù)結(jié)構(gòu)，具有后進(jìn)先出（LIFO，Last In First Out）的特性，即最后入棧的元素最先出棧。棧通常用于存儲(chǔ)臨時(shí)性的數(shù)據(jù)，如方法調(diào)用過程中的局部變量、操作數(shù)棧等。在計(jì)算機(jī)科學(xué)中，棧的應(yīng)用非常廣泛，包括編程語言中的函數(shù)調(diào)用、內(nèi)存分配以及表達(dá)式求值等領(lǐng)域。在Java編程語言中，棧也被廣泛應(yīng)用于方法調(diào)用和內(nèi)存管理的過程中。
二、Java中的棧幀
在Java虛擬機(jī)（JVM）中，每個(gè)方法在運(yùn)行時(shí)都會(huì)創(chuàng)建一個(gè)對(duì)應(yīng)的棧幀（Stack Frame），棧幀用于存儲(chǔ)方法的局部變量、操作數(shù)棧、動(dòng)態(tài)鏈接、返回地址等信息。
棧幀的結(jié)構(gòu)如下：
- 局部變量表（Local Variable Table）：局部變量表用于存儲(chǔ)方法參數(shù)和方法內(nèi)部定義的局部變量。局部變量表中的每個(gè)槽位可以存儲(chǔ)一個(gè)基本類型的值或?qū)ο笠?。在方法調(diào)用時(shí)，參數(shù)和本地變量的值會(huì)被壓入局部變量表；在方法執(zhí)行期間，可以通過索引來訪問局部變量表中的值。
- 操作數(shù)棧（Operand Stack）：操作數(shù)棧是用于執(zhí)行方法時(shí)進(jìn)行計(jì)算的臨時(shí)數(shù)據(jù)存儲(chǔ)區(qū)域。操作數(shù)棧的元素可以是任意的Java數(shù)據(jù)類型，包括基本類型和對(duì)象引用。在方法執(zhí)行過程中，操作數(shù)棧用于存儲(chǔ)方法執(zhí)行過程中的計(jì)算結(jié)果、方法參數(shù)以及臨時(shí)變量等數(shù)據(jù)。
- 動(dòng)態(tài)鏈接（Dynamic Linking）：動(dòng)態(tài)鏈接指向運(yùn)行時(shí)常量池中該方法的符號(hào)引用的指針。在Java中，動(dòng)態(tài)鏈接主要用于解析方法調(diào)用的目標(biāo)地址，以便在運(yùn)行時(shí)能夠正確調(diào)用方法。
- 方法返回地址：方法返回地址是指向方法調(diào)用者的指令地址。當(dāng)方法執(zhí)行完畢后，JVM會(huì)使用返回地址恢復(fù)執(zhí)行方法調(diào)用者的指令。
棧幀的創(chuàng)建和銷毀是在方法調(diào)用和返回過程中自動(dòng)進(jìn)行的。每當(dāng)發(fā)生方法調(diào)用時(shí)，JVM會(huì)為該方法創(chuàng)建一個(gè)新的棧幀并將其推入調(diào)用棧（Call Stack），當(dāng)方法返回時(shí)，對(duì)應(yīng)的棧幀會(huì)被銷毀，棧頂指針會(huì)回到前一個(gè)方法的棧幀。棧幀的動(dòng)態(tài)創(chuàng)建和銷毀確保了方法的獨(dú)立性和互相調(diào)用的正確性。
三、棧的應(yīng)用
- 符號(hào)匹配
- HTML和XML文件中的標(biāo)簽匹配（實(shí)質(zhì)還是符號(hào)匹配）
- 實(shí)現(xiàn)函數(shù)調(diào)用
- 文本編輯器中的撤銷
- 網(wǎng)頁瀏覽器中已訪問頁面的歷史記錄
- 作為一個(gè)算法的輔助數(shù)據(jù)結(jié)構(gòu)
四、棧的基本方法
- push(Object item)：將元素item壓入棧頂。
- pop()：彈出棧頂元素，并將其從棧中刪除。
- peek()：返回棧頂元素，但不刪除它。
- isEmpty()：判斷棧是否為空，返回布爾值。
- search(Object item)：搜索元素item在棧中的位置（從棧頂開始），如果找到則返回其距離棧頂?shù)奈恢茫ｍ敒?），如果未找到則返回-1。
- clear()：對(duì)當(dāng)前棧進(jìn)行清空。
下面是一個(gè)示例代碼，演示了如何使用Stack類進(jìn)行棧的基本操作：
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類提供的基本方法，我們可以方便地對(duì)棧進(jìn)行操作，包括壓入、彈出、查看棧頂元素、判斷棧是否為空以及搜索元素在棧中的位置。
五、棧的幾種實(shí)現(xiàn)方式
1、基于簡(jiǎn)單數(shù)組的實(shí)現(xiàn)方式：
使用簡(jiǎn)單數(shù)組作為底層數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)棧，通過將棧頂元素的索引存儲(chǔ)在變量中，實(shí)現(xiàn)壓棧和彈棧操作，每次壓棧時(shí)將元素添加到數(shù)組末尾，每次彈棧時(shí)將棧頂元素從數(shù)組中刪除。由于數(shù)組的長(zhǎng)度是固定的，需要提前定義棧的最大容量。
示例：
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、基于動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)方式：
使用動(dòng)態(tài)數(shù)組（如ArrayList）作為底層數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)棧，通過在動(dòng)態(tài)數(shù)組的尾部進(jìn)行插入和刪除操作來實(shí)現(xiàn)棧的功能。當(dāng)棧容量不足時(shí)，動(dòng)態(tài)數(shù)組可以自動(dòng)進(jìn)行擴(kuò)容，當(dāng)棧元素減少時(shí)，動(dòng)態(tài)數(shù)組可以自動(dòng)進(jìn)行縮容。這種實(shí)現(xiàn)方式提供了動(dòng)態(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、基于鏈表的實(shí)現(xiàn)方式：
使用鏈表作為底層數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)棧，鏈表的頭部或尾部作為棧頂，每次插入和刪除操作都在鏈表的頭部進(jìn)行，通過修改引用來實(shí)現(xiàn)棧的操作。鏈表實(shí)現(xiàn)的?？梢詣?dòng)態(tài)增加和縮小容量，不需要提前定義棧的最大容量，但相對(duì)于數(shù)組實(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ù)組實(shí)現(xiàn)和基于鏈表實(shí)現(xiàn)的比較
（1）基于數(shù)組實(shí)現(xiàn)的棧：
- 各個(gè)操作都是常數(shù)時(shí)間開銷
- 每隔一段時(shí)間進(jìn)行的倍增操作的時(shí)間開銷較大
（2）基于鏈表實(shí)現(xiàn)的棧：
- 棧規(guī)模的增加和減小都很容易
- 各個(gè)操作都是常數(shù)時(shí)間開銷
- 每個(gè)操作都需要使用額外的空間和時(shí)間開銷來處理指針
4、基于隊(duì)列的實(shí)現(xiàn)方式：
使用隊(duì)列作為底層數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)棧，可以使用兩個(gè)隊(duì)列來模擬棧的操作。當(dāng)壓棧時(shí)，將元素添加到非空隊(duì)列中；當(dāng)彈棧時(shí)，將非空隊(duì)列中的元素依次彈出并放入另一個(gè)空隊(duì)列中，直到剩下最后一個(gè)元素，即棧頂元素，然后彈出。這種實(shí)現(xiàn)方式可以保持棧頂元素總是在隊(duì)列的尾部，模擬了棧的后進(jì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），也被稱為雙端隊(duì)列（Deque），是一種支持在兩端進(jìn)行插入和刪除操作的數(shù)據(jù)結(jié)構(gòu)。它可以在棧頂和棧底執(zhí)行壓棧和彈棧操作，因此既能模擬棧的后進(jìn)先出（LIFO）特性，又可以模擬隊(duì)列的先進(jìn)先出（FIFO）特性。
雙端棧是線性表的一種,更是棧的一個(gè)特殊分類，可用借用動(dòng)態(tài)數(shù)組+棧的組合實(shí)現(xiàn)。
2、特點(diǎn)
雙端棧的特點(diǎn)是可以從兩個(gè)方向進(jìn)行操作，即從左側(cè)插入和刪除元素，也可以從右側(cè)插入和刪除元素。這使得雙端棧在某些場(chǎng)景下可以提供更靈活的操作和更高的效率。
3、示例
下面是一個(gè)使用Java的Deque實(shí)現(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();
}
}在這個(gè)示例中，我們使用了Java的Deque，具體是ArrayDeque實(shí)現(xiàn)類。ArrayDeque是基于可調(diào)整大小的數(shù)組實(shí)現(xiàn)的雙端隊(duì)列，可以在隊(duì)列的兩端進(jìn)行插入和刪除操作。我們將其作為雙端棧的底層數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。
通過雙端棧，我們可以在棧頂和棧底進(jì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
在這個(gè)例子中，我們將元素依次壓棧，并使用peek方法查看棧頂元素。隨后，我們連續(xù)進(jìn)行了三次彈棧操作，可以看到棧的后進(jìn)先出特性。最后，我們通過isEmpty方法驗(yàn)證棧是否為空。
通過雙端棧，我們可以自由地在棧頂和棧底進(jìn)行操作，根據(jù)具體的需求實(shí)現(xiàn)不同的功能。
七、關(guān)于棧的習(xí)題應(yīng)用
1、括號(hào)匹配
給定一個(gè)包含括號(hào)字符的字符串，判斷括號(hào)是否匹配，例如 “((()))” 是匹配的，而 “(()” 則不匹配?？梢允褂脳韺?shí)現(xiàn)括號(hào)匹配的算法。
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));
}
}在上面的示例代碼中，我們定義了一個(gè)isBracketMatch方法來判斷輸入的字符串中的括號(hào)是否匹配。我們使用一個(gè)Stack<Character>來存儲(chǔ)左括號(hào)，遍歷輸入字符串，遇到左括號(hào)就入棧，遇到右括號(hào)就出棧并匹配。最后檢查棧是否為空來判斷括號(hào)是否完全匹配。
在main方法中我們則可以測(cè)試該方法的使用，可以看到input1是匹配的，而input2則不匹配。
2、逆波蘭表達(dá)式求值
給定一個(gè)逆波蘭表達(dá)式，計(jì)算其值。逆波蘭表達(dá)式是一種通過后綴表達(dá)式來進(jìn)行計(jì)算的算法，可以使用棧來實(shí)現(xiàn)逆波蘭表達(dá)式的求值。
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("逆波蘭表達(dá)式的值為: " + evalRPN(tokens)); // 輸出：9
}
}在以上示例代碼中，我們定義了一個(gè)evalRPN方法，用于計(jì)算給定的逆波蘭表達(dá)式的值。我們使用一個(gè)Stack<Integer>來存儲(chǔ)操作數(shù)，遍歷逆波蘭表達(dá)式，當(dāng)遇到操作數(shù)時(shí)入棧，當(dāng)遇到運(yùn)算符時(shí)從棧中彈出相應(yīng)數(shù)量的操作數(shù)進(jìn)行計(jì)算后將結(jié)果入棧。最終棧中剩下的元素即為逆波蘭表達(dá)式的計(jì)算結(jié)果。
在main方法中我們則可以測(cè)試該方法的使用，可以看到給定逆波蘭表達(dá)式 {“2”, “1”, “+”, “3”, “*”} 的值為9。
3、表達(dá)式求值
給定一個(gè)中綴表達(dá)式（如 3 * (4 + 5) - 2），計(jì)算其值?？梢允褂脳韺⒅芯Y表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后使用棧來求解后綴表達(dá)式。
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
}
}在以上示例代碼中，我們定義了三個(gè)方法：
- evaluateInfixExpression：用于計(jì)算給定中綴表達(dá)式的值。這個(gè)方法首先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后再調(diào)用evaluatePostfixExpression方法對(duì)后綴表達(dá)式求值。
- infixToPostfix：用于將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。這個(gè)方法使用一個(gè)StringBuilder來構(gòu)建后綴表達(dá)式，同時(shí)使用一個(gè)棧來輔助轉(zhuǎn)換。遍歷中綴表達(dá)式的字符，遇到數(shù)字直接添加到后綴表達(dá)式中，遇到左括號(hào)入棧，遇到右括號(hào)則將棧頂?shù)倪\(yùn)算符全部彈出并添加到后綴表達(dá)式中，直到遇到左括號(hào)，括號(hào)不添加到最終結(jié)果中；遇到運(yùn)算符時(shí)，如果棧頂?shù)倪\(yùn)算符的優(yōu)先級(jí)高于或等于當(dāng)前運(yùn)算符，則將棧頂?shù)倪\(yùn)算符彈出并添加到后綴表達(dá)式中，然后將當(dāng)前運(yùn)算符入棧。
- evaluatePostfixExpression：用于對(duì)后綴表達(dá)式進(jìn)行求值。這個(gè)方法使用一個(gè)棧來存儲(chǔ)操作數(shù)，遍歷后綴表達(dá)式的字符，遇到數(shù)字就入棧，遇到運(yùn)算符就從棧中彈出相應(yīng)數(shù)量的操作數(shù)進(jìn)行計(jì)算后將結(jié)果入棧。返回棧中剩下的元素即為后綴表達(dá)式的計(jì)算結(jié)果。
在main方法中我們則可以測(cè)試該方法的使用，可以看到給定中綴表達(dá)式 “3 * (4 + 5) - 2” 的值為25。
4、函數(shù)調(diào)用堆棧
理解函數(shù)調(diào)用時(shí)棧的使用情況，包括函數(shù)調(diào)用、參數(shù)傳遞、局部變量的存儲(chǔ)等，可以通過手動(dòng)模擬函數(shù)調(diào)用過程并使用棧來實(shí)現(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;
}
}
}在以上示例代碼中，我們定義了四個(gè)函數(shù)：func1、func2、func3和func4。這些函數(shù)之間通過函數(shù)調(diào)用進(jìn)行嵌套調(diào)用。
在main方法中，我們手動(dòng)創(chuàng)建了一個(gè)棧幀棧stack，并在每個(gè)函數(shù)中使用stack來保存函數(shù)調(diào)用過程中的棧幀信息。在每個(gè)函數(shù)開始時(shí)，我們使用stack.push()來將當(dāng)前函數(shù)的棧幀入棧；在每個(gè)函數(shù)結(jié)束時(shí)，我們使用stack.pop()來將當(dāng)前函數(shù)的棧幀出棧。
最后，在main方法中，我們輸出了棧幀信息，可以看到函數(shù)調(diào)用的順序和棧幀的變化情況。
5、漢諾塔問題
使用棧來求解經(jīng)典的漢諾塔問題，將 n 個(gè)盤子從一個(gè)柱子移動(dòng)到另一個(gè)柱子，需要借助第三個(gè)柱子作為中轉(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<>(); // 用棧來模擬漢諾塔的移動(dòng)步驟
// 先將初始問題壓入棧中
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); // 將盤子直接從起始柱子移動(dòng)到目標(biāo)柱子
} else {
// 將大問題分解為三個(gè)子問題，并依次壓入棧中
stack.push(new HanoiStep(step.n - 1, step.temp, step.from, step.to)); // 將n-1個(gè)盤子從temp柱子移動(dòng)到to柱子
stack.push(new HanoiStep(1, step.from, step.temp, step.to)); // 將最后一個(gè)盤子從起始柱子移動(dòng)到目標(biāo)柱子
stack.push(new HanoiStep(step.n - 1, step.from, step.to, step.temp)); // 將n-1個(gè)盤子從from柱子移動(dòng)到temp柱子
}
}
}
static class HanoiStep {
int n; // 當(dāng)前盤子數(shù)
char from, temp, to; // 起始柱子、中轉(zhuǎn)柱子、目標(biāo)柱子
public HanoiStep(int n, char from, char temp, char to) {
this.n = n;
this.from = from;
this.temp = temp;
this.to = to;
}
}
}在以上示例代碼中，我們使用棧來模擬漢諾塔問題的求解過程。首先我們定義了一個(gè)HanoiStep類來表示漢諾塔問題的每一步移動(dòng)，包括盤子數(shù)n以及起始柱子、中轉(zhuǎn)柱子、目標(biāo)柱子的信息。然后我們使用棧stack來記錄每一步的移動(dòng)過程，初始時(shí)將整個(gè)問題壓入棧中，然后在循環(huán)中彈出棧頂?shù)囊苿?dòng)步驟，直到棧中的步驟全部完成。
通過這種方式，我們可以使用棧來求解經(jīng)典的漢諾塔問題，將n個(gè)盤子從一個(gè)柱子移動(dòng)到另一個(gè)柱子，并借助第三個(gè)柱子作為中轉(zhuǎn)。
6、迷宮求解
使用棧來搜索迷宮路徑，深度優(yōu)先搜索算法可以使用棧來實(shí)現(xiàn)，通過回溯法找出迷宮的所有路徑。
import java.util.*;
public class MazeSolver {
static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // 方向數(shù)組，表示上、右、下、左四個(gè)方向
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<>(); // 用于存儲(chǔ)所有路徑
Stack<int[]> stack = new Stack<>(); // 用棧記錄搜索過程中的路徑
stack.push(start); // 將起始點(diǎn)入棧
while (!stack.isEmpty()) {
int[] current = stack.pop();
if (Arrays.equals(current, end)) { // 到達(dá)終點(diǎn)
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; // 標(biāo)記該點(diǎn)已經(jīng)訪問過
stack.push(current); // 將當(dāng)前點(diǎn)入棧
stack.push(new int[]{x, y}); // 將新點(diǎn)入棧
}
}
}
}
return paths;
}
}在以上示例代碼中，我們定義了一個(gè)MazeSolver類來表示迷宮求解的過程。在findPaths方法中，我們使用棧stack來記錄搜索過程中的路徑信息，初始時(shí)將起始點(diǎn)入棧，然后在循環(huán)中不斷彈出棧頂?shù)狞c(diǎn)進(jìn)行搜索，直到棧為空。在搜索過程中，我們通過遍歷四個(gè)方向來擴(kuò)展搜索空間，將有效的下一步點(diǎn)入棧，并且對(duì)訪問過的點(diǎn)進(jìn)行標(biāo)記，防止重復(fù)訪問。
通過這種方式，我們可以使用棧來實(shí)現(xiàn)深度優(yōu)先搜索算法，通過回溯法找出迷宮的所有路徑。這樣可以得出迷宮中從起點(diǎn)到終點(diǎn)的所有可能路徑。
總結(jié)：
本篇博客詳細(xì)介紹了Java中棧的知識(shí)，包括棧的基本概念、棧幀的結(jié)構(gòu)、Java中的棧幀、棧的應(yīng)用、棧的基本方法、棧的幾種實(shí)現(xiàn)方式、雙端棧以及關(guān)于棧的習(xí)題應(yīng)用。希望讀者能通過本文更加深入地理解Java中棧的相關(guān)知識(shí)，并在實(shí)際編程中靈活運(yùn)用。
通過學(xué)習(xí)本篇博客，相信讀者對(duì)Java中的棧有了更清晰的認(rèn)識(shí)，也能更加熟練地運(yùn)用棧來解決實(shí)際的編程問題。感謝閱讀！
到此這篇關(guān)于深入理解Java中的棧（超詳細(xì)）新手必看的文章就介紹到這了,更多相關(guān)Java中的棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章是BUFFER.pwn同學(xué)分享的基于Java與MySQL的圖書管理系統(tǒng)，需要的朋友可以參考一下2021-04-04
這篇文章主要介紹了Java多態(tài)性定義與用法,較為詳細(xì)的分析了多態(tài)的概念、功能以及java定義與實(shí)現(xiàn)面向?qū)ο蠖鄳B(tài)性的相關(guān)操作技巧,需要的朋友可以參考下2017-09-09
java?-jar啟動(dòng)參數(shù)設(shè)置file.encoding編碼,解決中文亂碼的問題
這篇文章主要介紹了java?-jar啟動(dòng)參數(shù)設(shè)置file.encoding編碼,解決中文亂碼的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-07-07
詳解SpringCloud是如何動(dòng)態(tài)更新配置的
spring cloud在config配置管理的基礎(chǔ)上，提供了consul config的配置管理和動(dòng)態(tài)監(jiān)聽，那么這里面到底是怎樣實(shí)現(xiàn)的，本文將為你揭秘，感興趣的小伙伴可以跟著小伙伴一起來學(xué)習(xí)2023-06-06
SpringCloud與Consul集成實(shí)現(xiàn)負(fù)載均衡功能
負(fù)載均衡基本概念有：實(shí)服務(wù)、實(shí)服務(wù)組、虛服務(wù)、調(diào)度算法、持續(xù)性等，其常用應(yīng)用場(chǎng)景主要是服務(wù)器負(fù)載均衡，鏈路負(fù)載均衡。這篇文章主要介紹了SpringCloud與Consul集成實(shí)現(xiàn)負(fù)載均衡 ,需要的朋友可以參考下2018-09-09
這篇文章主要介紹了Java枚舉類用法,實(shí)例分析了java中枚舉類的實(shí)現(xiàn)與使用技巧,需要的朋友可以參考下2015-05-05
spring的TransactionalEventListener事務(wù)感知源碼解析
這篇文章主要為大家介紹了spring的TransactionalEventListener事務(wù)感知源碼解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-09-09
Java中List的contains()方法的使用小結(jié)
List?的?contains()?方法用于檢查列表中是否包含指定的元素,借助equals()方法進(jìn)行判斷,下面就來介紹Java中List的contains()方法的使用小結(jié),感興趣的可以了解一下2025-04-04
Mybatis-Plus @TableField自動(dòng)填充時(shí)間為null的問題解決
本文主要介紹了Mybatis-Plus @TableField自動(dòng)填充時(shí)間為null的問題解決，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
Java并發(fā)工具類Exchanger的相關(guān)知識(shí)總結(jié)
今天給大家?guī)淼奈恼率荍ava工具類Exchanger的相關(guān)知識(shí)總結(jié),文中有非常詳細(xì)的介紹及代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們很有幫助,需要的朋友可以參考下2021-06-06