Deque Datastruktur

I denna handledning lär du dig vad en kö med dubbla ändar (deque) är. Du hittar också arbetsexempel på olika operationer på en deque i C, C ++, Java och Python.

Deque eller Double Ended Queue är en typ av kö där insättning och borttagning av element kan utföras antingen framifrån eller bakifrån. Således följer den inte FIFO-regeln (First In First Out).

Representation för Deque

Typer av Deque

  • Input Restricted Deque
    I denna deque är ingången begränsad i en enda ände men tillåter radering i båda ändarna.
  • Output Restricted Deque
    I denna deque är output begränsad i en enda ände men möjliggör insättning i båda ändarna.

Operationer på en Deque

Nedan följer implementeringen av deque. I en cirkulär matris, om matrisen är full, börjar vi från början.

Men i en linjär arrayimplementering, om arrayen är full, kan inga fler element infogas. I varje operation nedan, kastas "överflödsmeddelande" om matrisen är full.

Innan du utför följande åtgärder följs dessa steg.

  1. Ta en matris (deque) av storlek n.
  2. Ställ in två pekare vid första positionen och ställ in front = -1och rear = 0.
Initiera en matris och pekare för deque

1. Sätt i fronten

Denna åtgärd lägger till ett element på framsidan.

  1. Kontrollera frontens läge. Kontrollera frontens läge
  2. Om front < 1, återinitialisera front = n-1(senaste index). Flytta fram till slutet
  3. Annars minskar du fronten med 1.
  4. Lägg till den nya nyckeln 5 i array(front). Sätt in elementet fram

2. Sätt in på baksidan

Denna operation lägger till ett element bak.

  1. Kontrollera om matrisen är full. Kontrollera om deque är full
  2. Om dekalen är full, starta om rear = 0.
  3. Annars, öka bakåt med 1. Öka bak
  4. Lägg till den nya nyckeln 5 i array(rear). Sätt in elementet på baksidan

3. Ta bort från fronten

Operationen raderar ett element framifrån.

  1. Kontrollera om dekalen är tom. Kontrollera om deque är tom
  2. Om deken är tom (dvs. front = -1) kan raderingen inte utföras ( underflödesförhållande ).
  3. Om deken bara har ett element (dvs. front = rear), ställ in front = -1och rear = -1.
  4. Annars om fronten är i slutet (dvs. front = n - 1), ställ in gå framåt front = 0.
  5. Else, front = front + 1. Öka fronten

4. Ta bort bakifrån

Denna åtgärd tar bort ett element bakifrån.

  1. Kontrollera om dekalen är tom. Kontrollera om deque är tom
  2. Om deken är tom (dvs. front = -1) kan raderingen inte utföras ( underflödesförhållande ).
  3. Om deketten bara har ett element (dvs. front = rear), ställ in front = -1och rear = -1följ annars stegen nedan.
  4. Om baksidan är framtill (dvs. rear = 0), ställ in framåt rear = n - 1.
  5. Else, rear = rear - 1. Minska den bakre delen

5. Markera Tom

Den här åtgärden kontrollerar om deken är tom. Om front = -1, deken är tom.

6. Markera Full

Denna åtgärd kontrollerar om deken är full. Om front = 0och rear = n - 1ELLER front = rear + 1är deken full.

Deque Implementation i Python, Java, C och 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; )

Tidskomplexitet

Tids komplexiteten av ovanstående operationer är konstant, dvs O(1).

Tillämpningar av Deque Datastruktur

  1. Ångra operationer på programvara.
  2. För att lagra historik i webbläsare.
  3. För att implementera både stackar och köer.

Intressanta artiklar...