三、数据结构算法-栈、队列、优先队列、双端队列

一、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 源码