在基础的数据结构中栈和队列使用极其广泛,其用法也很多,今天就来总结一下栈和队列的使用方法和相关的题目。
队列Queue
基本概念
队列是一个线性数据 结构,特点是先入先出,也就是能保证先入队的元素先出队,也即FIFO First In First Out。与现实生活中的排队是一样的。
基础应用
应用很广泛,像消息队列,任务队列,以及像滑动窗口。
典型题目
题目 | 题解 | 说明 |
---|---|---|
剑指 Offer II 041. 滑动窗口的平均值 | 题解 | |
622. 设计循环队列 | 题解 | |
题解 | ||
题解 | ||
题解 | ||
题解 |
中级应用
BFS要用到队列。
BFS可以参考另外一个文章。
典型题目
高级应用
单调队列,队列中的元素以非递增顺序或者非递减顺序排列。
单调队列参见另外一个文章。
栈Stack
基本概念
也是一个线性结构,与队列类似,但它是先入后出,或者说后入先出,FILO First In Last Out。现实生活中也有,比如像盘子,通常是叠在一起的,这就是一个栈,一个一个叠 在一起,最后放上去的,最先拿下来用。
基础应用
程序运行时会用到栈,函数的调用会用到栈。还有一些模拟的场景也会用到栈,比如像处理括号和表达式一类的问题时。
典型题目
题目 | 题解 | 说明 |
---|---|---|
20. 有效的括号 | 题解 | 栈模拟 |
155. 最小栈 | 题解 | 栈模拟 |
735. 行星碰撞 | 题解 | |
895. 最大频率栈 | 题解 | |
946. 验证栈序列 | 题解 | |
1441. 用栈操作构建数组 | 题解 | |
题解 | ||
题解 |
中级应用
DFS需要用到栈.
DFS可以参考另外一个文章。
高级应用
单调栈参见另外一个文章。
双端队列Deque
双端队列Deque读作dek,是两端都可以入队和出队,因此它即可以用作栈也可以用作队列,在实际使用中是最多的,大多数时候都尽可能用双端队列。