Deque-Datenstruktur

In diesem Tutorial erfahren Sie, was eine Double-Ended-Warteschlange (Deque) ist. Außerdem finden Sie Arbeitsbeispiele für verschiedene Operationen an einer Deque in C, C ++, Java und Python.

Deque oder Double Ended Queue ist eine Art von Warteschlange, in der das Einfügen und Entfernen von Elementen entweder von vorne oder von hinten erfolgen kann. Somit folgt es nicht der FIFO-Regel (First In First Out).

Darstellung von Deque

Arten von Deque

Eingangsbeschränkte Deque
In dieser Deque ist die Eingabe an einem einzelnen Ende beschränkt, ermöglicht jedoch das Löschen an beiden Enden.
Ausgabebeschränkte
Deque Bei dieser Deque ist die Ausgabe an einem einzelnen Ende beschränkt, ermöglicht jedoch das Einfügen an beiden Enden.

Operationen an einem Deque

Unten ist die Implementierung von deque für kreisförmige Arrays dargestellt. Wenn das Array in einem kreisförmigen Array voll ist, beginnen wir von vorne.

Wenn das Array in einer linearen Array-Implementierung voll ist, können keine weiteren Elemente eingefügt werden. Wenn das Array in jedem der folgenden Vorgänge voll ist, wird eine "Überlaufnachricht" ausgelöst.

Bevor Sie die folgenden Vorgänge ausführen, werden diese Schritte ausgeführt.

Nehmen Sie ein Array (deque) der Größe n.
Setzen Sie zwei Zeiger an die erste Position und setzen Sie front = -1und rear = 0.

Initialisieren Sie ein Array und Zeiger für deque

1. Vorne einsetzen

Diese Operation fügt vorne ein Element hinzu.

Überprüfen Sie die Position der Vorderseite. Überprüfen Sie die Position der Vorderseite
Wenn front < 1, neu initialisieren front = n-1(letzter Index). Vorne bis zum Ende verschieben
Andernfalls verringern Sie die Vorderseite um 1.
Fügen Sie den neuen Schlüssel 5 hinzu array(front). Setzen Sie das Element vorne ein

2. Setzen Sie hinten ein

Diese Operation fügt der Rückseite ein Element hinzu.

Überprüfen Sie, ob das Array voll ist. Überprüfen Sie, ob die Deque voll ist
Wenn die Deque voll ist, initialisieren Sie sie erneut rear = 0.
Andernfalls erhöhen Sie das Heck um 1. Erhöhen Sie das Heck
Fügen Sie den neuen Schlüssel 5 hinzu array(rear). Setzen Sie das Element hinten ein

3. Von vorne löschen

Die Operation löscht ein Element von vorne.

Überprüfen Sie, ob die Deque leer ist. Überprüfen Sie, ob die Deque leer ist
Wenn die Deque leer ist (dh front = -1), kann das Löschen nicht durchgeführt werden ( Unterlaufbedingung ).
Wenn die Deque nur ein Element hat (dh front = rear), setzen Sie front = -1und rear = -1.
Andernfalls, wenn die Vorderseite am Ende ist (dh front = n - 1), gehen Sie nach vorne front = 0.
Sonst , front = front + 1. Erhöhen Sie die Front

4. Löschen Sie von hinten

Diese Operation löscht ein Element von hinten.

Überprüfen Sie, ob die Deque leer ist. Überprüfen Sie, ob die Deque leer ist
Wenn die Deque leer ist (dh front = -1), kann das Löschen nicht durchgeführt werden ( Unterlaufbedingung ).
Wenn die Deque nur ein Element hat (dh front = rear), setzen Sie front = -1und rear = -1, sonst befolgen Sie die folgenden Schritte.
Wenn sich hinten vorne befindet (dh rear = 0), gehen Sie nach vorne rear = n - 1.
Sonst , rear = rear - 1. Verringern Sie das Heck

5. Überprüfen Sie Leer

Diese Operation prüft, ob die Deque leer ist. Wenn front = -1, ist die Deque leer.

6. Vollständig prüfen

Diese Operation prüft, ob die Deque voll ist. Wenn front = 0und rear = n - 1ODER front = rear + 1, ist die Deque voll.

Deque-Implementierung in Python, Java, C und C ++

Python Java C C ++

 # Deque implementaion in python class Deque: def __init__(self): self.items = () def isEmpty(self): return self.items == () def addRear(self, item): self.items.append(item) def addFront(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items)

 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )

 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )

 // Deque implementation in C++ #include 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" << 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 " << 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" << 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" << 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" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; 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 "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )