堆疊和佇列

1. 堆疊(Stack)
- 1.1 概念
- 1.2 實作
2. 佇列(Queue)
- 2.1 概念
- 2.2 實作
- 2.3 回圈佇列
3. 雙端佇列 (Deque)
- 3.1 概念
4. java 中的堆疊和佇列
5. LeetCode 題目
- 第一題 : 有效的括號
- - 解題思路:
  - 畫圖決議:
  - 代碼實作:
- 第二題 : 用佇列實作堆疊
- - 解題思路:
  - 畫圖決議:
  - 代碼實作:
- 第三題 : 用堆疊實作佇列
- - 解題思路:
  - 畫圖決議:
  - 代碼實作:
- 第四題 : 最小堆疊
- - 解題思路:
  - 畫圖決議:
  - 代碼實作:
- 第五題 : 設計回圈佇列
- - 解題思路:
  - 畫圖決議:
  - 代碼實作:
- 第六題 : 逆波蘭運算式求值(后綴運算式)
- - 解題思路:
  - 畫圖決議:
  - 代碼實作:

1. 堆疊(Stack)

1.1 概念

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，

壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料在堆疊頂，
在這里插入圖片描述
Stack的Push和Pop遵循先進后出的原則,如圖:

1.2 實作

利用順序表實作，即使用尾插 + 尾刪的方式實作
利用鏈表實作，則頭尾皆可.
頭插法: 入堆疊O(1) 出堆疊O(1)
尾插法: 入堆疊O(N) 出堆疊O(N)

相對來說，順序表的實作上要更為簡單一些，所以我們優先用順序表實作堆疊，

public class MyStack {
    //簡單的實作,使用int元素即可,也不考慮擴容問題
    private int[] elem = new int[100];
    private int usedSize = 0;// 堆疊中存在多少個有效元素
    
    //入堆疊
    public void push(int val){
        elem[usedSize] = val;
        usedSize++;
    }
    
    //取堆疊頂元素(最后進來的那個元素)
    public int peek(){
        return elem[usedSize - 1];
    }
    
    //出堆疊
    public int pop(){
        int ret = elem[usedSize - 1];
        usedSize--;
        return ret;
    }
}

2. 佇列(Queue)

2.1 概念

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(FirstIn First Out) 入佇列：進行插入操作的一端稱為隊尾（Tail/Rear） 出佇列：進行洗掉操作的一端稱為隊頭（Head/Front）
在這里插入圖片描述

2.2 實作

佇列也可以陣列和鏈表的結構實作，使用鏈表的結構實作更優一些，因為如果使用陣列的結構，出佇列在陣列頭上出資料，效率會比較低，
在這里插入圖片描述

public class MyQueueByLinkedList {
    /**
     * Node這個類叫做"內部類",定義在某個類或者方法中的類
     * static 效果就是: 創建Node的實體不依賴 MyQueueByLinkedList 這個類的實體
     */
    static class Node{
        public int val;
        Node next = null;

        public Node(int val){
            this.val = val;
        }
    }

    // 創建一個鏈表,就得有頭節點.此處的head節點不是傀儡節點.
    // 基于鏈表來實作佇列,可以入佇列可以從尾巴插入,出佇列從頭部洗掉;
    // 也可以入佇列從頭部插入,出佇列從尾部洗掉
    // 無論是那種實作方式,最好都把頭和尾都記錄下來.
    private Node head = null;
    private Node tail = null;

    // 入佇列(標準庫的佇列,入佇列操作就叫 offer)
    public void offer(int val) {
        Node newNode = new Node(val);
        if(head == null){
            head = newNode;
            tail = newNode;
            return;
        }
        //如果非空
        tail.next = newNode;
        tail = newNode;
    }

