一文帶你認識Java棧和佇列

推薦學習：《》

在學習棧和佇列 之前，先了解一下什麼是線性表：一次儲存單個同型別的元素，多個元素之間邏輯上連續，比如陣列，連結串列，字串，棧和佇列
棧和佇列其實操作受限的線性表，陣列也罷，連結串列也罷，既可以在頭部插入和刪除，也能在尾部插入和刪除，但是棧和佇列只能在一端插入，在一端刪除

一、棧

1.定義

只能在一端插入元素，也只能在這一端刪除元素（棧頂），可以把棧看作一個「水杯」，只能從一端新增元素，也只能從一段刪除元素，而且，先進入水杯的水在杯底，後進入水杯的水在杯頂，往出倒水的時候，也是倒出的杯頂的水，棧也是一樣，先入棧的元素在棧底，後入棧的元素在棧頂，所以先入棧的元素後出，後入棧的元素先出，這也是棧的特性「先進後出，後進先出」Last In First Out(LIFO),取出元素和新增元素只能在棧頂。
將1 2 3 4 5，一次放入棧中

2.棧的應用

1.無處不在的undo(復原)操作

在任何一個編輯器中輸錯一個內容後，使用Ctrl + z就返回到了輸入的內容；
在任何一個瀏覽器中點選後退操作

都是棧的這個結構的應用
1.使用編輯器使用復原操作，一次輸入就把內容壓入棧中，再輸入就就再壓入棧中，發現一次輸入錯誤，就使用復原操作，把當前棧頂的錯誤內容彈出，那麼當前棧頂的內容就是上次輸入的內容。
2.瀏覽網頁其實也是相同原理的，就像開啟百度 -> 開啟csdn -> 開啟創作中心，也是使用棧這個結構，先把百度網頁壓入棧中 ，然後csdn網頁壓入棧中，然後創作中心網頁壓入棧中，想要返回到csdn主頁，按下後頭箭頭，就把當前棧頂的創作中心網頁彈出，取出csdn主頁。

2.作業系統棧

程式再執行的過程中，從A函數呼叫B函數，從B函數呼叫C函數，呼叫結束，返回執行時，如何得知從哪繼續開始執行呢，背後也是棧這個結構

3.棧的實現

基於連結串列實現的棧 – 鏈式棧
基於陣列實現的棧 – 順序棧（使用較多）
定義一個基於動態陣列實現的棧

//基於動態陣列實現的順序棧public class MyStack<E> {
    //記錄當前棧的元素個數
    private int size;
    //實際儲存資料的動態陣列，此時在棧中只能在陣列的尾部新增和刪除元素
    private List<E> data = new ArrayList<>();
    }

4.棧的操作

1.向棧中新增一個元素
只能在棧頂新增

 /**
     * 向當前棧中新增元素 -- >壓棧操作
     * @param val
     */
    public void push(E val){
        data.add(val);
        size++;
    }

2.當前從棧頂彈出一個元素

