数据结构中的双端队列 (Deque)

在本文中，我们将讨论双端队列或 deque。我们应该先简要了解一下队列。

什么是队列？

队列是一种数据结构，遵循先进先出 (FIFO) 原则，即先进入的数据结构的数据最先被移除。在队列中，插入操作从一端进行，称为 **队尾 (rear end)** 或 **尾巴 (tail)**，而删除操作从另一端进行，称为队列的 **队头 (front end)** 或 **头部 (head)**。

队列的现实世界例子是电影院外排队买票的人群，第一个进入队列的人最先买到票，最后一个进入队列的人最后买到票。

什么是 Deque (双端队列)？

Deque 代表双端队列。Deque 是一种线性数据结构，其中插入和删除操作可以从两端执行。我们可以说 deque 是队列的广义版本。

虽然 deque 中的插入和删除操作可以在两端进行，但它并不遵循 FIFO 原则。deque 的表示如下所示 -

双端队列的类型

Deque 有两种类型

• 输入受限队列
• 输出受限队列

输入受限队列

在输入受限队列中，插入操作只能在一端进行，而删除操作可以从两端进行。

输出受限队列

在输出受限队列中，删除操作只能在一端进行，而插入操作可以从两端进行。

Deque 的操作

以下是可以应用于 deque 的操作 -

• 在队首插入
• 在队尾插入
• 从队首删除
• 从队尾删除

除了上述操作外，我们还可以对 deque 执行查看操作。通过查看操作，我们可以获取 deque 的队首和队尾元素。因此，除了上述操作外，deque 还支持以下操作 -

• 获取 deque 的队首元素
• 获取 deque 的队尾元素
• 检查 deque 是否已满
• 检查 deque 是否为空

现在，让我们通过一个例子来理解 deque 的操作。

在队首插入

在此操作中，元素从队列的队首插入。在执行此操作之前，我们首先需要检查队列是否已满。如果队列未满，则可以通过以下条件从队首插入元素 -

• 如果队列为空，则队尾和队首都初始化为 0。现在，两者都将指向第一个元素。
• 否则，检查队首的位置，如果队首小于 1 (front < 1)，则将其重新初始化为 **front = n - 1**，即数组的最后一个索引。

在队尾插入

在此操作中，元素从队列的队尾插入。在执行此操作之前，我们首先需要再次检查队列是否已满。如果队列未满，则可以通过以下条件从队尾插入元素 -

• 如果队列为空，则队尾和队首都初始化为 0。现在，两者都将指向第一个元素。
• 否则，将队尾加 1。如果队尾在最后一个索引（或大小 - 1），则不是加 1，而是需要将其设置为 0。

从队首删除

在此操作中，元素从队列的队首删除。在执行此操作之前，我们首先需要检查队列是否为空。

如果队列为空，即 front = -1，则为下溢条件，我们无法执行删除。如果队列未满，则可以通过以下条件从队首插入元素 -

如果 deque 只有一个元素，则将 rear = -1 和 front = -1。

否则，如果队首在末尾（意味着 front = size - 1），则将 front 设置为 0。

否则，将队首加 1（即 front = front + 1）。

从队尾删除

在此操作中，元素从队列的队尾删除。在执行此操作之前，我们首先需要检查队列是否为空。

如果队列为空，即 front = -1，则为下溢条件，我们无法执行删除。

如果 deque 只有一个元素，则将 rear = -1 和 front = -1。

如果 rear = 0（rear 在队首），则将 rear 设置为 n - 1。

否则，将队尾减 1（或 rear = rear -1）。

检查空

此操作用于检查 deque 是否为空。如果 front = -1，则表示 deque 为空。

检查满

此操作用于检查 deque 是否已满。如果 front = rear + 1，或者 front = 0 且 rear = n - 1，则表示 deque 已满。

deque 的所有上述操作的时间复杂度均为 O(1)，即常数时间。

双端队列的应用

• Deque 可以用作堆栈和队列，因为它同时支持这两种操作。
• Deque 可以用作回文检查器，这意味着如果我们从两端读取字符串，字符串是相同的。

双端队列的实现

现在，让我们看看 C 编程语言中 deque 的实现。

输出

这就是本文的全部内容。希望本文能为您提供帮助和信息。