应用、优势和缺点的双端队列

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< 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

<iostream>#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;
}

</iostream>

输出

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++可能的代码。

以上是应用、优势和缺点的双端队列的详细内容。更多信息请关注PHP中文网其他相关文章！