Java 棧與佇列超詳細分析講解

2022-04-02 19:01:33

一、棧（Stack）

1、什麼是棧？

棧其實就是一種資料結構 - 先進後出（先入棧的資料後出來，最先入棧的資料會被壓入棧底）

什麼是java虛擬機器器棧？

java虛擬機器器棧只是JVM當中的一塊記憶體，該記憶體一般用來存放例如：區域性變數當呼叫函數時，我們會為函數開闢一塊記憶體，叫做棧幀，在 java虛擬機器器棧中開闢，具體如下。

常見考點：不可能的出棧順序

這道題該怎麼分析呢？

首先我們知道，出棧時拿到的第一個元素為4，那麼4必須入棧，因為入棧的順序是 1 2 3 4 5 6，所以4要入棧，1 2 3 得先入棧。（通過後面分析得知，該出棧序列正確）

2、棧的常見方法

方法	作用
E push(E item)	放入元素
E pop()	獲取棧頂元素並彈出
E peek()	獲取棧頂元素
boolean isEmpty()	判斷棧是否為空（父類別Vector的方法）

3、自己實現一個棧（底層用一個陣列實現）

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[4];
    }

    // 放入元素
    public void push(int val) {
        if(isFull()) {
            // 如果放滿了，二倍擴容
            this.elem = Arrays.copyOf(elem,2 * elem.length);
        }
        this.elem[this.usedSize++] = val;
    }
    // 獲取棧頂元素並彈出
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("棧為空！");
        }
        usedSize--;
        return elem[usedSize];
    }
    // 獲取棧頂元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("棧為空！");
        }
        return elem[usedSize-1];
    }
    // 是否為空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    // 是否滿了
    public boolean isFull() {
        return elem.length == usedSize;
    }
}

二、佇列（Queue）

1、什麼是佇列？

只允許在一端進行插入資料操作，在另一端進行刪除資料操作的特殊線性表，佇列具有 - 先進先出。

入佇列：進行插入操作的一端稱為隊尾

出佇列：進行刪除操作的一端稱為隊頭

2、佇列的常見方法

// 普通佇列
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);// 隊尾入
int top = queue.peek();// 獲取隊頭元素
queue.poll();// 彈出隊尾元素並返回

// 雙端佇列
Deque<Integer> deque = new LinkedList<>();
deque.offer(1);// 預設隊尾入
deque.offerFirst(2);// 隊頭入
deque.offerLast(3);// 隊尾入

deque.peekFirst();// 獲取隊頭元素
deque.peekLast();// 獲取隊尾元素

deque.pollFirst();// 彈出隊頭元素並返回
deque.pollLast();// 彈出隊尾元素並返回

3、佇列的實現（單連結串列實現）

/**
 * 每個節點
 */
class Node{
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}
public class MyQueue {
    public Node head;
    public Node tail;

    /**
     * 插入元素 -- 尾插法
     * @param val
     */
    public void offer(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            tail = node;
        }else {
            tail.next = node;
            tail = tail.next;
        }
    }

    /**
     * 出佇列
     */
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("佇列為空！");
        }
        int val = head.val;
        head = head.next;
        return val;
    }

    /**
     * 獲取隊頭元素
     */
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("佇列為空！");
        }
        return head.val;
    }
    
    // 佇列是否為空
    public boolean isEmpty() {
        return head == null;
    }
}

4、迴圈佇列

當考慮用陣列來實現一個佇列，很容易想到以下結構：

當我們連續從該隊頭中彈出元素時，就可以發現問題了

可以看到此時陣列並沒有滿，但是當我們再次插入元素時，隊尾卻插入不了了，這時候我們可以想到將該陣列看成是迴圈的陣列，結構如下。

可以看出，當 front 和 rear 相遇時，佇列可能的情況有兩種，要麼為空，要麼是滿的狀態。那麼佇列什麼時候為空，什麼時候是滿的呢？

我們有兩種方法：

1、設定usedSize 當usedSize和陣列長度相等時為滿，等於0 則為空。

2、設定標誌位設 flag = true，每放一個元素，將 flag 置為 false，每有一個元素出佇列，則將 flag 置為 true。當 front 和 rear 相遇時，flag為 true 則是空的，反之則是滿的。

public class MyCircularQueue {
    public int[] elem;
    public int front;// 隊頭下標
    public int rear;// 隊尾下標
    boolean flag = true;// 是否為空

    public MyCircularQueue(int k) {
        elem = new int[k];
    }

    // 向迴圈佇列插入一個元素。如果成功插入則返回真。
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
//            throw new RuntimeException("佇列已滿!");
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        flag = false;
        return true;
    }

    // 從迴圈佇列中刪除一個元素。如果成功刪除則返回真。
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
//            throw new RuntimeException("佇列為空!");
        }
        front = (front + 1) % elem.length;
        flag = true;
        return true;
    }

    // 從隊首獲取元素。如果佇列為空，返回 -1 。
    public int Front() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException("佇列為空!");
        }
        return elem[front];
    }
    // 獲取隊尾元素。如果佇列為空，返回 -1 。
    public int Rear() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException("佇列為空!");
        }
        // 如果是0下標，拿最後一個元素
        if (rear == 0) {
            return elem[elem.length-1];
        }else {
            return elem[rear - 1];
        }
    }

    // 檢查迴圈佇列是否為空。
    public boolean isEmpty() {
        if (rear == front && flag){
            return true;
        }
        return false;
    }
    // 檢查迴圈佇列是否已滿。
    public boolean isFull() {
        if (rear == front && !flag){
            return true;
        }
        return false;
    }
}

到此這篇關於Java 棧與佇列超詳細分析講解的文章就介紹到這了,更多相關Java 棧與佇列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！