栈

• stack
• 先进后出
• 添加、删除复杂度为O(1) , 查询复杂度为O(n)

队列

• queue
• 先进先出
• 添加、删除复杂度为O(1) , 查询复杂度为O(n)

双端队列

• deque：Double-Ended Queue
• 栈和队列结合体
• 添加、删除复杂度为O(1), 查询复杂度为O(n)
• 类似js种的数组，实现了前后都可以插入、弹出

优先队列

• Priority Queue
• 插入复杂度为O(1) 取出操作复杂度为O(log n) 按元素的优先级取出

• 底层具体实现的数据结构较为多样和复杂

  • heap
  • bst
  • treap
  • …

    实战

    讲解

• https://leetcode.cn/problems/valid-parentheses/

• https://leetcode.cn/problems/min-stack/
• https://leetcode.cn/problems/largest-rectangle-in-histogram/

• https://leetcode.cn/problems/sliding-window-maximum/

  练习

• https://leetcode.cn/problems/design-circular-deque/

• https://leetcode.cn/problems/trapping-rain-water/