Deque Datastruktur

I denne opplæringen lærer du hva en kø med dobbel slutt (deque) er. Du finner også arbeidseksempler på forskjellige operasjoner på en deque i C, C ++, Java og Python.

Deque eller Double Ended Queue er en type kø der innsetting og fjerning av elementer kan utføres fra forsiden eller baksiden. Dermed følger den ikke FIFO-regelen (First In First Out).

Representasjon av Deque

Typer av Deque

  • Inngangsbegrenset deque
    I denne deken er inngangen begrenset i en enkelt ende, men tillater sletting i begge ender.
  • Output Restricted Deque
    I denne deque er produksjonen begrenset i en ende, men tillater innsetting i begge ender.

Operasjoner på en Deque

Nedenfor er implementering av deque i sirkulær matrise. I en sirkulær matrise, hvis matrisen er full, starter vi fra begynnelsen.

Men i en lineær matriximplementering, hvis matrisen er full, kan ikke flere elementer settes inn. Hvis matrisen er full i hver av operasjonene nedenfor, kastes "overløpsmelding".

Før du utfører følgende operasjoner, følges disse trinnene.

  1. Ta en matrise (deque) av størrelse n.
  2. Sett to pekere på første posisjon og sett front = -1og rear = 0.
Initialiser en matrise og pekere for deque

1. Sett inn foran

Denne operasjonen legger til et element foran.

  1. Kontroller posisjonen til fronten. Kontroller posisjonen til fronten
  2. Hvis front < 1, initialiser på nytt front = n-1(siste indeks). Skift front til slutten
  3. Ellers reduseres fronten med 1.
  4. Legg til den nye nøkkelen 5 i array(front). Sett inn elementet foran

2. Sett inn bak

Denne operasjonen legger til et element bak.

  1. Sjekk om matrisen er full. Sjekk om deque er full
  2. Hvis dekalen er full, start på nytt rear = 0.
  3. Annet, øk bakover med 1. Øk bak
  4. Legg til den nye nøkkelen 5 i array(rear). Sett inn elementet bak

3. Slett fra fronten

Operasjonen sletter et element fra fronten.

  1. Sjekk om dekken er tom. Sjekk om deque er tom
  2. Hvis deque er tom (dvs. front = -1), kan ikke sletting utføres ( understrømningsforhold ).
  3. Hvis dekken bare har ett element (dvs. front = rear), sett front = -1og rear = -1.
  4. Ellers hvis fronten er på slutten (dvs. front = n - 1), sett gå til fronten front = 0.
  5. Else, front = front + 1. Øk fronten

4. Slett bakfra

Denne operasjonen sletter et element bakfra.

  1. Sjekk om dekken er tom. Sjekk om deque er tom
  2. Hvis deque er tom (dvs. front = -1), kan ikke sletting utføres ( understrømningsforhold ).
  3. Hvis dekken bare har ett element (dvs. front = rear), sett front = -1og rear = -1følg trinnene nedenfor.
  4. Hvis bak er foran (dvs. rear = 0), må du gå til fronten rear = n - 1.
  5. Else, rear = rear - 1. Reduser bakpartiet

5. Merk av for Tom

Denne operasjonen sjekker om dekken er tom. Hvis front = -1deken er tom.

6. Merk av for Full

Denne operasjonen kontrollerer om dekningen er full. Hvis front = 0og rear = n - 1ELLER front = rear + 1, er deken full.

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

Tidskompleksitet

Tiden kompleksitet alle de ovennevnte operasjonene er konstant altså O(1).

Anvendelser av Deque Datastruktur

  1. Ved angre på programvare.
  2. For å lagre historikk i nettlesere.
  3. For å implementere både stabler og køer.

Interessante artikler...