双端队列的应用、优点和缺点
双端队列或双端队列是一种顺序线性集合数据队列，提供类似双端队列的功能。在此数据结构中，该方法不遵循先进先出 (FIFO) 数据处理规则。此数据结构也称为双端队列，因为元素被插入到队列的末尾并从前面移除。对于双端队列，我们只能从两端添加和删除数据。双端队列操作的时间复杂度为 O(1)。有两种类型的双端队列 -
输入受限
限制单端输入。
允许从两端删除数据。
输出受限
限制单端输出。
允许将数据插入两端。
以下是一些命令，可帮助程序员对双端队列上的数据集池执行各种操作 -
push_back()-从双端队列的后面插入一个元素。
push_front()-从双端队列的前面插入一个元素。
pop_back()-从双端队列的后面删除元素双端队列。
pop_front()-从双端队列的前面删除元素。
front()-返回双端队列前面的元素。
back()-返回双端队列后面的元素。
at()-在指定索引处设置/返回。
size()-返回元素数量。
empty()-如果双端队列为空，则返回 true。
在循环数组中，我们可以使用双端队列操作。如果数组已满，那么我们可以从头开始该过程。但对于线性数组，如果数组已满，则无法插入更多数据。然后我们可以看到一个"溢出弹出窗口"。
Deque 的应用
Deque 有很多实时应用。
用于作业调度应用程序。
在 O(1) 时间内，我们可以执行顺时针和逆时针旋转操作。
Deque 算法也存在于 Web 浏览器历史记录中。
用于排序中的撤消操作。
Deque 的优势
Deque 有很多优势。
我们可以从前端和后端添加和删除数据。
它们的大小是动态的。
Deque 提供高效的计时来执行操作。
此处使用 LIFO 堆栈。
此处无法重新分配。
这是一个具有适当同步的线程安全进程。
缓存友好。
Deque 的缺点
Deque 的缺点是
Deque 进程具有更高的内存消耗率。
它与多线程存在同步问题。
无法在所有平台上实现。
不适合实现排序操作。
Deque 的功能很少。
Deque 操作的算法
步骤 1 − 考虑一个大小为 n 的 deque 数组。
步骤 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++ 中，双端队列被实现为一个向量的向量。
使用双端队列的各种方法
方法 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++ 的算法和可能的代码。
