Day7 - Queue Pre-Knowledge

Day7 - 队列前置知识

1. 队列的介绍

队列是一个线性集合，可以通过在一端添加元素(排队操作)，从另一端删除元素(出队列操作)。通常，添加元素的一端称为队列的后端或尾部，删除元素的一端称为队列的头部或前端。作为一种抽象数据类型，队列可以使用数组或单链表来实现。

队列的操作通常被称为FIFO(先进先出)。

广度优先搜索(BFS)通常使用队列实现。

2. 队列的实现

语言	对应接口
C++	std::queue
Java	java.util.Queue

3. 队列复杂度

操作	时间复杂度
front	O(1)
back	O(1)
push	O(1)
pop	O(1)
empty	O(1)

4. 注意的事情

有些语言没有可以使用的内置队列这个数据类型，通常使用数组(JavaScript)或列表(Python)作为队列。在这种情况下，出队列操作(假设队列的前面在左边)将是O(n)，因为它需要将所有其他元素向左移动一位。

5. 队列边界条件

• 空队列

• 队列中只有一个元素

• 队列中只有两个元素