队列数据结构的基本操作

队列是一种遵循 FIFO（先进先出）原则的线性数据结构，其中在队尾进行插入操作，而在队首进行删除操作。

以下是一些基本操作，使我们能够高效地添加、删除和访问元素。

• enqueue() – 向队列中插入元素。
• dequeue() – 从队列中移除元素。
• getFront()- 获取队列首节点的数据元素，而不删除它。
• getRear() – 此操作返回队尾的元素而不将其移除。
• isEmpty() – 检查队列是否为空。
• size() – 此操作返回队列的大小，即其中包含的元素总数。

现在让我们看看如何在队列上执行这些操作。

enqueue()

入队操作会在队列的末尾（即队尾）插入一个元素。

C++


CODEBLOCK_62a1a06a


Java


CODEBLOCK_79e80850


Python


CODEBLOCK_d310b463


C#


CODEBLOCK_de0a7bf0


JavaScript


CODEBLOCK_497a4cdc

时间复杂度： O(1)，因为在队尾插入元素需要常数时间。
辅助空间： O(1)
注意： 如果队列是使用固定大小的数组实现的，向已满的栈中插入元素将导致上溢 条件。

dequeue()

出队操作会移除位于队列首端的元素。

C++


CODEBLOCK_b935905e


Java


CODEBLOCK_a9d94053


Python


CODEBLOCK_852be34b


C#


CODEBLOCK_2c10d4f7


JavaScript


CODEBLOCK_d0d2c2fe

时间复杂度： O(1)，因为从队首删除元素需要常数时间。

在 JavaScript 中，没有内置的队列，所以我们使用数组。使用 q.shift() 删除元素需要 O(n) 时间，因为所有元素都需要重新索引。

辅助空间： O(1)
注意： 如果队列为空，删除元素将导致下溢 条件。

getFront()

getFront 操作将返回队列首端的元素而不将其移除。

!getFront

C++


CODEBLOCK_b6038517


Java


CODEBLOCK_4831e91c


Python


CODEBLOCK_a5767ca9


C#


CODEBLOCK_41238008


JavaScript


CODEBLOCK_f1486288

时间复杂度： O(1)，因为访问队首元素需要常数时间。
辅助空间： O(1)

getRear()

getRear 操作将返回队尾的元素而不将其移除。

!getRear

C++


CODEBLOCK_4370574d


Java


CODEBLOCK_1a0cd488


Python


CODEBLOCK_3be90e95


C#


CODEBLOCK_ce992589


JavaScript


CODEBLOCK_edbf0cbb

时间复杂度： O(1)，因为访问队尾元素需要常数时间（在标准实现中）。
辅助空间： O(1)

isEmpty()

isEmpty 操作检查队列是否为空。

C++


CODEBLOCK_ff25af04


Java


CODEBLOCK_05a25ccc


Python


CODEBLOCK_ad7ebb07


C#


CODEBLOCK_633950a9


JavaScript


CODEBLOCK_ab6879f2

时间复杂度： O(1)
辅助空间： O(1)

size()

size 操作返回队列的大小，即其中包含的元素总数。

C++


CODEBLOCK_57fe04ea


Java


CODEBLOCK_f5e4fd7a


Python


CODEBLOCK_52cbe0bb


C#


CODEBLOCK_b7ad7094


JavaScript


CODEBLOCK_4198fe6e

时间复杂度： O(1)，获取大小通常是一个存储的值，所以是常数时间操作。
辅助空间： O(1)