深入理解棧與隊列——從原理理解到實戰應用

一、引言

二、棧（Stack）

2.1 棧的基本概念

2.2 棧的使用

2.3 棧的模擬實現

2.4 棧的實戰應用

2.4.1 括號匹配

2.4.2 逆波蘭表達式求值

2.4.3 出棧入棧次序匹配

2.4.4 最小棧

三、隊列（Queue）

3.1 隊列的基本概念

3.2 隊列的使用

3.3 隊列的模擬實現

3.4 隊列的實戰應用

3.4.1 設計實現循環隊列

四、常見面試題與實戰應用

4.1 用隊列實現棧

4.2 用棧實現隊列

五、總結

一、引言

數據結構是編程的基石，無論是算法設計還是系統開發，都離不開對數據結構的深入理解。棧和隊列作為兩種最基礎的線性數據結構，廣泛應用于各種場景中。本文將系統性地介紹棧和隊列的概念、實現方式以及實際應用，幫助讀者建立完整的知識體系。

二、棧（Stack）

2.1 棧的基本概念

棧是一種遵循先進后出（FILO，First In Last Out）原則的線性數據結構，只允許在棧頂進行入棧（壓棧）和出棧操作。

拿生活中的一些現象舉例子：比如超市里盤子售賣區的一摞一摞盤子，我們想要新增盤子只能放在最頂部，同樣地，拿出盤子也只能在最頂部拿。

2.2 棧的使用

在Java內置的Stack類中，提供了以下操作方法：

public void push(int data)	入棧/壓棧，即增加新元素
public int pop()	出棧，即刪除棧頂的元素并返回該元素
public int peek()	獲取棧頂元素并返回，不刪除
public boolean empty()	判斷棧是否為空
public int size()	獲取棧的大小

具體使用示例如下：

import java.util.Stack;public class StackExample {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();// 壓棧操作stack.push(1);stack.push(2);stack.push(3);// 查看棧頂元素System.out.println("棧頂元素: " + stack.peek()); // 輸出 3// 出棧操作System.out.println("出棧: " + stack.pop()); // 輸出 3System.out.println("出棧: " + stack.pop()); // 輸出 2// 判斷棧是否為空System.out.println("棧是否為空: " + stack.empty()); // 輸出 false// 獲取棧的大小System.out.println("棧的大小: " + stack.size());   // 輸出 1}
}

2.3 棧的模擬實現

在模擬實現棧時，我們可以選用數組也可以選用鏈表：用數組實現的棧叫順序棧；用鏈表實現的棧叫鏈式棧。

我們先編寫一個 MyStack 類如下：

public class MyStack {// 順序棧public int[] arr;public int usedSize;           //用于記錄棧的元素個數public MyStack(int[] arr) {this.arr = new int[10];    //暫定長度為10}// 鏈式棧（單向）static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public int usedSize;           //用于記錄棧的元素個數// 鏈式棧（雙向）static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode tail;public int usedSize;           //用于記錄棧的元素個數
}

接下來我們來實現 push方法，思路很簡單，我們只需要在 usedSize 位置增加新元素就可以了，但是要注意棧滿了的時候，需要擴容。

順序棧實現如下：