    // 出佇列
    public Integer poll(){
        // 如果當前佇列就是空佇列,再去poll顯然不科學
        if(head == null){
            // 如果出佇列失敗,回傳一個錯誤的值
            return null;
        }
        int ret = head.val;
        head = head.next;
        if(head == null){
            //洗掉當前元素之后,佇列變成了空的佇列
            tail = null;

        }
        return ret;
    }

    // 取隊首的元素
    public Integer peek() {
        if(head == null){
            return null;
        }
        return head.val;
    }
}

2.3 回圈佇列

實際中我們有時還會使用一種佇列叫回圈佇列，如作業系統課程講解生產者消費者模型時可以就會使用回圈佇列，
環形佇列通常使用陣列實作，
在這里插入圖片描述

public class MyQueueByArray {
    private int[] elem = new int[100];
    // [head,tail) 有效元素的范圍. 注意, tail 可能在 head 之前
    private int head = 0; // 表示對首元素下標
    private int tail = 0; // 表示對尾下一個元素的下標
    private int size = 0; // 元素個數

    public void offer(int val){
        if (size == elem.length) {
            //佇列滿了, 無法繼續插入
            return ;
        }
        // 保證這個操作下標不能越界
        elem[tail] = val;
        tail++;
        // tail ++ 之后如果超出陣列有效范圍,就從頭開始
        if (tail >= elem.length){
            tail = 0;
        }
        size++;
    }

    public Integer poll(){
        if (size == 0){
            return null;
        }
        Integer ret = elem[head];
        head++;
        if(head >= elem.length){
            head = 0;
        }
        size--;
        return ret ;
    }

    public Integer peek(){
        if(size == 0){
            return null;
        }
        return elem[head];
    }
}

3. 雙端佇列 (Deque)

3.1 概念

雙端佇列（deque) 是指允許兩端都可以進行入隊和出隊操作的佇列，deque 是 “double ended queue” 的簡稱，
那就說明元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊，

4. java 中的堆疊和佇列

Stack

方法	解釋
E push(E item)	壓堆疊
E pop()	出堆疊
E peek()	查看堆疊頂元素
boolean empty()	判斷堆疊是否為空

Stack方法的演示:

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        //壓堆疊
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        //查看堆疊頂元素
        System.out.println(stack.peek());

        //出堆疊
        int ret = stack.pop();
        System.out.println(ret);  //4
        ret = stack.pop();
        System.out.println(ret);  //3
        ret = stack.pop();
        System.out.println(ret);  //2
        ret = stack.pop();
        System.out.println(ret);  //1
        //判斷堆疊是否為空
        System.out.println(stack.empty());
        //此時堆疊為空 如果 查看堆疊頂元素 或者 出堆疊 會報例外(EmptyStackException)
        System.out.println(stack.peek());
        System.out.println(stack.pop());
    }

運行結果:
在這里插入圖片描述

Queue

錯誤處理	拋出例外	回傳特殊值
入佇列	add(e)	offer(e)
出佇列	remove()	poll()
隊首元素	element()	peek()

Deque

頭部/尾部	頭部元素（隊首）		尾部元素（隊尾）
錯誤處理	拋出例外	回傳特殊值	拋出例外	回傳特殊值
入佇列	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
出佇列	removeFirst()	pollFirst()	removeLast()	pollLast()
獲取元素	getFirst()	peekFirst()	getLast()	peekLast()

總結:
Stack:
push ,pop,peek.當當前是一個空堆疊的,再去pop或者peek就會產生例外.
Queue:
add,remove,element 如果當前操作失敗就會拋出例外;
offer,poll,peek 如果操作失敗就會回傳一個錯誤值;

5. LeetCode 題目

第一題 : 有效的括號

有效的括號
LeetCode 20:
描述:
給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，
有效字串需滿足：

左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，

解題思路:

