如何检查双端队列是否为空？

Deque或双端队列是队列的扩展，允许从队列的两端插入和删除。在本文中，我们将深入了解队列、不同类型的队列、双端队列，最后，如何检查双端队列是否为空。让我们开始吧！

什么是队列？

队列是一种遵循 FIFO 规则的线性数据结构。先进先出规则也称为先进先出规则。在队列中，数据从前面进入，从后面退出。它在文件 IO、套接字等方面有大量的应用。

相关：深入了解Python中的队列。

队列主要有4种类型：

简单队列
循环队列
优先级队列（heapq）
双端队列

简单队列

简单队列是经典队列，遵循先进先出规则。在这种类型的队列中，我们跟踪队列前面和后面的元素。简单队列有很多限制，它是队列的最基本形式。

限制之一是，如果队列已满并且我们从队列中删除一个元素，那么队列前面将有一些可用的空白空间，但我们将无法插入新元素。这会导致内存的浪费。为了避免这个问题，我们使用循环队列。

循环队列

在循环队列中，当队列已满时，它开始在前面追加元素。循环队列不会导致内存浪费，因为它利用了为队列分配的所有空间。仅当队列中确实没有剩余空间时（无论是在后面还是在前面）才显示队列已满。

循环队列的插入公式为(rear+1)%size，其中rear为最后一个元素的索引，size为队列的大小。

优先队列

优先级队列是一个队列，其中元素按照其优先级存储在队列中。在优先级队列中，优先级最高的元素将首先被弹出。可以使用堆来实现。堆是一棵完全二叉树，其中叶节点的优先级较低，而根节点的优先级最高。有两种类型——最小堆和最大堆。

双端队列

在一个简单的队列中，我们只能在一端追加和弹出。这个限制使得队列成为队列。但有时我们需要从同一端甚至两端追加或弹出。在这些情况下，可以使用双端队列（也称为双端队列）。Deque 是一种线性数据结构，允许在 O(1) 时间内从两端追加和弹出。

为什么我们需要双端队列？

双端队列允许从两端插入和删除。它易于实施，但带来了多种可能性。它可以同时用作队列或堆栈。在 O(1) 时间内从两端执行删除的能力使得执行回文检查变得更容易和更快。它在内存管理和一些基于图形的问题中也有应用。Deque 为许多应用程序打开了大门。

如何实现双端队列？

众所周知，Python 拥有丰富的模块和库。Python有一个名为collections的模块，它为我们提供了双端队列数据结构。使用集合中的双端队列，我们可以轻松实现双端队列。

deque 类以列表作为参数，并将给定列表转换为双端队列。

双端队列的Python实现

from collections import deque #importing deque
dq = deque([1,2,3,4,5]) #using deque to create a deque of a list
print(dq)

输出
deque([1, 2, 3, 4, 5])

双端队列的函数

追加功能

append 函数将给定元素附加到双端队列的末尾。

语法：-deque.append(6)

输出：-deque([1,2,3,4,5,6])

左追加函数

append 函数将给定元素附加到双端队列的开头。

语法：- deque.appendleft(0)

输出：- 双端队列([0,1,2,3,4,5,6])

弹出功能

pop 函数删除双端队列的最后一个元素。

语法：-deque.pop()

输出：-deque([1,2,3,4,5])

Popleft 函数

pop 函数删除双端队列的第一个元素。

语法：-deque.popleft()

输出：-deque([2,3,4,5])

双端队列可以为空吗？

双端队列有可能为空。如果双端队列中不存在任何元素，则称双端队列为空。

有两种方法可以使双端队列为空：

我们传递一个空列表作为双端队列的参数。
我们使用双端队列的 pop 或 popleft 函数弹出双端队列的所有元素。

在 Python 中创建一个空双端队列

from collections import deque #importing deque
dq = deque([]) #using deque to create a deque of a list
print(dq)

输出：-deque([])

在上面的代码中，我们只是传递了一个空列表作为双端队列的参数。这样我们就会有一个空的双端队列。

如何检查双端队列是否为空？

我们学习了如何创建一个空双端队列。但是如果我们有一个双端队列并且我们必须检查它是否为空怎么办？空双端队列是指其中没有元素的双端队列。如果双端队列中没有元素，那么它的长度将为 0。因此，要检查双端队列是否为空，我们必须检查其长度。如果双端队列的长度为0，则它是一个空双端队列。

让我们看看如何在代码中做到这一点。

检查双端队列是否为空的 Python 代码

from collections import deque #importing deque
dq = deque([]) #using deque to create a deque of a list
#creating an if-else block to check the length of the deque and output the result
if len(dq)==0:
    print("The deque is empty!")
else:
    print(f"There is/are {len(dq)} elements in the deque.")

检查双端队列是否为空的代码和输出

在上面的代码中，首先，我们从集合中导入了一个双端队列，然后创建了一个以空列表作为参数的双端队列。然后我们编写了一个 if-else 结构来检查双端队列是否为空。我们将if语句的条件设置为len(dq)==0。“len”函数给出双端队列的长度作为输出。所以它基本上意味着，如果 dq 的长度为 0，则输出空双端队列，否则输出 no。双端队列中的元素数量。

from collections import deque #importing deque
dq = deque([1,2,3]) #using deque to create a deque of a list
#creating an if-else block to check the length of the deque and output the result
if len(dq)==0:
    print("The deque is empty!")
else:
    print(f"There is/are {len(dq)} elements in the deque.")

检查双端队列是否为空的代码和输出

这次我们传递列表 [1,2,3] 作为参数。该列表中有 3 个元素。因此 len(dq)==0 将为 false，因此解释器将执行 else 块。因此输出将是“双端队列中有 3 个元素”。

为什么我们需要检查双端队列是否为空？

双端队列常用于图题或者dfs/bfs。在与它们合作时，我们需要不断检查双端队列的状态。所以有必要学会检查双端队列是否为空。

结论

双端队列是一种重要的数据结构，有很多应用。它实现起来非常简单，并且具有强大的功能。它比简单的队列或堆栈更快、更灵活。确保您完全理解它并学习如何应用它。双端队列有其自身的缺点，但也有很多优点。不断探索并乐于学习新事物。确保您还检查如何使用其他类型的队列，例如循环队列和优先级队列。

参考

Python 官方文档

堆栈溢出