double ended queue c with examples
Ein ausführliches Tutorial zu Deque oder Double-Ended Queue in C ++. Das Tutorial erklärt, was Deque, grundlegende Operationen, C ++ & Java-Implementierung und -Anwendungen sind:
Double Ended Queue oder einfach 'Deque' genannt ist eine verallgemeinerte Version von Queue.
Der Unterschied zwischen Queue und Deque besteht darin, dass es nicht dem FIFO-Ansatz (First In, First Out) folgt. Das zweite Merkmal von Deque ist, dass wir Elemente entweder am vorderen oder am hinteren Ende einfügen und entfernen können.
=> Lesen Sie die Easy C ++ - Schulungsserie durch
Was du lernen wirst:
- Double Ended Queue Classification
- Grundlegende Touch-Operationen
- und Illustration
- und Implementierung
- Anwendungen
- Fazit
- Literatur-Empfehlungen
Double Ended Queue Classification
Deque kann wie folgt klassifiziert werden:
Eingaben mit eingeschränkter Berührung; Bei Eingabebeschränkung kann das Löschen an beiden Enden erfolgen, das Einfügen jedoch nur am hinteren Ende der Warteschlange.
Ausgabebeschränkte Deque: In der ausgabebeschränkten Warteschlange kann das Einfügen von beiden Enden aus erfolgen, das Löschen erfolgt jedoch nur an einem Ende, d. H. Am vorderen Ende der Warteschlange.
Wir können auch Stapel und Warteschlangen mit deque implementieren.
Grundlegende Touch-Operationen
Im Folgenden sind die grundlegenden Vorgänge aufgeführt, die für die Deque ausgeführt werden können.
- Vorderseite einfügen: Fügen Sie einen Gegenstand an der Vorderseite der Deque ein oder fügen Sie ihn hinzu.
- insertLast: Fügen Sie einen Gegenstand an der Rückseite der Deque ein oder fügen Sie ihn hinzu.
- deleteFront: Löschen oder entfernen Sie das Element an der Vorderseite der Warteschlange.
- Letzte löschen: Löschen oder entfernen Sie das Element von der Rückseite der Warteschlange.
- getFront: Ruft das vordere Element in der Deque ab.
- getLast: Ruft das letzte Element in der Warteschlange ab.
- ist leer: Überprüft, ob die Deque leer ist.
- ist voll: Überprüft, ob die Deque voll ist.
und Illustration
Eine leere Deque wird wie folgt dargestellt:
wie man eine Binärdatei öffnet
Als nächstes fügen wir vorne Element 1 ein.
Jetzt fügen wir Element 3 hinten ein.
Als nächstes fügen wir Element 5 zur Vorderseite hinzu und wenn es erhöht wird, zeigen die vorderen Punkte auf 4.
Dann fügen wir die Elemente 7 hinten und 9 vorne ein. Die Deque sieht wie unten gezeigt aus.
Als nächstes entfernen wir ein Element von der Vorderseite.
Wir sehen also, dass beim Einfügen der Elemente an der Vorderseite die vordere Position verringert wird, während sie beim Entfernen eines Elements erhöht wird. Für das hintere Ende wird die Position zum Einsetzen erhöht und zum Entfernen verringert .
und Implementierung
100 ++ Touch-Implementierung
Wir können eine Deque in C ++ mithilfe von Arrays sowie einer verknüpften Liste implementieren. Abgesehen davon verfügt die Standard Template Library (STL) über eine Klasse „deque“, die alle Funktionen für diese Datenstruktur implementiert.
Die Array-Implementierung der Deque ist unten angegeben. Da es sich um eine Warteschlange mit zwei Enden handelt, haben wir für die Implementierung zirkuläre Arrays verwendet.
Präprozessor-Direktiven in c ++ mit Beispiel
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!!
' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; dq.insertrear(3); cout << 'rear element of deque ' << ' ' << dq.getRear() << endl; dq.deleterear(); cout << 'After deleterear, rear = ' << dq.getRear() << endl; cout << 'inserting element 5 at front end
'; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; } Ausgabe:
Setzen Sie Element 1 am hinteren Ende ein
Element 3 am hinteren Ende einsetzen
hinteres Element der Deque 3
Nach dem Löschen ist hinten = 1
Einfügen von Element 5 am vorderen Ende
vorderes Element der Deque 5
Nach deletefront ist front = 1
Nachzählung der Java-Implementierung
Die Deque-Schnittstelle in Java, 'java.util.Deque', ist von der Schnittstelle 'java.util.Queue' abgeleitet. Deque kann als Warteschlange (First In, First Out) oder als Stack (Last In, First Out) verwendet werden. Diese Implementierungen arbeiten schneller als die verknüpfte Liste.
Im Folgenden ist die Hierarchie für die Deque-Schnittstelle in Java angegeben.
Wir müssen uns einige Punkte über die Deque-Oberfläche in Java merken:
- Die Implementierung ist nicht threadsicher, da keine externe Synchronisation erfolgt.
- Deque unterstützt nicht die gleichzeitige Verwendung mehrerer Threads.
- Deques, die mithilfe von Arrays implementiert wurden, erlauben nicht die Verwendung von NULL-Elementen.
- Arrays können gemäß den Anforderungen wachsen, wobei die uneingeschränkte Kapazität und die Unterstützung von anpassbaren Arrays die beiden wichtigsten Funktionen sind.
Im Folgenden sind die verschiedenen Methoden aufgeführt, die von der Deque-Schnittstelle unterstützt werden:
oracle pl sql Interview Fragen und Antworten für erfahrene
| Nein. | Methode | Beschreibung |
|---|---|---|
| 7 | iterator () | Gibt einen Iterator für die Deque zurück. |
| ein | add (Element) | Fügt dem Schwanz ein Element hinzu. |
| zwei | addFirst (Element) | Fügt dem Kopf / der Vorderseite ein Element hinzu. |
| 3 | addLast (Element) | Fügt dem Heck / Heck ein Element hinzu. |
| 4 | Angebot (Element) | Fügt dem Schwanz ein Element hinzu; Gibt einen booleschen Wert zurück, um anzuzeigen, ob das Einfügen erfolgreich war. |
| 5 | OfferFirst (Element) | Fügt dem Kopf ein Element hinzu. Gibt einen booleschen Wert zurück, um anzuzeigen, ob das Einfügen erfolgreich war. |
| 6 | quoteLast (Element) | Fügt dem Schwanz ein Element hinzu; Gibt einen booleschen Wert zurück, um anzuzeigen, ob das Einfügen erfolgreich war. |
| 8 | descendingIterator () | Gibt einen Iterator zurück, der die umgekehrte Reihenfolge für diese Deque hat. |
| 9 | push (Element) | Fügt dem Kopf der Deque ein Element hinzu. |
| 10 | Pop (Element) | Entfernt ein Element vom Kopf der Deque und gibt es zurück. |
| elf | removeFirst () | Entfernt das Element am Kopf der Deque. |
| 12 | removeLast () | Entfernt das Element am Ende der Deque. |
| 13 | Umfrage() | Ruft das erste Element der Deque ab und entfernt es (dargestellt durch den Kopf der Deque). Gibt NULL zurück, wenn die Deque leer ist. |
| 14 | pollFirst () | Ruft das erste Element dieser Deque ab und entfernt es. Gibt null zurück, wenn diese Deque leer ist. |
| fünfzehn | pollLast () | Ruft das letzte Element dieser Deque ab und entfernt es. Gibt null zurück, wenn diese Deque leer ist. |
| 16 | spähen() | Ruft den Kopf (erstes Element der Deque) der Warteschlange ab, die durch diese Deque dargestellt wird. Gibt null zurück, wenn diese Deque leer ist. Hinweis: Durch diesen Vorgang wird das Element nicht entfernt. |
| 17 | peekFirst () | Ruft das erste Element dieser Deque ab. Gibt null zurück, wenn diese Deque leer ist. Hinweis: Durch diesen Vorgang wird das Element nicht entfernt. |
| 18 | peekLast () | Ruft das letzte Element dieser Deque ab oder gibt null zurück, wenn diese Deque leer ist. Hinweis: Durch diesen Vorgang wird das Element nicht entfernt. |
Die folgende Java-Implementierung zeigt die verschiedenen oben beschriebenen Vorgänge.
import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } Ausgabe:
Und die (11, 7, 3, 1, 5, 9, 13)
Standard-Iterator
11 7 3 1 5 9 13
Iterator umkehren
13 9 5 1 3 7 11
Peek 11
Nach dem Blick: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Nach dem Pop: (7, 3, 1, 5, 9, 13)
Enthält Element 3?: True
Deque nach dem Entfernen des ersten und letzten Elements: (3, 1, 5, 9)
Im obigen Programm haben wir die Deque-Schnittstelle von Java verwendet und eine Deque von ganzzahligen Elementen definiert. Dann haben wir verschiedene Operationen an dieser Deque durchgeführt und die Ergebnisse dieser Operationen ausgegeben.
Anwendungen
Deque kann in einigen der folgenden Anwendungen verwendet werden.
# 1) Planungsalgorithmus: Ein Planungsalgorithmus, 'A-Steal-Planungsalgorithmus', implementiert die Aufgabenplanung für verschiedene Prozessoren im Multiprozessorsystem. Diese Implementierung verwendet deque und der Prozessor erhält das erste Element aus der deque zur Ausführung.
# 2) Liste der Aktivitäten rückgängig machen: In Softwareanwendungen haben wir viele Aktionen. Einer ist 'Rückgängig'. Wenn wir die Aktion mehrmals rückgängig gemacht haben, werden alle diese Aktionen in einer Liste gespeichert. Diese Liste wird als Deque gepflegt, damit wir Einträge von jedem Ende aus problemlos hinzufügen / entfernen können.
#3) Entfernen Sie die Einträge nach einiger Zeit: Apps aktualisieren Einträge in ihrer Liste wie Apps, in denen die Lagereinträge aufgelistet sind usw. Diese Apps entfernen die Einträge nach einiger Zeit und fügen auch neue Einträge ein. Dies erfolgt mit einer Deque.
Fazit
Deque ist eine Warteschlange mit zwei Enden, mit der wir Elemente an beiden Enden, d. H. Vorne und hinten, der Warteschlange hinzufügen / entfernen können. Deque kann mithilfe von Arrays oder verknüpften Listen implementiert werden. Wir haben jedoch auch eine STL-Klasse (Standard Template Library), die die verschiedenen Operationen der Deque implementiert.
In Java haben wir eine Deque-Schnittstelle, die von der Warteschlangenschnittstelle geerbt wird, um Deque zu implementieren. Abgesehen von den grundlegenden Standardoperationen des Deque unterstützt diese Schnittstelle verschiedene andere Operationen, die mit Deque ausgeführt werden können.
Deque wird im Allgemeinen für Anwendungen verwendet, bei denen Elemente an beiden Enden hinzugefügt / entfernt werden müssen. Es wird auch hauptsächlich bei der Planung von Prozessoren in Multiprozessorsystemen verwendet.
=> Schauen Sie sich die komplette C ++ - Schulungsserie an
Literatur-Empfehlungen
- Prioritätswarteschlange In STL
- Was ist ein Vergleichstest (Lernen mit Beispielen)
- Python DateTime Tutorial mit Beispielen
- Shell-Sortierung in C ++ mit Beispielen
- Befehl in Unix mit Beispielen ausschneiden
- Unix Cat-Befehlssyntax, Optionen mit Beispielen
- Verwendung des Cursors in MongoDB mit Beispielen
- Ls-Befehl unter Unix mit Beispielen