/**
     * 彈出當前棧頂元素,返回棧頂元素的值
     * @return
     */
    public E pop(){
        if (isEmpty()){
            //棧為空無法彈出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //在陣列末尾刪除元素
        E val = data.get(size - 1);
        data.remove(size - 1);
        size --;
        return val;
    }

3.檢視當前棧頂元素，但不彈出

/**
     * 檢視當前棧頂元素值，不彈出該元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size - 1);
    }

二、佇列

1.定義

佇列：先進先出（FIFO）的資料結構i，元素只能從隊尾新增到佇列中，也只能從隊首出佇列，元素的出隊順序和入隊順序保持一致
將1 2 3 4 5依次入隊

2.佇列的應用

現實生活中，各種各樣的「排隊」操作

3.佇列的實現

基於陣列實現的佇列 – 順序佇列
基於連結串列實現的佇列 – 鏈式佇列
出隊操作只能在佇列的頭部進行，若採用陣列實現的佇列，每次出隊一個元素就得搬移剩下的所有元素向前移動一個單位，此時採用連結串列實現的佇列更適合佇列的結構，刪除元素只需要刪除頭結點，新增元素在連結串列的尾部新增

public interface Queue<E> {
    //入隊操作
    void offer(E val);
    //出隊操作
    E poll();
    //檢視隊首元素
    E peek();
    boolean isEmpty();}

對於棧來說佇列的實現子類是比較多的，比如
FIFO佇列
雙端佇列
迴圈佇列
優先順序佇列
不管哪個佇列都要實現

4.FIFO佇列

1.定義一個FIFO佇列

// An highlighted blockvar foo = 'bar';

2.向佇列中新增一個元素

public void offer(E val) {
        Node<E> node = new Node<>(val);
        if (head == null){
            head = tail = node;
        }else{
            //連結串列的尾插
            tail.next = node;
            tail = node;
        }
        size++;
    }

3.從當前隊首出隊一個元素

 public E poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        //頭刪
        E val = head.val;
        Node<E> node = head;
        head = head.next;
        node.next = node = null;
        size--;
        return val;
    }

4.檢視當前佇列的隊首元素

public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }

5.迴圈佇列

1.定義：基本上都是使用固定長度的陣列來實現，陣列在實現隊時，若從陣列頭部刪除元素需要頻繁的移動後面的元素，效率比較低；出隊和入隊操作，使用兩個參照，一個head，一個tail,新增元素在陣列的尾部新增，刪除元素只需要移動head參照指向的地址即可（邏輯刪除）
2.應用：作業系統的生產消費者模型，MySQL資料庫的InnoDB儲存引擎的redo紀錄檔
3.迴圈佇列就是使用長度固定的陣列來實現，陣列頭部就是隊首（head），陣列的尾部就是隊尾（tail），陣列[head…tail)時迴圈佇列的有效元素
head永遠指向迴圈佇列的第一個元素
tai永遠指向迴圈佇列有效元素的後一個位置

此時迴圈佇列的有效元素就為7 9 1兩個元素
迴圈佇列出隊一個元素，就只用讓head參照向後移動一個位置

此時迴圈佇列的有效元素就只有9 和 1 兩個元素了
再出隊一個元素，但此時head參照已經走到末尾了，所謂迴圈佇列就是當head或者tail參照走到陣列末尾時，再向後移動就是返回陣列頭部的操作，迴圈佇列最大好處就是進行元素的刪除的時候不需要進行資料的搬移操作，當有新的元素新增到佇列中就會覆蓋掉原來的元素，就只需要將tail索引位置覆蓋上新的元素，再讓tail再向後移動

當佇列為空時,head == tail

當佇列已「滿」時，head == tail

迴圈佇列需要注意的關鍵點
1.因此當head 和 tail相等時，沒法區分此時迴圈佇列已滿，還是為空，因此在迴圈佇列中，若(tail + 1) % n == head就認為迴圈佇列已滿

此時迴圈佇列就已經滿了，在迴圈佇列中就會浪費一個空間，判斷佇列是否已滿
2.head和tail的移動不能簡單的 + 1，使用取模操作，取陣列長度
tail = (tail + 1) % n
head = (head + 1) % n
對陣列長度取模的本質：
當head和tai走到陣列最後一個索引位置時，下一次要返回陣列頭部，就必須用 + 1對陣列長度取模
3.head == tail時，認為佇列為空

6.迴圈佇列的操作

1.定義一個迴圈佇列

//基於整形的迴圈佇列public class LoopQueue implements Queue<Integer> {
    //定長陣列
    private Integer[] data;
    //指向隊首元素
    int head;
    //指向隊尾元素的下一個元素
    int tail;
    public LoopQueue(int size){
        data = new Integer[size + 1];
    }}

2.向迴圈佇列中新增一個元素

@Override    public void offer(Integer val) {
       if (isFull()){
           throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
       }
       data[tail] = val;
       tail = (tail + 1) % data.length;
    }

3.從迴圈佇列中出隊一個元素

 @Override    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }

4.檢視當前迴圈佇列隊首元素

 @Override    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek!");
        }
        return data[head];
    }

5.判斷當前迴圈佇列是否為空

 @Override    public boolean isEmpty() {
        return head == tail;
    }

6.判斷當前迴圈佇列是否已滿

 public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

7.toString方法

public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最後一個有效元素的索引
        int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lsatIndex){
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }

7.雙端佇列

雙端佇列：Deque是Queue的子介面，這個佇列既可以尾插，頭出；也可以頭插，尾出

雙端佇列的一個常用子類就是LinkedList，不管使用棧還是佇列，都可以統一使用雙端佇列介面
1.現在需要一個棧

2.現在需要一個佇列

推薦學習：《》

以上就是一文帶你認識Java棧和佇列的詳細內容，更多請關注TW511.COM其它相關文章！