棧與隊列簡介

2020 年 9 月 28 日
筆記
數據結構

棧與隊列和數組、鏈表、樹這幾種數據結構不太一樣。棧與隊列主要是做為程式設計師的工具來使用，它們主要做為構思演算法的輔助工具，而不是完全的數據存儲工具。

它們的生命周期比數組那些要短得多，在程式執行期間它們才會被創建，任務執行完就會被銷毀。

一棧

棧是一種只能在一端進行插入和刪除數據的數據結構，這一端被稱為棧頂（top）。其特點簡單來講就是先進後出。棧的主要機制可以用數組來實現，當然也可以用鏈表來實現。

用數組實現棧，並完成常用操作——出棧、入棧、查看元素（只能查看棧頂元素）、判斷棧是否為空等操作。

public class StackTest {
	
    private long[] arr;
    // 棧頂
    private int top;

    public StackTest(){
        arr = new long[10];
        top = -1;
    }
    public StackTest(int maxsize){
        arr = new long[maxsize];
        top = -1;
    }

    /**
     * 添加數據
     * @param value
     */
    public void push(int value){
        arr[++top] = value;
    }

    /**
     * 移除數據
     * @return
     */
    public long pop() {
        return arr[top--];
    }

    /**
     * 查看數據
     * @return
     */
    public long peek(){
        return arr[top];
    }
    public boolean isEmpty(){
        return top == -1;
    }

    /***
     * 判斷是否滿了
     * @return
     */
    public boolean isFull(){
        return top == arr.length-1;
    }
}

棧的所有操作複雜度都為O(1)，棧的操作不依賴棧中元素大小，棧不需要移動和比較操作。

二隊列

隊列的特點是先進先出。隊列也是用數組來實現。

用數組實現隊列，並完成常用操作——出隊、入隊、查看元素、判斷隊列是否為空等操作。

public class QueueTest {

    private long[] arr;
    // 有效數據的大小
    private int elements;
    // 隊頭
    private int front;
    // 隊尾
    private int end;

    public QueueTest(){
        arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public QueueTest(int maxsize){
        arr = new long[maxsize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 插入數據
     * @param value
     */
    public void insert(long value){
        arr[++end] = value;
        elements++;
    }

    /**
     * 刪除數據
     * @return
     */
    public long remove(){
        elements--;
        return arr[front++];
    }

    /**
     * 查看數據，從對頭查看
     * @return
     */
    public long peek(){
        return arr[front];
    }

    /**
     * 判斷是否為空
     * @return
     */
    public boolean isEmpty(){
        return elements == 0;
    }

    public boolean isFull(){
        return elements == arr.length;
    }
}

隊列的插入、刪除等操作的複雜度都為O(1)。

三優先順序隊列

優先順序隊列和普通隊列一樣，也是一個隊頭，一個隊尾，從隊頭移除元素，優先順序隊列中，數據項是有序的，這樣插入數據的時候就會根據某種規則去比較，然後插入到隊列合適的位置。因此，優先順序隊列插入的複雜度為O(N)，刪除和查看元素的複雜度為O(1)。

用數組實現優先順序隊列，並完成常用操作——出隊、入隊、查看元素、判斷隊列是否為空等操作。

public class FirstQueueTest {

    private long[] arr;
    // 有效數據的大小
    private int elements;
    // 隊頭
    private int front;
    // 隊尾
    private int end;

    public FirstQueueTest(){
        arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public FirstQueueTest(int maxsize){
        arr = new long[maxsize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 插入數據
     * @param value
     */
    public void inser(long value){
        if(elements == 0){
            arr[++end] = value;
            elements++;
        }else{
            // 按某種規則進行比較，這裡使用value的大小比較，按從小到大排序
            for(int i = elements-1;i>=0;i--){
                if(value<arr[i]){
                    arr[i+1] = arr[i];
                    arr[i] = value;
                }else{
                    arr[i+1] = value;
                    break;
                }
            }
            elements++;
            end++;
        }
    }

    /**
     * 刪除數據
     * @return
     */
    public long remove(){
        elements--;
        return arr[front++];
    }

    /**
     * 查看數據，從對頭查看
     * @return
     */
    public long peek(){
        return arr[front];
    }

    /**
     * 判斷是否為空
     * @return
     */
    public boolean isEmpty(){
        return elements == 0;
    }

    public boolean isFull(){
        return elements == arr.length;
    }
}

四總結

棧的特點是先進後出，棧只能查看棧頂的一個元素
隊列的特點是先進先出，只能查看隊頭的一個元素
優先順序隊列插入一條元素，平均需要移動2/N個元素，因此插入的複雜度為O(N)
棧和隊列，可以用數組實現，也可以用其他數據結構實現
棧和隊列是為了完成某些工作，手動構造的數據結構

點關注、不迷路

如果覺得文章不錯，歡迎關注、點贊、收藏，你們的支援是我創作的動力，感謝大家。

如果文章寫的有問題，請不要吝嗇，歡迎留言指出，我會及時核查修改。

如果你還想更加深入的了解我，可以微信搜索「Java旅途」進行關注。回復「1024」即可獲得學習影片及精美電子書。每天7:30準時推送技術文章，讓你的上班路不在孤獨，而且每月還有送書活動，助你提升硬實力！

Tags: 數據結構