数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究双端队列（Deque）的应用、优点和缺点
双端队列（Deque）或双端队列是一种顺序线性集合数据队列，它提供类似于双端队列的功能。在这种数据结构中，方法不遵循先进先出（FIFO）规则来处理数据。这种数据结构也称为双端队列，因为元素被插入到队列的末尾，并从前端移除。对于双端队列，我们只能从两端添加和删除数据。双端队列操作的时间复杂度为 O(1)。双端队列有两种类型：
输入受限
仅在一端限制输入。
允许从两端删除数据。
输出受限
仅在一端限制输出。
允许从两端插入数据。
以下是一些命令，可以帮助程序员对双端队列上的数据集执行各种操作：
push_back() - 从双端队列的末尾插入一个元素。
push_front() - 从双端队列的开头插入一个元素。
pop_back() - 从双端队列的末尾移除元素。
pop_front() - 从双端队列的开头移除元素。
front() - 返回双端队列开头处的元素。
back() - 返回双端队列末尾处的元素。
at() - 设置/返回指定索引处的元素。
size() - 返回元素的数量。
empty() - 如果双端队列为空，则返回 true。
在循环数组中，我们可以使用双端队列操作。如果数组已满，则可以从开头开始该过程。但是对于线性数组，如果数组已满，则无法再插入数据。然后我们会看到一个“溢出弹出窗口”。
双端队列的应用
双端队列有许多实际应用。
用于作业调度应用程序。
我们可以在 O(1) 时间内执行顺时针和逆时针旋转操作。
双端队列算法也存在于网页浏览器历史记录中。
用于排序中的撤销操作。
双端队列的优点
双端队列有很多优点。
我们可以从前端和后端添加和删除数据。
它们的大小是动态的。
双端队列提供了执行操作的高效时间。
这里使用 LIFO 栈。
此处无法进行重新分配。
它是一个通过适当同步实现的线程安全过程。
缓存友好。
双端队列的缺点
双端队列的缺点是
双端队列过程具有更高的内存消耗率。
它在多线程中存在同步问题。
无法在所有平台上实现。
不适合实现排序操作。
双端队列的功能数量较少。
双端队列操作的算法
步骤 1 - 考虑一个大小为 n 的双端队列数组。
步骤 2 - 设置两个指针，"front=-1" 用于前端，"rear=0" 用于设置。
此过程中有很多子部分。在双端队列中，我们可以执行多个操作。我们在这里对它们进行了总结。
在双端队列中从前端插入数据的算法：
步骤 1 - 检查前端位置。
步骤 2 - 如果 "front<1"，则将 "front=n-1" 应用于最后一个索引。
步骤 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 - 如果 rear 在前端 "rear=0"。转到前端 "rear = n-1"。
步骤 6 - 否则，rear=rear-1。
检查双端队列是否为空的算法：
步骤 1 - 如果 front=-1，则双端队列为空。
检查双端队列是否已满的算法：
步骤 1 - 如果 front=0 且 rear = n-1
步骤 2 - 或 front=rear+1
双端队列的语法
deque< object_type > deque_name;
deque<int> deque1 = {11, 21, 31, 41, 51};
deque<int> deque2 {10, 20, 30, 40, 50};
在数据结构中，双端队列继承了栈和队列的一些属性。在 C++ 中，双端队列实现为向量（vector）的向量。
使用双端队列的各种方法
方法 1 - 以一般方式实现双端队列
方法 2 - 将元素插入双端队列
方法 3 - 从双端队列访问元素
方法 4 - 更改双端队列的元素
以一般方式实现双端队列
在此 C++ 构建代码中，我们以一般方式配置了双端队列操作。在此示例中，我们在队列的后端插入了一个元素，并且整个系统已按照该方式执行。
示例 1
#include <iostream> using namespace std; #define MAX 10 class 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 << "Overflow\n" << 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 << " Overflow\n " << 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 Underflow\n" << 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 << " Underflow\n" << 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 << " Underflow\n" << endl; return -1; } return arr[front]; } int Deque::getRear() { if (isEmpty() || rear < 0) { cout << " Underflow\n" << 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: 11 after deletion of the rear element, the new rear element: 5 insert element at front end front element: 8 after deletion of front element new front element: 5
将元素插入双端队列
在此代码中，我们尝试创建 C++ 代码以将元素插入双端队列。有两种方法可以执行此操作。
push_back() - 将元素插入数组的末尾。
push_front() - 将元素插入数组的开头。
示例 2
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> 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 <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> 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: 16 Back element are here: 10 Element at index 1 present here: 7 Element at index 0 present here: 16
更改双端队列的元素
在此代码中，我们可以使用 at() 方法替换或更改该特定双端队列的元素。
示例 4
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> 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++ 的算法和可能的代码。
2K+ 浏览量
