算法训练营-栈和队列的实现与特性

栈

想象成一个先入后出的容器：

队列

像排队，先来先出：

栈和队列关键点

栈（Stack）：先入后出；添加、删除操作的时间复杂度都为O(1)，查询为O(n)
队列（Queue）：先入后出；添加、删除操作的时间复杂度都为O(1),查询为O(n)

双端队列(Double End Queue)

首端和尾端都可以添加、删除元素：

简单理解：两端都可以进出的队列；
插入和删除都是O(1)的操作。

Stack、Queue、Deque的工程实现

优先队列(Priority Queue)

插入操作：O(1)
取出操作：O(logN)-按照元素的优先级取出
底层具体实现的数据结构较为多样和复杂：heap、bst、treap

Java源码分析

Stack-source Java

时间复杂度

作业

1，用新的api-addfirst,addlast去改写
2，分析Queue，Priority Queue源码

参考链接

Stack Java 12 doc

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
When a stack is first created, it contains no items.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

   
   Deque<Integer> stack = new ArrayDeque<Integer>();

Priority Queue Java 12 doc