数据结构 — 队列(Queue)

普通队列 #

队列的特点就是先进先出,后进后出。可以使用数组、链表实现队列。

队列的操作 #

插入元素(add)一般指在队列首部插入元素。

删除元素(remove)指删除队列末尾的元素。

获取元素(get)一般是获取队列最前面的元素。

应用场景 #

二叉树的广度优先搜索 #

二叉树的广度优先搜索是从上到下按层遍历二叉树,从二叉树的根节点开始,先遍历二叉树的第1层,再遍历第2层,接着遍历第3层,并以此类推。

通常基于队列来实现二叉树的广度优先搜索。从二叉树的根节点开始,先把根节点放入一个队列之中,然后每次从队列中取出一个节点遍历。如果该节点有左右子节点,则分别将它们添加到队列当中。重复这个过程,直到所有节点都遍历完为止,此时队列为空。

剑指 Offer II 043. 往完全二叉树添加节点

常见题型 #

剑指 Offer II 041. 滑动窗口的平均值

剑指 Offer II 042. 最近请求次数

双端队列 #

双端队列是栈和队列的结合,双端队列中的元素可以从两端弹出,插入和删除操作限定在队列的两边进行。相对应的,普通的队列就是单端队列。

https://rogerspy.github.io/2021/09/05/ds-deque/

二项队列 #

本文共 426 字,上次修改于 Oct 12, 2022
相关标签: 算法, 数据结构