public void push(int data) {if (empty()) {this.arr = Arrays.copyOf(this.arr,2*this.arr.length);    //擴容為原長度的2倍}arr[usedSize] = data;usedSize++;
}

單向鏈式棧實現思路：使用頭插法入棧，時間復雜度是O(1)

public void push(int data) {// 頭插法入棧ListNode toAdd = new ListNode(data);toAdd.next = head;head = toAdd;usedSize++;
}

雙向鏈式棧實現方式可以頭插也可以尾插。

public void push(int data) {// 頭插法ListNode toAdd = new ListNode(data);toAdd.next = head;head.prev = toAdd;head = head.prev;usedSize++;
}public void push(int data) {// 尾插法ListNode toAdd = new ListNode(data);tail.next = toAdd;toAdd.prev = tail;tail = tail.next;usedSize++;
}

然后是 pop方法，我們只需要將?usedSize 的個數減一即可。雖然元素在數組中仍然存在，但是不需要擔心，等到下次增加元素時，該元素將被覆蓋。

順序棧實現如下：

public int pop() {if (empty()) {throw new EmptyStackException("This stack is empty!");}usedSize--;return this.arr[usedSize];
}

單向鏈式棧：我們可以使用頭刪法，每次刪除并返回鏈表的第一個節點

public int pop() {if (empty()) {throw new EmptyStackException("This stack is empty!");}int val = head.val;head = head.next;usedSize--;return val;
}

雙向鏈式棧：與單向鏈式棧不同的是，我們需要把第二個節點的 prev 置空

public int pop() {if (empty()) {throw new EmptyStackException("This stack is empty!");}int val = head.val;head = head.next;head.prev = null;usedSize--;return val;
}

其中的異常編寫如下：

public class StackEmptyException extends RuntimeException {public StackEmptyException() {super();}public StackEmptyException(String message) {super(message);}
}

peek方法十分簡單，只需要返回 usedSize - 1 位置的元素即可，但是注意要判斷棧是否為空。

順序棧實現如下：

public int peek() {if (empty()) {throw new EmptyStackException("This stack is empty!");}return this.arr[usedSize-1];
}

單/雙向鏈式棧：直接返回鏈表第一個節點的 val 即可

public int peek() {if (empty()) {throw new EmptyStackException("This stack is empty!");}return head.val;
}

empty方法，只需判斷 usedSize 是否等于數組的長度即可。

順序棧實現如下：

public boolean empty() {return usedSize == this.arr.length;
}

單/雙向鏈式棧：判斷指向鏈表第一個節點的引用是否為空即可

public boolean empty() {if (head == null) return true;return false;
}

最簡單的是 size方法，只需要返回 usedSize 即可：

public int size() {return this.usedSize;
}

對于單/雙鏈式棧來說，需要遍歷整個棧：

public int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;
}

2.4 棧的實戰應用

棧相關的面試題：

2.4.1 括號匹配

算法實現思路：

遍歷字符串，如果是左括號，就放入棧中；如果是右括號，就獲取棧頂元素并進行匹配
情況一：當棧為空并且字符串遍歷完成，左右括號都匹配成功時，返回true；情況二：當左右括號匹配失敗時，返回false；情況三：當字符串遍歷完成但是棧不為空時，表示左括號多余，返回false；情況四：當字符串未遍歷完成但是棧已經空了，表示右括號多余，返回false。
注意：當遍歷字符串發現字符是右括號時，在匹配前必須先檢查棧是否為空：若不為空才進行匹配；若為空則是第四種情況

具體實現如下：

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch=='(' || ch=='[' || ch=='{') {stack.push(ch);} else {    // 此時 ch 是右括號if (stack.empty()) {       // 棧已空，右括號多余return false;}char leftCh = stack.peek();if ((leftCh=='(' && ch==')')|| (leftCh=='[' && ch==']')|| (leftCh=='{' && ch=='}')) {     // 匹配成功stack.pop();} else {               // 匹配失敗return false;}}}if (!stack.empty()) {       // 棧不為空但字符串已經遍歷完成，左括號多余return false;}return true;
}

2.4.2 逆波蘭表達式求值

算法實現思路：

遍歷，遇到數字就放入棧，遇到運算符就取出兩個棧頂數字并進行計算（第一個取出的數字作為右操作數，第二個作為左操作數），將計算結果放入棧
當遍歷完成后，棧中所存的元素就是該表達式的最終結果

中綴表達式轉后綴表達式（逆波蘭表達式）的計算方法：

先判斷中綴表達式的優先級，然后按照優先級依次在算式外部添加括號
全部添加完成后，從左至右依次將運算符移至括號后面
例：中綴表達式 a + b * c + ( d * e + f ) * g?
首先劃分優先級：
單項式( d * e ) ——> 多項式( ( d * e ) + f ) ——> 多項式( ( d * e ) + f ) * g ) ——> 單項式( b * c )?——> 多項式( a + ( b * c ) ) ——> 多項式（ ( a + ( b * c ) ) + ( ( d * e ) + f ) * g ) ）
然后按照優先級先后把運算符全部移到括號后面：
( ( a + ( b * c ) ) + ( ( ( d * e ) + f ) * g ) ) ——> (?( a ( b c ) * ) + ( ( ( d e ) * f ) + g ) * ) +
去掉所有的括號最終結果就是:
?a b c * + d e * f + g * +

具體實現如下：

public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String s : tokens) {if (s.equals("+")|| s.equals("-")|| s.equals("*")|| s.equals("/")) {    // 是運算符int v2 = stack.pop();   // 右操作符int v1 = stack.pop();   // 左操作符switch (s) {case "+":stack.push(v1+v2);break;case "-":stack.push(v1-v2);break;case "*":stack.push(v1*v2);break;case "/":stack.push(v1/v2);break;}} else {            // 是數字int val = Integer.parseInt(s);  // 轉換為整型stack.push(val);}}return stack.pop();
}

2.4.3 出棧入棧次序匹配

算法實現思路：

遍歷pushV數組并入棧，每次入棧一個元素之后拿棧頂元素與popV數組中的 j 位置的元素進行比較是否相等：若一樣，就可以出棧；否則，繼續遍歷pushV數組、入棧
一旦有一個元素相等，后面的所有元素均相等
當棧為空或者popV數組和pushV數組遍歷完成時，返回true

具體實現如下：

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

2.4.4 最小棧

算法實現思路：

使用兩個棧，一個普通棧（stack）存放所有的數據，一個最小棧（minStack）用于存放當前 stack 所存元素的最小值
入棧：當第一個元素放入 stack ，且 minStack 為空時，minStack 也要放。接下來 stack 存放元素后，都要與 minStack 的棧頂元素進行大小比較：若比棧頂元素小，就放入 minStack（注意：若與棧頂元素相等，也要放入）；否則不放入
出棧：當普通棧出一個元素時，判斷一下最小棧是否也有相同的元素：若有就出；否則不出

具體實現如下：

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

三、隊列（Queue）

3.1 隊列的基本概念

隊列是一種遵循先進先出（FIFO, First In First Out）原則的線性數據結構。只允許在隊尾進行插入操作，在隊頭進行刪除操作。

現實生活中的隊列例子：

排隊購票：先來的人先得到服務
打印機任務隊列：先提交的打印任務先執行

3.2 隊列的使用

在Java內置的Queue類中，提供了以下操作方法：

public void offer(int data)	入隊，即增加新元素
public int poll()	出隊，即刪除隊頭元素并返回該元素
public int peek()	獲取隊頭元素并返回，不刪除
public boolean isEmpty()	判斷隊列是否為空
public int size()	獲取隊列的大小

具體使用示例如下：

import java.util.LinkedList;
import java.util.Queue;public class QueueExample {public static void main(String[] args) {Queue<Integer> queue = new LinkedList<>();// 入隊操作queue.offer(1);queue.offer(2);queue.offer(3);// 查看隊頭元素System.out.println("隊頭元素: " + queue.peek()); // 輸出 1// 出隊操作System.out.println("出隊: " + queue.poll()); // 輸出 1System.out.println("出隊: " + queue.poll()); // 輸出 2// 判斷隊列是否為空System.out.println("隊列是否為空: " + queue.isEmpty()); // 輸出 false// 獲取隊列的元素個數System.out.println("隊列的長度: " + queue.size()); // 輸出 1}
}

3.3 隊列的模擬實現

由于Java的內置隊列 Queue 是采用雙向鏈表實現的，我們這里也使用雙向鏈表。各個方法的實現思路與棧的方法的實現思路差不多，此處不再過多闡述。

具體實現如下：

public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode first;public ListNode last;public int usedSize;public void offer(int data) {   // 尾插ListNode toAdd = new ListNode(data);if(first == null) {first = last = toAdd;return;}last.next = toAdd;toAdd.prev = last;last = last.next;usedSize++;}public int poll() {    // 頭刪if(first == null) {return -1;}int v = first.val;first = first.next;if (first != null) {first.prev = null;}usedSize--;return v;}public int peek() {     // 獲取隊頭的值if(first == null) {return -1;}return first.val;}public int size() {    // 獲取隊列的大小return usedSize;}
}

3.4 隊列的實戰應用

3.4.1 設計實現循環隊列

我們把一個數組卷起來呈圓形，以這樣的結構來實現的隊列稱為循環隊列。

當兩個引用 front? 和 rear 指向同一個位置（即 front == rear）時，該隊列為空。

它的方法如下：

public boolean enQueue(int value)	入隊，即增加新元素
public boolean deQueue()	出隊，即刪除隊頭元素并返回該元素
public int Front()	獲取隊頭元素并返回
public int Rear()	獲取隊尾元素并返回
public boolean isEmpty()	判斷隊列是否為空
public boolean isFull()	判斷隊列空間是否已滿

算法實現思路：

如何判斷隊列為空/隊列已滿？：當 front == rear
怎么區分為空還是為滿？：1.定義 usedSize；2.空出最后一個位置；3.添加一個布爾類型的變量作為標記
怎么做到循環遍歷隊列？即怎么讓 rear 從下標為7的位置走到下標為0的位置呢？：用公式( rear + 1 ) % array.length判斷 rear 的下一個是否 front
入隊列、出隊列、返回隊頭元素、返回隊尾元素（需要判斷 rear）

具體實現如下：

class MyCircularQueue {    // 這里采用的是第二種方法區分為空還是為滿public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {this.elem = new int[k+1];}public boolean enQueue(int value) {    // 入隊列if (isFull()) {return false;}elem[rear] = value;rear = (rear+1)%elem.length;return true;}public boolean deQueue() {    // 出隊列if (isEmpty()) {return false;}front = (front+1)%elem.length;return true;}public int Front() {    // 獲取隊頭元素if (isEmpty()) {return -1;}return elem[front];}public int Rear() {    // 獲取隊尾元素if (isEmpty()) {return -1;}int pos = (rear==0) ? elem.length-1 : rear-1;return elem[pos];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear+1)%elem.length == front;}
}

四、常見面試題與實戰應用

4.1 用隊列實現棧

算法實現思路（使用兩個隊列）：

模擬的入棧操作：將入棧的元素放入不為空的隊列中；
第一次入棧默認放入qu1中，接下來判斷哪個隊列不為空就放入哪個隊列中：if...else if...else
模擬的出棧操作：把不為空的隊列中的除要出棧的元素之外的（size-1）所有元素放入另一個隊列當中，再出隊列即可；先判斷棧是否為空，再判斷哪個隊列不為空就出哪個隊列
模擬的獲取棧頂元素操作：在出棧操作的基礎下（把全部元素都出），加一個變量存儲出隊列的元素，當最后一個出隊列的元素存儲后，該值就是模擬的棧頂元素
兩個隊列交替工作

具體實現如下：

public class MyStack {Queue<Integer> qu1;Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()) {qu2.offer(x);} else {qu1.offer(x);}}public int pop() {if (empty()) {return -1;}if (!qu1.isEmpty()) {int size = qu1.size();for (int i = 0; i < size-1; i++) {qu2.offer(qu1.poll());}return qu1.poll();} else {int size = qu2.size();for (int i = 0; i < size-1; i++) {qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {if (empty()) {return -1;}if (!qu1.isEmpty()) {int size = qu1.size();int val = 0;for (int i = 0; i < size; i++) {val = qu1.poll();qu2.offer(val);}return val;} else {int size = qu2.size();int val = 0;for (int i = 0; i < size; i++) {val = qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

4.2 用棧實現隊列

算法實現思路（使用兩個棧）：

指定一個棧用來入隊列，一個棧用來出隊列
模擬的入隊列操作：放入指定的入隊列棧中即可
模擬的出隊列操作：先判斷出隊列棧是否為空？：若為空，將入隊列棧中的元素放入出隊列棧中，再出棧即可；否則直接出棧
模擬的獲取隊頭元素操作：在出隊列操作下，直接peek出隊列棧的棧頂元素即可

具體實現如下：

public class MyQueue {Stack<Integer> st1;Stack<Integer> st2;public MyQueue() {st1 = new Stack<>();st2 = new Stack<>();}public void push(int x) {st1.push(x);}public int pop() {if (empty()) {return -1;}if (st2.isEmpty()) {while (!st1.isEmpty()) {st2.push(st1.pop());}}return st2.pop();}public int peek() {if (empty()) {return -1;}if (st2.isEmpty()) {while (!st1.isEmpty()) {st2.push(st1.pop());}}return st2.peek();}public boolean empty() {return st1.isEmpty() && st2.isEmpty();}
}