Anwendungen, Vor- und Nachteile von Deque

Deque oder doppelendige Warteschlange ist eine sequentielle lineare Datenerfassungswarteschlange, die ähnliche Funktionen wie eine doppelendige Warteschlange bietet. In dieser Datenstruktur folgt die Methode nicht der First-In-First-Out-Regel (FIFO) für die Datenverarbeitung. Diese Datenstruktur wird auch Deque genannt, da Elemente am Ende der Warteschlange eingefügt und an der Vorderseite entfernt werden. Mit einer Deque können wir Daten nur an beiden Enden hinzufügen und entfernen. Die zeitliche Komplexität der Deque-Operation beträgt O(1). Es gibt zwei Arten von Deque -

• Die Eingabe ist begrenzt

• Single-Ended-Eingabelimit.

• Ermöglicht das Löschen von Daten von beiden Enden.

• Ausgabe begrenzt

• Single-Ended-Ausgabelimit.

• Ermöglicht das Einfügen von Daten an beiden Enden.

Die folgenden Befehle helfen Programmierern bei der Durchführung verschiedener Vorgänge mithilfe des Datensatz-Poolings auf einer Deque -

• push_back() – Fügt ein Element von der Rückseite der Deque ein.

• push_front() – Fügt ein Element von der Vorderseite der Deque ein.

• pop_back() – Entfernt Elemente von der Rückseite einer Deque.

• pop_front() – Entfernt Elemente von der Vorderseite der Deque.

• front() – Gibt das vordere Element der Deque zurück.

• back() – Gibt das Element am Ende der Deque zurück.

• at() – Setzt/gibt den angegebenen Index zurück.

• size() – Gibt die Anzahl der Elemente zurück.

• empty() – Gibt true zurück, wenn die Deque leer ist.

In einem kreisförmigen Array können wir die Deque-Operation verwenden. Wenn das Array voll ist, können wir den Prozess von vorne beginnen. Wenn das Array jedoch voll ist, können bei einem linearen Array keine weiteren Daten eingefügt werden. Dann sehen wir ein „Überlauf-Popup“.

Anwendung der doppelendigen Warteschlange

Deque verfügt über viele Echtzeitanwendungen.

• Für die Bewerbung zur Arbeitsplanung.

• Wir können Rotationsoperationen im und gegen den Uhrzeigersinn in O(1)-Zeit durchführen.

• Der Deque-Algorithmus ist auch im Webbrowser-Verlauf vorhanden.

• Zum Rückgängigmachen von Sortiervorgängen.

Vorteile der doppelendigen Warteschlange

Deque hat viele Vorteile.

• Wir können Daten von der Vorder- und Rückseite hinzufügen und löschen.

• Ihre Größe ist dynamisch.

• Deque bietet ein effizientes Timing für die Durchführung von Vorgängen.

• LIFO-Stack wird hier verwendet.

• Umverteilung ist hier nicht möglich.

• Dies ist ein Thread-sicherer Prozess mit ordnungsgemäßer Synchronisierung.

• Cache-freundlich.

Nachteile der doppelseitigen Warteschlange

Die Nachteile der doppelseitigen Warteschlange sind

• Die Speicherverbrauchsrate des Deque-Prozesses ist hoch.

• Es gibt Probleme mit der Multithread-Synchronisierung.

• Nicht auf allen Plattformen verfügbar.

• Nicht für die Durchführung von Sortiervorgängen geeignet.

• Deque hat weniger Funktionen.

Algorithmus des Double-Ended-Queue-Betriebs

• Schritt 1 – Betrachten Sie ein Deque-Array der Größe n.

• Schritt 2 – Setzen Sie die beiden Zeiger auf „front=-1“ (bedeutet vorne) und „rear=0“ (bedeutet gesetzt).

Dieser Prozess besteht aus vielen Unterabschnitten. Wir können mehrere Operationen in einer Deque ausführen. Wir fassen sie hier zusammen.

• Algorithmus zum Einfügen von Daten von vorne in Deque:-

• Schritt 1 – Überprüfen Sie die vordere Position.

• Schritt 2 – Wenn „front

• Schritt 3 – Ansonsten müssen wir „vorne“ um 1 reduzieren.

• Schritt 4 – Fügen Sie das neue Schlüsselelement an der Vorderseite des Arrays hinzu.

• Algorithmus zum Einfügen von Daten nach Deque:-

• Schritt 1 – Überprüfen Sie, ob das Array voll ist.

• Schritt 2 – Wenn voll, wenden Sie „hinten=0“ an.

• Schritt 3 – Andernfalls erhöhen Sie den Wert von „hinten“ um 1.

• Schritt 4 – Fügen Sie den neuen Schlüssel erneut zu „array[rear]“ hinzu.

• Algorithmus zum Löschen von Daten vor der Deque:-

• Schritt 1 – Überprüfen Sie, ob die Deque leer ist.

• Schritt 2 – Wenn die Liste leer ist („front=-1“), handelt es sich um eine Unterlaufbedingung und das Löschen kann nicht durchgeführt werden.

• Schritt 3 – Wenn die Deque nur ein Element enthält. Dann „vorne=hinten=-1“.

• Schritt 4 – Ansonsten steht „front“ am Ende, dann auf „front=0“ setzen.

• Schritt 5 – Ansonsten gilt: vorne=vorne+1.

• Algorithmus zum Löschen von Daten von der Rückseite der Deque:-

• Schritt 1 – Überprüfen Sie, ob die Deque leer ist.

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

Das obige ist der detaillierte Inhalt vonAnwendungen, Vor- und Nachteile von Deque. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!