資料結構--棧和隊列學習小結

學習内容

棧 (Stack)

棧（stack）又名

堆棧

，它是一種

運算受限

的

線性表

。限定僅在

表尾進行插入

和

删除

操作的線性表。這一端被稱為

棧頂

，相對地，把另一端稱為

棧底

。向一個棧插入新元素又稱作

進棧、入棧或壓棧

，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧删除元素又稱作

出棧或退棧

，它是把棧頂元素删除掉，使其相鄰的元素成為新的棧頂元素。

稍微介紹一下關鍵名詞：

運算受限：也就是這個表你不能随便的删除插入。隻能按照它的規則進行插入删除。比如棧就隻能在一端就行插入和删除。同樣，隊列也是運算受限，隻能在兩天操作。

線性表：棧也是一種線性表，前面詳細介紹過線性表，它表達的是一種資料的邏輯關系。也就是在棧内各個元素是相鄰的。當然在具體實作上也分

數組和連結清單實作

，他們的實體存儲結構不同。但是邏輯結構(

實作的目的

)相同。

棧頂棧底： 這個描述是偏向于邏輯上的内容，因為大家知道

數組在末尾插入删除

更容易，而

單連結清單通常在頭插入删除

更容易。是以數組可以用末尾做棧頂，而連結清單可以頭做棧頂。

Stack這種資料結構應用很廣泛，比如你的程式執行檢視調用堆棧、加減運算、甚至在搜尋算法中dfs，替代遞歸等等。 在計算機的使用中，大量的運用了棧，比如編譯器中的詞法分析器、Java虛拟機、軟體中的撤銷操作（Undo）、浏覽器中的回退操作，編譯器中的函數調用實作等等。

棧的實作

接口	說明	複雜度
void push(E e)	向棧中加入元素	O(1) 均攤
E pop()	彈出棧頂元素	O(1) 均攤
E peek()	檢視棧頂元素	O(1)
int getSize()	擷取棧中元素個數	O(1)
boolean isEmpty()	判斷棧是否為空	O(1)

說明：push和pop操作在最後面進行，有可能觸發resize，但均攤來算是O(1)的。

棧的實作可以通過 數組 或者 連結清單 實作，在這裡我們使用 數組來實作上述接口。

/**
  * 基于動态數組的棧
  *
  * @param <E>
  */
 public class ArrayStack<E> extends Array<E> implements Stack<E> {
 
    private Array<E> array;
 
    public ArrayStack(int capacity) {
        this.array = new Array<>(capacity);
    }

    public ArrayStack() {
        this.array = new Array<>();
    }

    @Override
    public void push(E e) {//O(1)
        array.addLast(e);
    }

    @Override
    public E pop() {//O(1)
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public int size() {
        return array.getSize();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack:");
        res.append("[");
        for (int i = 0; i < size(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1) {
                res.append(", ");
            }
        }
        res.append("] top");
        return res.toString();
    }
}
           

隊列 Queue

隊列是一種特殊的

線性表

，特殊之處在于它隻允許在表的

前端（front）

進行删除操作，而在表的

後端（rear）

進行插入操作，和棧一樣，隊列是一種

操作受限制

的線性表。進行插入操作的端稱為

隊尾

，進行删除操作的端稱為

隊頭

。

隊頭front： 删除資料的一端。對于數組，

從後面插入更容易，前面插入較困難

，是以一般用數組實作的隊列隊頭在前面。(删除直接index遊标前進，不超過隊尾即可)。而對于連結清單。插入删除在

兩頭分别進行

那麼

頭部(前面)删除尾部插入

是最友善的選擇。

隊尾rear： 插入資料的一端，同上，在數組和連結清單中

通常均在尾部位置

。當然，其實數組和連結清單的front和rear還有點小差別，後面會具體介紹。

enQueue(入隊)： 在

隊尾

rear插入元素

deQueue(出隊)： 在

對頭

front删除元素

隊列的應用可以在播放器上的播放清單，資料流對象，異步的資料傳輸結構(檔案IO，管道通訊，套接字等)上展現，當然最直覺的的就是排隊了。

隊列的實作

接口	說明	複雜度
void enqueue(E e)	入隊	O(1) 均攤
E dequeue()	出隊	O(n)
E getFront()	擷取隊首元素	O(1)
int getSize()	擷取隊列元素個數	O(1)
boolean isEmpty()	判斷隊列是否為空	O(1)

入隊是從隊尾開始，有可能觸發resize，是以均攤下來是O(1)。出隊是在隊首，數組實作每次都要挪動所有元素,O(n)。

import datastructure.array.Array;
 /**
  * 動态隊列結構
  *
  * @param <E>
  */
 public class ArrayQueue<E> implements Queue<E> {
     private Array<E> array;

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayQueue() {
       this(10);
   }

    @Override
   public void enqueue(E e) {
        array.addLast(e);
    }

    /**
    * 每次移除的是數組的第一個，會導緻所有資料的移動 性能低效
     */
    @Override
    public E dequeue() {
        if (isEmpty()) return null;
        return array.removeFirst();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

   @Override
    public int size() {
        return array.getSize();
    }

    @Override
    public E getTopQueue() {
        return array.get(0);
    }

    @Override
    public String toString() {
       StringBuilder res = new StringBuilder();
        res.append("Queue: \n");
       res.append("top: ");
        for (int i = 0; i < size(); i++) {
            res.append(array.get(i));
            if (i < size() - 1) {
                res.append(", ");
            }
        }
        return res.toString();
    }

    public static void main(String[] args) {
//        ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
       System.out.println("求餘："+1%2);
   }
}
           

學習小結

棧和隊列的比較：

相同點：從"資料結構"的角度看，它們都是線性結構，即資料元素之間的關系相同。

不同點：棧是限定隻能在表的一端進行插入和删除操作的線性表。 隊列是限定隻能在表的一端進行插入和在另一端進行删除操作的線性表。它們是完全不同的資料類型。除了它們各自的基本操作集不同外，主要差別是對插入和删除操作的"限定"。

最後一點點感悟就是不要為了使用資料結構而使用資料結構。舉個例子，之前看到過一個數組反轉的問題，剛學過Stack可能會想，這個簡單啊，直接将字元串挨個的Push進去，然後Pop出來就可以了，完美的解決方案。但是，這是不是最有效地呢，其實有更有效地方法，那就是以中間為對折，然後左右兩邊替換