1. 遍歷字串,依次取出字串中的字符.
1.1 如果取出的字串為左括號例如’(’,’[’,’{’.就放入堆疊中
1.2 如果取出的字串為右括號例如’)’,’]’,’}’.就和堆疊頂元素比較是否匹配.
a) 匹配就出堆疊,然后繼續遍歷.
b) 不匹配就直接回傳false
1.3 如果堆疊為空,且取出的字符是右括號,則回傳false沒有例如字串"]()"
2. 遍歷結束后,判斷是否堆疊為空
2.1 如果為空則滿足題意 return true;
2.2 如果不為空表示沒有足夠匹配的字符, return false; 如字串"["

畫圖決議:

在這里插入圖片描述

代碼實作:

    public boolean isValid(String str) {
        Map<Character,Character> map = new HashMap<>();
        map.put('(',')');
        map.put('[',']');
        map.put('{','}');

        //1.先創建一個堆疊,堆疊中保存字符型別即可
        Stack<Character> stack = new Stack<>();
        //2.遍歷字串的每個字符
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            //3.判斷字符 ch 是否為左括號,如果是,就入堆疊
            if (ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
                continue;//進入下次回圈,取出下一個字符
            }
            if(stack.empty()){
                //如果ch不是左括號,且堆疊為空,則不是合法括號
                return false;
            }
            //4.判斷ch是否是右括號,如果是,就取堆疊頂元素比較是否相等
            char top = stack.pop();//堆疊頂元素
            //以下是3種情況合法情況 -- 寫法1
            /*if(top == '(' && ch == ')') {
                continue;
            }
            if(top == '[' && ch == ']') {
                continue;
            }
            if(top == '{' && ch == '}') {
                continue;
            }*/
            // 判斷合法情況 -- 寫法2
            if(map.get(top) == ch){
                continue;
            }
            //如果三種情況都不滿足,表示不是合法情況
            return false;
        }
        //遍歷完成后 如果堆疊為空 則滿足條件
        if(stack.empty()) {
            return true;
        }
        //否則就不合法
        return false;
    }

第二題 : 用佇列實作堆疊

用佇列實作堆疊
LeetCode 225:
描述:
請你僅使用兩個佇列實作一個后入先出（LIFO）的堆疊，并支持普通堆疊的全部四種操作（push、top、pop 和 empty），
實作 MyStack 類：

void push(int x) 將元素 x 壓入堆疊頂，
int pop() 移除并回傳堆疊頂元素，
int top() 回傳堆疊頂元素，
boolean empty() 如果堆疊是空的，回傳 true ；否則，回傳 false ，

注意：

你只能使用佇列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作，
你所使用的語言也許不支持佇列，你可以使用 list （串列）或者 deque（雙端佇列）來模擬一個佇列 , 只要是標準的佇列操作即可，

解題思路:

1. 用兩個佇列來模擬一個堆疊的效果,參考兩個佇列 A 和 B .
2. 入堆疊 : 直接把元素入隊到A中即可
3. 出堆疊 : 因為佇列是先進先出的,堆疊是后進先出的,可以讓 A佇列元素出佇列然后入佇列到 B佇列中,直到A佇列中最后一個元素的時候,直接出佇列,就實作了后進先出.然后要讓A和B交換,始終讓入堆疊到A佇列中.
4. 取堆疊頂元素 : 取堆疊頂元素就是出堆疊的元素, 不過取堆疊頂元素要把這個元素回傳去
5. 判斷是否為空 : A 和 B都為空的時候就是空堆疊

畫圖決議:

1NETiBAd3d6enp6enp6enp6enp6,size_20,color_FFFFFF,t_70,g_se,x_16)

代碼實作:

import java.util.LinkedList;
import java.util.Queue;

public class MyStackByDoubleQueue {
    private Queue<Integer> A = new LinkedList<>();
    private Queue<Integer> B = new LinkedList<>();

    public void push(int x) {
        // x往A中入佇列即可
        A.offer(x);
    }

    public Integer pop() {
        if (empty()){
            return null;
        }
        // 把A中的元素往 B 中放
        while(A.size() > 1) {
            Integer font = A.poll();
            B.offer(font);
        }
        //當回圈結束后,A 中 應該只剩1個元素
        //這個元素就應該是被出堆疊的元素
        int ret = A.poll();
        //交換A和B
        swapAB();
        return ret;
    }

    private void swapAB(){
        Queue<Integer> tmp = A;
        A = B;
        B = tmp;
    }

    public Integer top() {
        if (empty()){
            return null;
        }
        // 把A中的元素往 B 中放
        while(A.size() > 1) {
            Integer font = A.poll();
            B.offer(font);
        }
        //當回圈結束后,A 中 應該只剩1個元素
        //這個元素就應該是被出堆疊的元素
        int ret = A.poll();
        B.offer(ret); // top 和 pop的區別就是 top要把元素回傳去,pop不需要回傳去
        //交換A和B
        swapAB();
        return ret;
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

第三題 : 用堆疊實作佇列

用堆疊實作佇列
LeetCode 232:
描述:
請你僅使用兩個堆疊實作先入先出佇列，佇列應當支持一般佇列支持的所有操作（push、pop、peek、empty）：
實作 MyQueue 類：

void push(int x) 將元素 x 推到佇列的末尾
int pop() 從佇列的開頭移除并回傳元素
int peek() 回傳佇列開頭的元素
boolean empty() 如果佇列為空，回傳 true ；否則，回傳 false

解題思路:

1. 參考2個堆疊A和B,A專門用來入佇列;B專門用來出佇列
2. 實作入佇列: 先把B中的所有元素都放到A中(因為出堆疊的時候元素會放入B中),然后直接往A里入堆疊.
3. 實作出佇列: 后進先出的堆疊實作先進先出的佇列,要讓A中的所有元素移入B中,先出的的元素就是后進的,此時堆疊頂就是就是最先進入的元素,B中出堆疊操作即可
4. 實作取隊首元素: 同出佇列操作,把A所有元素放入B中,然后取B的堆疊頂元素就是隊首元素.
5. 判空: A 和 B 都為空.

畫圖決議:

在這里插入圖片描述

代碼實作:

import java.util.Stack;

public class MyQueueByDoubleStack {
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();

    public void push(int x) {
        //1.先將B中的元素 放入 A 中
        while (!B.isEmpty()){
            int tmp = B.pop();
            A.push(tmp);
        }
        //2.把新元素放入A中
        A.push(x);
    }


    public Integer pop() {
        //1.如果為空 直接回傳
        if(empty()){
            return null;
        }
        //2.把A中的元素都給B
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.針對B進行出堆疊
        return B.pop();
    }

    public Integer peek() {
        //1.如果為空 直接回傳
        if(empty()){
            return null;
        }
        //2.把A中的元素都給B
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.取B的堆疊頂元素
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

第四題 : 最小堆疊

最小堆疊
LeetCode 155:
設計一個支持 push ，pop ，top 操作，并能在常數時間內檢索到最小元素的堆疊，

push(x) —— 將元素 x 推入堆疊中，
pop() —— 洗掉堆疊頂的元素，
top() —— 獲取堆疊頂元素，
getMin() —— 檢索堆疊中的最小元素，

解題思路:

1. 參考2個堆疊A和B, A按照正常堆疊的規則入堆疊出堆疊,B存放的是A的最小值以及A歷史的最小值
2. 實作入堆疊操作: A中: 直接入堆疊 . B中: 取要入堆疊的值和 B堆疊頂元素比較,把較小值入堆疊到B中.
3. 實作出堆疊操作: A 和 B 一起出堆疊
4. 實作取堆疊頂元素操作: 直接取 A 堆疊頂元素
5. 實作取最小值操作: 直接取 B 堆疊頂元素

畫圖決議:

在這里插入圖片描述

代碼實作:

import java.util.Stack;

public class MinStack {
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();

    public void push(int x){
        //A 直接入堆疊
        A.push(x);
        //如果B為空 直接入堆疊
        if(B.isEmpty()){
            B.push(x);
            return;
        }
        //如果B不為空,比較x和B堆疊頂的較小值,將較小值入堆疊
        int min = B.peek();
        min = min < x ? min : x;
        B.push(min);
    }

    public Integer pop(){
        //如果A為空 直接回傳
        if(A.isEmpty()){
            return null;
        }
        //B和A同時出堆疊
        B.pop();
        return A.pop();
    }

    public Integer top(){
        //如果A為空 直接回傳
        if(A.isEmpty()){
            return null;
        }
        return A.peek();
    }

    public Integer getMin(){
        //如果B為空 直接回傳
        if(B.isEmpty()){
            return null;
        }
        //B的堆疊頂即使最小元素
        return B.peek();
    }

}

第五題 : 設計回圈佇列

設計回圈佇列
LeetCode 622:
描述:
設計你的回圈佇列實作，回圈佇列是一種線性資料結構，其操作表現基于 FIFO（先進先出）原則并且隊尾被連接在隊首之后以形成一個回圈，它也被稱為“環形緩沖器”，

回圈佇列的一個好處是我們可以利用這個佇列之前用過的空間，在一個普通佇列里，一旦一個佇列滿了，我們就不能插入下一個元素，即使在佇列前面仍有空間，但是使用回圈佇列，我們能使用這些空間去存盤新的值，

你的實作應該支持如下操作：

MyCircularQueue(k): 構造器，設定佇列長度為 k ，
Front: 從隊首獲取元素，如果佇列為空，回傳 -1 ，
Rear: 獲取隊尾元素，如果佇列為空，回傳 -1 ，
enQueue(value): 向回圈佇列插入一個元素，如果成功插入則回傳真，
deQueue(): 從回圈佇列中洗掉一個元素，如果成功洗掉則回傳真，
isEmpty(): 檢查回圈佇列是否為空，
isFull(): 檢查回圈佇列是否已滿，

解題思路:

1. 回圈佇列運用陣列實作. head和tail是下標,head位置始終都是隊首的元素;tail位置始終都是隊尾的下一個元素有效元素個數[ head, tail) 左閉右開
2. 入佇列 : 把新元素放到 tail 位置上,同時 tail++.
3. 出佇列 : 取出 head 位置的元素,同時 head++.
4. 空佇列 : 有效元素個為0
5. 滿佇列 : 有效元素個數等于陣列長度
6. 注意當head 和 tail達到元素上線時,回到最開始的位置.

畫圖決議:

在這里插入圖片描述

代碼實作:

public class MyCircularQueue {
    private int[] elem;
    private int head = 0;//隊首元素下標
    private int tail = 0;//隊尾下一個元素下標
    private int size = 0;//有效元素個數

    /**
     * 構造器，設定佇列長度為 k ，
     * @param k 佇列長度
     */
    public MyCircularQueue(int k) {
        this.elem = new int[k];
    }

    /**
     * 向回圈佇列插入一個元素，如果成功插入則回傳真，
     * @param value 插入元素
     * @return
     */
    public boolean enQueue(int value) {
        //隊滿就無法入隊 回傳false
        if(size == elem.length){
            return false;
        }
        elem[tail] = value;
        tail++;
        //tail>=佇列長度 要歸零
        if(tail >= elem.length){
            tail = 0;
        }
        size++;
        return true;
    }

    /**
     * 從回圈佇列中洗掉一個元素，如果成功洗掉則回傳真，
     * 隊頭出
     * @return
     */
    public boolean deQueue() {
        //如果佇列為空 沒有要洗掉的回傳false
        if(size == 0){
            return false;
        }
        head++;
        //head>=佇列長度 要歸零
        if(head >= elem.length){
            head = 0;
        }
        size--;
        return true;
    }

    /**
     * 從隊首獲取元素，如果佇列為空，回傳 -1 ，
     * @return
     */
    public int Front() {
        if(size == 0){
            return -1;
        }
        return elem[head];
    }

    /**
     * 獲取隊尾元素，如果佇列為空，回傳 -1 ，
     * @return
     */
    public int Rear() {
        if(size == 0){
            return - 1;
        }
        if(tail==0) return elem[elem.length - 1];
        return elem[tail-1];
    }

    /**
     * 檢查回圈佇列是否為空，
     * @return
     */
    public boolean isEmpty() {
        if(size == 0){
            return true;
        }
        return false;
    }

    /**
     * 檢查回圈佇列是否已滿
     * @return
     */
    public boolean isFull() {
        if(size == elem.length){
            return true;
        }
        return false;
    }

}

第六題 : 逆波蘭運算式求值(后綴運算式)

后綴運算式
逆波蘭運算式求值
LeetCode 150:
劍指 Offer Ⅱ 036:
描述:
根據逆波蘭表示法，求運算式的值，

有效的算符包括+、-、*、/，每個運算物件可以是整數，也可以是另一個逆波蘭運算式，

說明：
整數除法只保留整數部分，
給定逆波蘭運算式總是有效的，換句話說，運算式總會得出有效數值且不存在除數為 0 的情況，

解題思路:

1. 中綴記法是一個通用的算識訓邏輯公式表示方法,中綴運算式如3 + 4
前綴運算式如+ 3 4 , 后綴運算式如3 4 +. 前綴和后綴運算式都表示3+4
2. 用堆疊解決逆波蘭運算式, 遍歷字符陣列
① 如果為數字入堆疊
② 如果為 +、-、*、/出堆疊兩個數字完成對應操作,然后將得到的資料入堆疊
3. 注意完成對應 +、-、*、/操作時,是后一個出堆疊的資料 +、-、*、/ 前一個出堆疊的資料

畫圖決議:

在這里插入圖片描述

代碼實作:

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        //遍歷
        for (int i = 0; i < tokens.length; i++) {
            if("+".equals(tokens[i])){
                // '+' 運算
                stack.push(stack.pop() + stack.pop());
            }else if ("-".equals(tokens[i])){
                // '-' 運算
                stack.push(-stack.pop() + stack.pop());
            }else if ("/".equals(tokens[i])){
                // '/' 運算 
                int m = stack.pop();
                int n = stack.pop();
                stack.push(n / m);
            }else if ("*".equals(tokens[i])){
                // '*' 運算
                stack.push(stack.pop() * stack.pop());
            }else{
                // 不是運算子 直接入堆疊
                stack.push(Integer.valueOf(tokens[i]));
            }
        }
        //遍歷結束 出堆疊即是結果
        return stack.pop();
    }

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/374751.html

標籤：java

上一篇：面試官：說說你了解幾種限流演算法，手寫個demo?

下一篇：【MySQL 資料庫進階】面試官常問索引+事務+JDBC

資料結構 Java資料結構 堆疊和佇列 以及LeetCode相關面試題

堆疊和佇列

1. 堆疊(Stack)

1.1 概念

1.2 實作

2. 佇列(Queue)

2.1 概念

2.2 實作

2.3 回圈佇列

3. 雙端佇列 (Deque)

3.1 概念

4. java 中的堆疊和佇列

5. LeetCode 題目

第一題 : 有效的括號

解題思路:

畫圖決議:

代碼實作:

第二題 : 用佇列實作堆疊

解題思路:

畫圖決議:

代碼實作:

第三題 : 用堆疊實作佇列

解題思路:

畫圖決議:

代碼實作:

第四題 : 最小堆疊

解題思路:

畫圖決議:

代碼實作:

第五題 : 設計回圈佇列

解題思路:

畫圖決議:

代碼實作:

第六題 : 逆波蘭運算式求值(后綴運算式)

解題思路:

畫圖決議:

代碼實作:

資料結構 Java資料結構堆疊和佇列以及LeetCode相關面試題