栈

LIFO：先入后出。先进来的元素会被放在最下面，叠在一起，不能从下面出任何元素。
image.png

源码实现

Java 的 Stack 源码

队列

FIFO：排队，先来先出。谁先进来谁先出去。就像排队一样
image.png
Java 的 Queue 源码

栈和队列关键点

  • Stack：先入后出；添加、删除皆为 O(1)，查询为O(N)
  • Queue：先入先出；添加、删除皆为 O(1)，查询为O(N)

双端队列（Double End Queue）

  • 简单理解：两端可以进出的Queue
  • Deque - double ended queue
  • 插入和删除都是O(1) 操作

image.png

优先队列（Priority Queue）

  • 插入操作：O(1)
  • 取出操作：O(logN) 按照元素优先级取出元素
  • 底层实现多重多样且复杂。堆实现（heap），bst，avl，红黑树，treap