栈和队列的实现与特性

  • Stack：Last in - First out；添加、删除皆为 O(1)；查询为 O(n)
  • Queue：Last in - Last out / First in - First out；添加、删除皆为 O(1)；查询为 O(n)
  • Deque（Double-End Queue）：常用。Stack 和 Queue 的结合，头和尾都可以进行出和入；插入和删除都是 O(1) 的操作；查询为 O(n)
  • Priority Queue
    • 插入操作 O(1)
    • 取出操作 O(logn) - 按照元素的优先级取出
    • 底层具体实现的数据结构较为多样和复杂：heap、BST、treap