我们可以在数组中访问任意一个元素,但有时候我们希望限制处理顺序,这样我们可以忽略其它细节。在线性结构的处理顺序中,有两种常见的处理顺序,先进先出和后进先出,而它们对应的数据结构是队列和栈。
Queue:First-in-first-out Data Structure
Queue
先进先出Java
中初始化一个队列一般用:Queue<T> queue = new LinkedList<T> ()
Queue and BFS
BFS(Breadth-first Search)
两种常用场景是遍历和寻找最短路径。广度优先搜索对结点的处理顺序就是先进先处理,所以常用队列这种数据结构来配合实现;
Stack:Last-in-first-out Data Structure
Stack
后进先出Java
中初始化一个栈一般用:Deque<T> stack = new ArrayDeque<T> ()
,因为Java
中的Stack
是一个古老的类,跟现有的Collections
类不相通
Stack and BFS
DFS (Depth-first Search)
深度优先搜索的实现一般需要栈这种数据结构来配合- 递归的时候是隐式地使用了栈:
call stack
,能用递归实现的都可以用一个显式栈加迭代实现
总结:
队列和栈本身并不复杂,但一般都会结合树、图等复杂的数据结构,所以很多题目还不能够清晰地实现解决。