FIFO(first in, first out)型数据结构,当你想首先处理第一个元素时,队列将是最合适的数据结构。
在JavaScript中,数组的地址是连续的,在栈内存中保存了数组的首地址,通过下标寻址的方式查找元素;队列不同于栈,当每个元素出队列时,会在堆内存中通过遍历元素将元素前移;因此效率是十分低的;
为了解决这个问题,有相应的策略:
-
通过一个指针模拟头节点,每次出队列将头节点后移,并不是真正的推出元素;
缺点:在使用过程中效率是有保证的,但是随着使用,浪费的内存空间会越来越大;
-
为了避免空间的无限制浪费,可以采用限制队列大小的方案,通过覆盖旧值,甚至扩容策略来解决,这就是循环队列!
循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
广度优先搜索BFS,优先遍历下一层级的子树,再推出根节点,再依次遍历;
Queue:
A ->
ABCD ->
BCD ->
BCDE ->
CDE ->
CDEF ->
DEF ->
EFG ->
FG ->
G ->
空
甚至可以考虑双向BFS的思路:



