【Java】距離我上次知道堆疊和佇列有多簡單還是在上次

那么接下來，就讓我來講講道理!

引子

堆疊、佇列和線性表一樣都是一種線性的資料結構，各個元素之間呈線性關系，但是和一般的線性結構又存在著不同，

對堆疊所實施的操作限定在表尾，主要的操作為進堆疊、出堆疊、取堆疊頂的元素

對佇列所實施的操作限定在表頭和表尾，主要操作為表尾入隊、表頭出隊、表頭取對頭元素

一、堆疊

1.1 概念

堆疊的操作有先進后出的特點

在生活中這樣的例子到處都是，使用盤子時，總是會自上而下的取走盤子，洗盤子時，總是會自下而上的將盤子堆疊在一起，一摞厚厚的書，想要拿到壓在下面的書，比較安全的做法就是將上面的書一本一本的取走，再拿到想拿的書，再一本一本將書放在上面，

規律總結：無論是取盤子、書，放盤子、書，都只在最上端進行，遵循著后放入的先取出的原則

堆疊的使用就是如此，先進后出，后進先出，只允許在固定的一段進行插入元素（即入堆疊）洗掉元素（出堆疊），該端被稱為堆疊頂，那么另一端就為堆疊底，堆疊頂會一直隨著插入洗掉變化著，堆疊底一直固定不變，

1.2 實體

1.2.1 不可能的出堆疊順序

題目：
已知一個堆疊的入堆疊序列是 mnxyz ，則不可能出現的出堆疊順序是？

A.mnxyz B.xnyzm C.nymxz D.nmyzx

題解：

該題目的重點在于入堆疊后也可以直接又出堆疊

選項A: 顯而易見的，五個元素分別都入堆疊后又直接出堆疊，成立
選項B: mnx依次入堆疊，x出堆疊，n再出堆疊，y入堆疊后又出堆疊，z入堆疊后又出堆疊，m最后出堆疊，成立
選項C: mn依次入堆疊，n出堆疊，xy依次入堆疊，y出堆疊，下一個若是出堆疊必定是x而不是m，錯誤

選項D: mn依次入堆疊，n出堆疊，m出堆疊，xy依次入堆疊，y出堆疊，z入堆疊后出堆疊，x最后出堆疊，成立

答案：C

1.2.2 中綴運算式轉后綴運算式

運算式有三種不同的記法，即前綴、中綴、后綴運算式，我們日常生活中常用的運算式是中綴運算式，運算子在運算元的中間，前綴運算式的運算子在運算元的前面，后綴運算式的運算子在運算元的后面，

例如：

中綴運算式：(((2 + 3) * 4) - (6 / 2))

前綴運算式：- * + 2 3 4 / 6 2

后綴運算式: 2 3 + 4 * 6 2 / -

對于人們來說，中綴運算式的形式更易于計算，另外兩種沒有辦法一時間看出來寫的是什么

對于計算機來說不然，前綴、后綴運算式的計算更為簡單，因此在計算運算式的時候，計算機都會將中綴運算式轉化為前綴或后綴運算式

就拿中綴運算式轉后綴運算式為例，說一個最簡便的轉換方式：

1. 按照運算子的優先級依次加上()
2. 依次將運算子移動到對應的括號的后面（如果是轉換為前綴運算式的話則移動到括號前面）
3. 去掉括號，得到后綴運算式

以運算式((2 + 3) * 4)為例

圖解：

后綴運算式計算的方式：

1. 如果后綴運算式為數字，就依次入堆疊
2. 如果遇見運算子，就從堆疊中彈出一個數字放在運算子的右側，再彈出一個數字放在運算子的左側
3. 計算后，將計算結果入堆疊
4. 回圈往復，直到堆疊中沒有數字，就完成了整個計算程序

1.3 自我實作

可以用順序表的方式來實作堆疊，也可以用鏈表的方式來實作堆疊，相對而言，順序表的實作更加方便簡單，這里就用順序表來實作堆疊，

堆疊的順序存盤結構是指使用一組地址連續的存盤單元來依次存放自堆疊底到堆疊頂的資料元素，采用順序的存盤方式存盤的堆疊叫做順序堆疊，在這里實作這個堆疊的類 MyStack 就叫順序堆疊類

在此處，使用了一維陣列int[] elem來存盤堆疊中的資料元素，設定合適的初始長度；使用變數 usedSized 來記錄堆疊中的資料元素的個數，如果想要洗掉一個元素(出堆疊)，使其減一，如果想要入堆疊，使其加一，如果想要清空堆疊，就可以使其為0

實作方法：

• public MyStack()

  初始化陣列的長度

• public boolean isFull()

  當發現堆疊中的元素的個數和陣列的長度相等，代表堆疊滿，回傳 true，否則回傳 false

• public void push(int val)

  將資料元素val推入堆疊中，如果堆疊滿，則將實作堆疊的陣列進行擴容，再將資料元素放到陣列下標為 usedSized 的地方，陣列大小加一

• public boolean empty()

  判斷堆疊是否為空，當發現 usedSized 大小為0，回傳 true，否則回傳 false

• public int peek()

  如果堆疊不為空，則回傳堆疊頂的資料元素；如果為空，就報例外，提示“堆疊空了”

• public int pop()

  如果堆疊不為空，usedSized 大小減一，則洗掉堆疊頂的資料元素并將其回傳；如果為空，就報例外，提示“堆疊空了”

📑代碼示例：

import java.util.Arrays;
public class MyStack {
   public int[] elem;
   public int usedSized;
   //初始化
   public MyStack() {
       this.elem = new int[100];
   }
   //判斷堆疊是否滿
   public boolean isFull() {
       return (this.usedSized == this.elem.length);
   }    
   //入堆疊
   public void push(int val) {
       if (isFull()){
           this.elem = Arrays.copyOf(this.elem,this.elem.length*2);
       }
       this.elem[this.usedSized] = val;
       this.usedSized++;
   }
   //判斷堆疊是否為空
   public boolean empty() {
       return this.usedSized == 0;
   }
   //取堆疊頂元素
   public int peek() throws RuntimeException{
       if (empty()){
           throw new RuntimeException("堆疊空了");
       }
       return this.elem[this.usedSized-1];
   }
   //出堆疊
   public int pop() throws RuntimeException{
       if (empty()){
           throw new RuntimeException("堆疊空了");
       }
       this.usedSized--;
       return this.elem[this.usedSized - 1];
   }
}

二、佇列

1.1 概念

佇列的操作有先進先出的特點

和生活當中的排隊一樣，講究先來先服務先走，在排隊事件中，新成員加入到隊尾，每次離開的成員都是來自隊頭的，即隊尾入隊，隊頭出隊，

佇列的使用就是如此，先進先出，后進后出，佇列只限定在一端進行插入，該端叫隊尾，只限定在另一端洗掉，另一端叫隊頭，插入操作叫入隊，洗掉操作叫出隊，隨著插入和洗掉，佇列的隊頭和隊尾一直在發生改變，

a₁是隊頭元素，a_n是隊尾元素，佇列中的元素是以 a₁，a₂，a₃，…，a_n-1,a_n的順序進佇列的，按照佇列的概念，如果要執行入隊操作，入隊的元素為a_n+1，其變成隊尾，如果執行出隊操作，出隊的元素為a₁，此時隊頭為a₂，

1.2 實體

1.2.1 無法吃午餐的學生數量

題目：

學校的自助午餐提供圓形和方形的三明治，分別用數字0 和 1 表示，所有學生站在一個佇列里，每個學生要么喜歡圓形的要么喜歡方形的，
餐廳里三明治的數量與學生的數量相同，所有三明治都放在一個堆疊里，每一輪：

如果佇列最前面的學生喜歡堆疊頂的三明治，那么會 拿走它 并離開佇列，
否則，這名學生會放棄這個三明治并回到佇列的尾部，
這個程序會一直持續到佇列里所有學生都不喜歡堆疊頂的三明治為止，

給你兩個整數陣列 students 和 sandwiches ，其中 sandwiches[i] 是堆疊里面第 i 個三明治的型別（i = 0 是堆疊的頂部）， students[j] 是初始佇列里第 j 名學生對三明治的喜好（j = 0 是佇列的最開始位置），請你回傳無法吃午餐的學生數量，

力扣鏈接

題解：

如果將這道題用佇列的思想進行解決，那么就應該是這樣的，，，

步驟一：首先對學生陣列和三明治陣列進行判斷是否為空，增強代碼的健壯性

步驟二：將同學們對三明治的喜好放進一個佇列當中

步驟三：進入一個回圈，條件就是學生的佇列不為空，三明治陣列的長度不可超過(本題目三明治的數量與學生的數量相同，該條件一定會成立，所以該條件針對數量不同的情況)

步驟四：在上述的回圈當中進行回圈判斷，如果輪的程序中喜好匹配成功，就將隊頭的學生喜好送走，三明治陣列的 j 下標向后走一格，若學生隊頭和三明治陣列的 j 下標的元素不同，就將其從隊頭送走，送到隊尾去，佇列中所有成員都輪了一遍，都沒人領走三明治，就說明此時佇列的大小就是沒飯吃的學生數目

步驟五：回圈走完了，仍然沒有回傳，在本題的條件下，佇列一定為空了，如果三明治的數量與學生的數量不相同的話，也可能是因為三明治數量少了，佇列的大小就是沒飯吃的學生數目

圖解舉例：

📑代碼示例：

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        //對學生陣列和三明治陣列進行判斷是否為空
        if (students == null || students.length == 0) return 0;
        if (sandwiches == null || sandwiches.length == 0) return students.length;
        //將同學們對三明治的喜好放進一個佇列當中
        Queue<Integer> queue1 = new LinkedList<>();
        for (int i = 0; i < students.length; i++) {
            queue1.add(students[i]);
        }
        int j = 0;
        while (!queue1.isEmpty() && j < sandwiches.length) {
            int i = 0;
            for (; i < queue1.size(); i++) {
                //學生隊頭和三明治陣列的 j 下標的元素不同，就將其從隊頭送走，送到隊尾去
                if (queue1.peek() != sandwiches[j]) {
                    queue1.add(queue1.poll());
                }else {
                    //喜好匹配成功
                    break;
                }
            }
            //佇列所有成員都輪了一遍，此時佇列的大小就是沒飯吃的學生數目
            if (i == queue1.size()) {
                return queue1.size();
            }
            //喜好匹配成功，就將隊頭的學生喜好送走，三明治陣列的 j 下標向后走一格
            queue1.poll();
            j++;
        }
        //回傳佇列的大小
        return queue1.size();
    }
}

1.3 自我實作

由于佇列先進先出的特點，如果要用普通的一維陣列來實作佇列，當想要在隊尾插入元素時，時間復雜度為O(1)，但是當在隊頭洗掉元素的時候，由于下標為0的元素被移走了，就意味著后面的元素都要集體向前移動一格，時間復雜度為O(N)

因此采取鏈式存盤結構比采取順序存盤結構更為有利，這里我們將使用鏈表來實作佇列，可以使用雙向鏈表，也可以使用單鏈表，在這里我們就將使用單鏈表來實作一個佇列，定義一個 front 節點來記錄鏈表的頭即隊頭，定義一個 rear 節點來記錄鏈表的尾即隊尾

鏈式佇列的操作實際上就是單鏈表的插入和洗掉的一種特殊情形，入隊操作相當于從鏈尾插入一個資料元素，出隊操作相當于從鏈頭洗掉一個資料元素，入隊和出隊操作均可以通過修改 front 節點和 rear 節點的指向來實作，

實作圖例：

實作方法：

• public void offer(int val)

  在鏈佇列中插入新的隊尾元素 val，

  步驟一：生成一個元素值為 val 的新節點 newNode

  步驟二：判斷鏈佇列是否為空，若為空使頭結點 front 指向新節點，若不為空，則需要使尾節點 rear 的參考域指向新節點

  步驟三：使尾節點指向新節點

  步驟四：鏈佇列的元素個數 usedSize 加一

• public int poll()

  若鏈佇列為空，拋出一個"佇列為空"的例外；若不為空，就從佇列中取出隊頭元素并回傳

  步驟一：判斷是否佇列為空，為空拋例外

  步驟二：定義變數 ret 來記錄此時隊頭元素資料域的值

  步驟三：若此時只有一個節點，就將頭結點和尾節點都設定為 null，若不止一個節點，就使頭結點 front 指向其指向的下一個元素，即洗掉了隊頭的節點

  步驟四：鏈佇列的元素個數 usedSize 減一

  步驟五：回傳 ret

• public int peek()

  若鏈佇列為空，拋出一個"佇列為空"的例外；若不為空，就從佇列中回傳隊頭元素

  步驟一：判斷是否佇列為空，為空拋例外

  步驟二：回傳頭結點 front 此時指向的隊頭元素資料域的值

• public boolean isEmpty()

  判斷鏈佇列是否為空，為空時 usedSize 為 0

• public int size()

  回傳鏈佇列的長度

📑代碼示例：

class Node {
    public int data;
    public Node next;

    public Node(int data) {
        this.data = data;
    }
}
public class MyQueueLinked {
    //未初始化時，默認front 和 rear 都指向 null，usedSize 為 0
    private Node front;
    private Node rear;
    private int usedSize;
	//入佇列
    public void offer(int val) {
        Node newNode = new Node(val);
        if (isEmpty()){
            this.front = newNode;
        }else {
            this.rear.next = newNode;
        }
        this.rear = newNode;
        this.usedSize++;
    }
	//出佇列
    public int poll() throws RuntimeException{
        //判斷佇列是否為空
        if (isEmpty()) {
            throw new RuntimeException("佇列為空");
        }
        int ret = this.front.data;
        //判斷是否為一個節點
        if (this.front.next == null) {
            this.front = null;
            this.rear = null;
        }else {
            this.front = this.front.next;
        }
        this.usedSize--;
        return ret;
    }
    //取隊頭元素
    public int peek() throws RuntimeException{
        //判斷佇列是否為空
        if (isEmpty()) {
            throw new RuntimeException("佇列為空");
        }
        return this.front.data;
    }
    //判斷鏈佇列是否為空
    public boolean isEmpty() {
        return this.usedSize == 0;
    }
    //回傳鏈佇列的長度
    public int size() {
        return this.usedSize;
    }
}

1.4 雙端佇列(deque)

顧名思義就是指允許兩端都可以進行入隊和出隊操作的佇列，那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊，

事實上，經過上面的佇列的實作，雙端佇列的實作方法基本差不多，為方便起見，此處采用雙向鏈表的思想來實作雙端佇列，在此就話不多說，上代碼！

📑代碼示例：

class Node {
    public int data;
    public Node next;
    public Node prev;

    public Node(int data) {
        this.data = data;
    }
}
class MyDeque {
    public Node head;//記錄佇列的隊頭
    public Node rear;//記錄佇列的隊尾
    public int usedSized;//佇列中的元素個數
    public int capacity;//佇列的容量大小
	//初始化佇列的容量大小
    public MyDeque(int k) {
        this.capacity = k;
    }
	//將一個元素添加到雙端佇列頭部,如果操作成功回傳 true
    public boolean insertFront(int value) {
        Node newNode = new Node(value);
        if (isFull()) {
            return false;
        }
        if (!isEmpty()) {
            newNode.next = this.head;
            this.head.prev = newNode;
        }else {
            this.rear = newNode;
        }
        this.head = newNode;
        this.usedSized++;
        return true;
    }
	//將一個元素添加到雙端佇列尾部,如果操作成功回傳 true
    public boolean insertLast(int value) {
        Node newNode = new Node(value);
        if (isFull()) {
            return false;
        }
        if (!isEmpty()) {
            this.rear.next = newNode;
            newNode.prev = this.rear;
        }else {
            this.head = newNode;
        }
        this.rear = newNode;
        this.usedSized++;
        return true;
    }
	//從雙端佇列頭部洗掉一個元素,如果操作成功回傳 true
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        //如果雙端佇列中只有一個節點
        if (this.head == this.rear) {
            this.head = null;
            this.rear = null;
        }else {
            this.head = this.head.next;
        }
        this.usedSized--;
        return true;
    }
	//從雙端佇列尾部洗掉一個元素,如果操作成功回傳 true
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        //如果雙端佇列中只有一個節點
        if (this.head == this.rear) {
            this.head = null;
            this.rear = null;
        }else {
            this.rear = this.rear.prev;
        }
        this.usedSized--;
        return true;

    }
	//從雙端佇列頭部獲得一個元素,如果雙端佇列為空,回傳 -1
    public int getFront() {
        if (isEmpty()) return -1;
        return this.head.data;
    }
	//從雙端佇列尾部獲得一個元素,如果雙端佇列為空,回傳 -1
    public int getRear() {
        if (isEmpty()) return -1;
        return this.rear.data;
    }
	//檢查雙端佇列是否為空，標準為雙端佇列中的資料元素個數等于0
    public boolean isEmpty() {
        return this.usedSized == 0;
    }
	//檢查雙端佇列是否滿了,標準為雙端佇列中的資料元素個數等于佇列容量
    public boolean isFull() {
        return this.usedSized == this.capacity;
    }
}

三、Java中的堆疊和佇列

Java 中可以直接使用堆疊和佇列，具體方法如下

3.1 Java中的堆疊

📑代碼示例：

import java.util.Stack;
public class TestDemo {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(2);
        stack.push(4);
        System.out.println(stack.peek());//4
        System.out.println(stack.pop());//4
        System.out.println(stack.empty());//false
    }
}

3.2 Java 中的佇列

📑代碼示例：

import java.util.LinkedList;
import java.util.Queue;
public class TestDemo {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(4);
        queue.offer(5);
        System.out.println(queue.element());//4
        System.out.println(queue.peek());//4
        System.out.println(queue.remove());//4
        System.out.println(queue.poll());//5
        System.out.println(queue.isEmpty());//true
    }
}

說明：

使用 LinkedList 來實作佇列，方式一和方式二都能實作所需方法，不一樣的是當遇見錯誤的時候，方式一會拋出例外，方式二會回傳特殊值

3.3 Java 中的雙端佇列

📑代碼示例：

import java.util.Deque;
import java.util.LinkedList;
public class TestDemo {
    public static void main(String[] args) {
        Deque<Integer> deQueue = new LinkedList<>();
        deQueue.addFirst(2);
        deQueue.addLast(3);
        deQueue.offerFirst(4);
        deQueue.offerLast(5);
        System.out.println(deQueue.removeFirst());//4
        System.out.println(deQueue.peekLast());//5
        System.out.println(deQueue.pollLast());//5
        System.out.println(deQueue.getFirst());//2
        System.out.println(deQueue.isEmpty());//false
    }
}

說明：

使用 LinkedList 來實作佇列，方式一和方式二都能實作所需方法，不一樣的是當遇見錯誤的時候，方式一會拋出例外，方式二會回傳特殊值

完！