logo

TechCodeview

Deque (oder doppelendige Warteschlange)

In diesem Artikel besprechen wir die doppelendige Warteschlange oder Deque. Wir sollten zunächst eine kurze Beschreibung der Warteschlange sehen.

Was ist eine Warteschlange?

Eine Warteschlange ist eine Datenstruktur, in der alles, was zuerst kommt, zuerst rausgeht, und sie folgt der FIFO-Richtlinie (First-In-First-Out). Das Einfügen in die Warteschlange erfolgt von einem Ende aus, dem so genannten hinteres Ende oder der Schwanz, wohingegen die Löschung von einem anderen Ende aus erfolgt, das als „ Frontend oder der Kopf der Warteschlange.

Java-Datum zum String

Das reale Beispiel einer Warteschlange ist die Ticketwarteschlange vor einem Kinosaal, bei der die Person, die zuerst in die Warteschlange eintritt, zuerst die Karte erhält und die Person, die zuletzt in die Warteschlange eintritt, die Karte zuletzt erhält.

Was ist eine Deque (oder doppelendige Warteschlange)?

Das Deque steht für Double Ended Queue. Deque ist eine lineare Datenstruktur, bei der die Einfüge- und Löschvorgänge von beiden Enden aus ausgeführt werden. Wir können sagen, dass Deque eine verallgemeinerte Version der Warteschlange ist.

Obwohl das Einfügen und Löschen in einer Doppelschlange an beiden Enden durchgeführt werden kann, folgt es nicht der FIFO-Regel. Die Darstellung einer Deque ist wie folgt gegeben:

Deque (oder doppelendige Warteschlange)

Arten von Deque

Es gibt zwei Arten von Deques:

  • Eingabebeschränkte Warteschlange
  • Ausgabebeschränkte Warteschlange

Eingabebeschränkte Warteschlange

In einer eingabebeschränkten Warteschlange kann der Einfügevorgang nur an einem Ende durchgeführt werden, während der Löschvorgang an beiden Enden durchgeführt werden kann.

Deque (oder doppelendige Warteschlange)

Ausgabebeschränkte Warteschlange

In einer ausgabebeschränkten Warteschlange kann der Löschvorgang nur an einem Ende durchgeführt werden, während das Einfügen an beiden Enden erfolgen kann.

Deque (oder doppelendige Warteschlange)

Auf Deque ausgeführte Operationen

Es gibt die folgenden Operationen, die auf eine Deque angewendet werden können:

  • Einschub vorne
  • Einschub hinten
  • Löschung vorne
  • Löschung hinten

Wir können neben den oben aufgeführten Operationen auch Peek-Operationen in der Deque durchführen. Durch die Peek-Operation können wir die vorderen und hinteren Elemente der Deque abrufen. Zusätzlich zu den oben genannten Operationen werden in Deque auch die folgenden Operationen unterstützt:

Muschelsortierung
  • Holen Sie sich den vorderen Gegenstand aus der Deque
  • Holen Sie sich den hinteren Gegenstand aus der Deque
  • Überprüfen Sie, ob die Deque voll ist oder nicht
  • Überprüft, ob die Deque leer ist oder nicht

Lassen Sie uns nun anhand eines Beispiels die für deque ausgeführte Operation verstehen.

Einschub am vorderen Ende

Bei dieser Operation wird das Element vom vorderen Ende der Warteschlange eingefügt. Bevor wir die Operation durchführen, müssen wir zunächst prüfen, ob die Warteschlange voll ist oder nicht. Wenn die Warteschlange nicht voll ist, kann das Element unter Verwendung der folgenden Bedingungen vom Frontend aus eingefügt werden:

  • Wenn die Warteschlange leer ist, werden sowohl hinten als auch vorne mit 0 initialisiert. Jetzt zeigen beide auf das erste Element.
  • Andernfalls überprüfen Sie die Position der Vorderseite, wenn die Vorderseite kleiner als 1 ist (vorne).<1), then reinitialize it by front = n - 1 , d. h. der letzte Index des Arrays.
Deque (oder doppelendige Warteschlange)

Einschub am hinteren Ende

wichtig

Bei dieser Operation wird das Element vom hinteren Ende der Warteschlange eingefügt. Bevor wir die Operation durchführen, müssen wir zunächst noch einmal prüfen, ob die Warteschlange voll ist oder nicht. Wenn die Warteschlange nicht voll ist, kann das Element unter Verwendung der folgenden Bedingungen vom hinteren Ende eingefügt werden:

  • Wenn die Warteschlange leer ist, werden sowohl hinten als auch vorne mit 0 initialisiert. Jetzt zeigen beide auf das erste Element.
  • Andernfalls erhöhen Sie die Rückseite um 1. Wenn die Rückseite den letzten Index (oder die Größe - 1) hat, müssen wir sie, anstatt sie um 1 zu erhöhen, auf 0 setzen.
Deque (oder doppelendige Warteschlange)

Löschung am Frontend

Bei diesem Vorgang wird das Element vom vorderen Ende der Warteschlange gelöscht. Bevor wir die Operation implementieren, müssen wir zunächst prüfen, ob die Warteschlange leer ist oder nicht.

Wenn die Warteschlange leer ist, d. h. front = -1, liegt eine Unterlaufbedingung vor und wir können den Löschvorgang nicht durchführen. Wenn die Warteschlange nicht voll ist, kann das Element unter Verwendung der folgenden Bedingungen vom Frontend aus eingefügt werden:

Wenn die Doppelschlange nur ein Element hat, setzen Sie hinten = -1 und vorne = -1.

Andernfalls, wenn die Vorderseite am Ende ist (das heißt Vorderseite = Größe - 1), setzen Sie Vorderseite = 0.

Gleichheit von Strings in Java

Andernfalls erhöhen Sie die Vorderseite um 1 (d. h. Vorderseite = Vorderseite + 1).

Deque (oder doppelendige Warteschlange)

Löschung am hinteren Ende

Bei diesem Vorgang wird das Element vom hinteren Ende der Warteschlange gelöscht. Bevor wir die Operation implementieren, müssen wir zunächst prüfen, ob die Warteschlange leer ist oder nicht.

Wenn die Warteschlange leer ist, d. h. front = -1, liegt eine Unterlaufbedingung vor und wir können den Löschvorgang nicht durchführen.

Wenn die Doppelschlange nur ein Element hat, setzen Sie hinten = -1 und vorne = -1.

Wenn hinten = 0 (hinten ist vorne), dann setze hinten = n - 1.

Andernfalls verringern Sie die Rückseite um 1 (oder Rückseite = Rückseite -1).

Deque (oder doppelendige Warteschlange)

Überprüfen Sie, ob es leer ist

Dieser Vorgang wird ausgeführt, um zu überprüfen, ob die Deque leer ist oder nicht. Wenn front = -1 bedeutet, dass die Deque leer ist.

Scheck voll

Dieser Vorgang wird ausgeführt, um zu überprüfen, ob die Deque voll ist oder nicht. Wenn vorne = hinten + 1 oder vorne = 0 und hinten = n - 1, bedeutet dies, dass die Deque voll ist.

Die zeitliche Komplexität aller oben genannten Operationen der Deque ist O(1), also konstant.

Anwendungen von Deque

  • Deque kann sowohl als Stack als auch als Warteschlange verwendet werden, da es beide Operationen unterstützt.
  • Deque kann als Palindromprüfer verwendet werden. Wenn wir die Zeichenfolge von beiden Enden lesen, wäre die Zeichenfolge dieselbe.

Implementierung von Deque

Sehen wir uns nun die Implementierung von deque in der Programmiersprache C an.

diskrete mathematische Negation 
 #include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf(&apos;
Elements in a deque are: &apos;); while(i!=r) { printf(&apos;%d &apos;,deque[i]); i=(i+1)%size; } printf(&apos;%d&apos;,deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at front is: %d&apos;, deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at rear is %d&apos;, deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=0; } else { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[r]); f=-1; r=-1; } else if(r==0) { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=size-1; } else { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; }

Ausgabe:

Deque (oder doppelendige Warteschlange)

Das ist also alles über den Artikel. Ich hoffe, der Artikel wird für Sie hilfreich und informativ sein.