Deque或双端队列是一种顺序线性收集数据队列，提供类似于双端队列的功能。在此数据结构中，该方法不遵循先进先出（FIFO）规则进行数据处理。这种数据结构也称为双端队列，因为元素插入到队列的末尾并从前面删除。对于双端队列，我们只能从两端添加和删除数据。双端队列操作的时间复杂度为O(1)。有两种类型的双端队列 –
输入受限
单端输入限制。
允许从两端删除数据。
输出受限
单端输出限制。
允许向两端插入数据。
以下命令可帮助编码人员使用双端队列上的数据集池执行各种操作 –
push_back() – 从双端队列的后面插入一个元素。
push_front() – 从双端队列的前面插入一个元素。
pop_back() – 从双端队列后面删除元素。
pop_front() – 从双端队列的前面删除元素。
front() – 返回双端队列前面的元素。
back() – 返回双端队列后面的元素。
at() – 设置/返回指定索引处。
size()-返回元素的数量。
empty() – 如果双端队列为空，则返回 true。
在循环数组中我们可以使用双端队列操作。如果数组已满，那么我们可以从头开始该过程。但对于线性数组，如果数组已满，则无法插入更多数据。然后我们可以看到一个“溢出弹出窗口”。
双端队列的应用
Deque 有很多实时应用程序可供使用。
用于作业调度应用程序。
在 O(1) 时间内我们可以执行顺时针和逆时针旋转操作。
双端队列算法也存在于网络浏览器历史记录中。
用于排序中的撤消操作。
双端队列的优点
Deque 有很多优点。
我们可以从正面和背面添加和删除数据。
它们的大小是动态的。
Deque 提供了执行操作的高效时序。
此处使用了 LIFO 堆栈。
此处无法重新分配。
这是一个具有适当同步的线程安全进程。
缓存友好。
双端队列的缺点
双端队列的缺点是
Deque进程内存消耗率较高。
它存在多线程同步问题。
无法在所有平台上实现。
不适合实现排序操作。
Deque 的功能较少。
双端队列操作的算法
第 1 步 – 考虑一个大小为 n 的双端队列数组。
第 2 步 – 将两个指针设置为“front=-1”（表示 front）和“rear=0”（表示 set）。
这个过程有很多子部分。在双端队列中我们可以执行多个操作。我们在这里总结了它们。
在双端队列中从前面插入数据的算法：-
第 1 步 – 检查前面的位置。
第 2 步 – 如果“front
第 3 步 – 否则，我们需要将“front”减少 1。
第 4 步 – 将新的键元素添加到数组的前面位置。
在双端队列后面插入数据的算法：-
第 1 步 – 检查阵列是否已满。
第 2 步 – 如果已满，则应用“rear=0”。
第 3 步 – 否则，将“rear”的值增加 1。
第 4 步 – 再次将新键添加到“array[rear]”中。
从双端队列前面删除数据的算法：-
第 1 步 – 检查双端队列是否为空。
第 2 步 – 如果列表为空（“front=-1”），则为下溢条件，无法进行删除。
步骤 3 – 如果双端队列中只有一个元素。然后“front=rear=-1”。
第 4 步 – 否则，“front”位于末尾，然后设置为“front=0”。
第 5 步 – 否则，front=front+1。
从双端队列后面删除数据的算法：-
第 1 步 – 检查双端队列是否为空。
步骤 2 – 如果为空（“front=-1”），则无法执行删除。这是下溢条件。
第 3 步 – 如果双端队列只有一个数据，则“front=rear=-1”。
第 4 步 – 否则，请按照以下步骤操作。
步骤 5 – 如果后部位于前面“后部=0”。转到前面“rear = n-1”。
第 6 步 – 否则，rear=rear-1。
检查双端队列是否为空的算法：-
第 1 步 – 如果 front=-1，则双端队列为空。
检查双端队列是否已满的算法：-
步骤 1 – 如果前=0 且后= n-1
第 2 步 – 或者，front=rear+1
双端队列的语法
deque
在数据结构中，双端队列继承了堆栈和队列的一些属性。在 C++ 中，双端队列被实现为向量的向量。
使用双端队列的各种方法的处理
方法 1 – 以一般方式实现双端队列
方法 2 – 将元素插入双端队列
方法 3 – 从双端队列访问元素
方法 4 – 更改双端队列的元素
双端队列的一般实现
在此 C++ 构建代码中，我们以通用方式配置了双端队列操作。在这个例子中，我们在队列的后端插入了一个元素，整个系统就是按照这种方式执行的。
示例 1
#include using namespace std;#define MAX 10class Deque { int arr[MAX]; int front; int rear; int size; public: Deque(int size) { front = -1; rear = 0; this->size = size; } void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear();};bool Deque::isFull() { return ((front == 0 && rear == size - 1) || front == rear + 1);}bool Deque::isEmpty() { return (front == -1);}void Deque::insertfront(int key) { if (isFull()) { cout << "Overflown" << endl; return; } if (front == -1) { front = 0; rear = 0; } else if (front == 0) front = size - 1; else front = front - 1; arr[front] = key;}void Deque ::insertrear(int key) { if (isFull()) { cout << " Overflown " << endl; return; } if (front == -1) { front = 0; rear = 0; } else if (rear == size - 1) rear = 0; else rear = rear + 1; arr[rear] = key;}void Deque ::deletefront() { if (isEmpty()) { cout << "Queue Underflown" << endl; return; } if (front == rear) { front = -1; rear = -1; } else if (front == size - 1) front = 0; else front = front + 1;}void Deque::deleterear() { if (isEmpty()) { cout << " Underflown" << endl; return; } if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size - 1; else rear = rear - 1;}int Deque::getFront() { if (isEmpty()) { cout << " Underflown" << endl; return -1; } return arr[front];}int Deque::getRear() { if (isEmpty() || rear < 0) { cout << " Underflown" << endl; return -1; } return arr[rear];}int main() { Deque dq(4); cout << "insert element at rear end n"; dq.insertrear(5); dq.insertrear(11); cout << "rear element: " << dq.getRear() << endl; dq.deleterear(); cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl; cout << "insert element at front end n"; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl;}
输出
insert element at rear end rear element: 11after deletion of the rear element, the new rear element: 5insert element at front end front element: 8after deletion of front element new front element: 5
将元素插入双端队列
在此代码中，我们尝试创建 C++ 代码以将元素插入双端队列。有两种方法可以执行此操作。
push_back() – 在数组末尾插入元素。
push_front() – 在数组的开头插入元素。
示例 2
#include #include using namespace std;int main() { deque nums {16, 7}; cout << "Initial Deque As We Give: "; for (const int& num : nums) { cout << num << ", "; } nums.push_back(2001); nums.push_front(1997); cout << "nFinal Deque Is Here: "; for (const int& num : nums) { cout << num << ", "; } return 0;}
输出
Initial Deque As We Give: 16, 7, Final Deque Is Here: 1997, 16, 7, 2001,
从双端队列访问元素
我们可以使用两种方法访问双端队列中的元素。
front() – 在前面我们可以获得返回值。
back() – 返回后面的数据。
at() – 从指定索引返回。
#include #include using namespace std;int main() { deque nums {16, 07, 10}; cout << "Front element are here: " << nums.front() << endl; cout << "Back element are here: " << nums.back() << endl; cout << "Element at index 1 present here: " << nums.at(1) << endl; cout << "Element at index 0 present here: " << nums[0]; return 0;}
输出
Front element are here: 16Back element are here: 10Element at index 1 present here: 7Element at index 0 present here: 16
更改双端队列的元素
在此代码中，我们可以使用 at() 方法来替换或更改该特定双端队列的元素。
示例 4
#include #include using namespace std;int main() { deque nums = {07,16,10,1997,2001}; cout << "Initial Deque: "; for (const int& num : nums) { cout << num << ", "; } nums.at(0) = 2022; nums.at(1) = 10-05; cout << "nUpdated Deque: "; for (const int& num : nums) { cout << num << ", "; } return 0;}
输出
Initial Deque: 7, 16, 10, 1997, 2001, Updated Deque: 2022, 5, 10, 1997, 2001,
结论
通过这篇文章，我们了解了双端队列，它的操作方法、应用、优缺点以及算法和使用C++可能的代码。
以上就是应用、优势和缺点的双端队列的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444515.html
微信扫一扫 
支付宝扫一扫 
