三、數據結構演算法-棧、隊列、優先隊列、雙端隊列

• 2020 年 12 月 30 日
• 筆記
• 數據結構, 數據結構與演算法

一、Stack （棧）

1、數據結構

　　Stack是棧。它的特性是：先進後出(FILO, First In Last Out) 後進先出（Last in – First out）。java工具包中的Stack是繼承於Vector(矢量隊列)的，由於Vector是通過數組實現的，這就意味著，Stack也是通過數組實現的，而非鏈表。當然，我們也可以將LinkedList當作棧來使用。

2、Stack的繼承關係

3、時間複雜度

4、源碼實現

Stack 繼承自 Vector 底層為動態數組實現

   /**
     * 向棧頂添加元素
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item); // Vector 中的新增方法

        return item;
    }

   /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     * 查看棧頂元素並刪除
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1); // Vector 中的按照下標移除元素的方法

        return obj;
    }
    /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     * 查看棧頂元素但不刪除
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    // 棧是否為空
    public boolean empty() {
        return size() == 0;
    }

    // 查找「元素o」在棧中的位置：由棧底向棧頂方向數
    public synchronized int search(Object o) {
        // 獲取元素索引，elementAt()具體實現在Vector.java中
        int i = lastIndexOf(o);
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

Java 的 Stack 源碼

二、Queue （隊列）

1、數據結構

First in – First out（先進先出 FIFO）

2、時間複雜度

3、源碼實現

//介面Queue：
public interface Queue<E> extends Collection<E> {
    //將指定元素插入到隊列的尾部（隊列滿了話，會拋出異常）
    boolean add(E e);

    //將指定元素插入此隊列的尾部(隊列滿了話，會返回false)
    boolean offer(E e);

    /返回取隊列頭部的元素，並刪除該元素(如果隊列為空，則拋出異常)
    E remove();

    //返回隊列頭部的元素，並刪除該元素(如果隊列為空，則返回null)
    E poll();

    //返回隊列頭部的元素,不刪除該元素(如果隊列為空，則拋出異常)
    E element();

    //返回隊列頭部的元素，不刪除該元素(如果隊列為空，則返回null)
    E peek();
}

Java 的 Queue 源碼

三、Deque (Double-Ended Queue 雙端隊列)

1、數據結構

線性集合，支援兩端插入和移除元素。名稱deque是「雙端隊列（double ended queue）」的縮寫。
也可以理解為 Queue 與 Stack 的結合體，可以從頭部 Push 或者 Pop 元素，也可以在尾部 Push 或者 Pop 元素，兩端可以進出的隊列

2、Deque 的繼承關係

3、方法摘要

4、時間複雜度

5、源碼實現

Java 的 Deque 源碼

四、Priority Queue (優先隊列)🌶️

1、數據結構

底層具體實現的數據結構較為多樣和複雜可以使用 heap、bst(binary search tree)、treap

2、時間複雜度

3、源碼實現 & 文檔

它的使用與隊列幾乎沒有區別，只不過我們在取元素的時候需要注意都是取優先順序最高的，優先順序怎麼定義？我們只需要將元素取實現 comparator （比較器）就可以由大到小或由小到大 再或者 自己定義某個欄位優先等等。

Java 的 PriorityQueue 文檔
Java 的 PriorityQueue 源碼