Gruntle Software & Testing

Av Stewart TristianPublicerad den Publicerad i Guider

En djupgående handledning om Deque eller Double-ended Queue i C++. Handledningen förklarar vad Deque är, grundläggande operationer, implementering och tillämpningar i C++ & Java:

Dubbelkö eller helt enkelt kallad "Deque" är en generaliserad version av kö.

Skillnaden mellan Queue och Deque är att de inte följer FIFO-principen (First In, First Out). Den andra egenskapen hos Deque är att vi kan infoga och ta bort element från antingen främre eller bakre änden.

Klassificering av dubbla köer

Deque kan klassificeras enligt följande:

Ingångsbegränsad Deque: Vid inmatningsbegränsning kan radering ske från båda ändarna, men insättning kan endast ske i den bakre änden av kön.

Utgångsbegränsad Deque: I en kö med begränsad utdata kan man lägga in filer i båda ändarna, men radering sker bara i en ände, dvs. i den främre änden av kön.

Vi kan också implementera staplar och köer med hjälp av deque.

Grundläggande Deque-operationer

Följande är de grundläggande operationer som kan utföras på deque.

  • Insats framsida: Infoga eller lägga till ett objekt i början av deque.
  • insertLast: Infoga eller lägga till ett objekt i den bakre delen av deque.
  • deleteFront: Ta bort eller ta bort objektet från början av kön.
  • radera sist: Ta bort eller ta bort objektet från den bakre delen av kön.
  • getFront: Hämtar det första objektet i deque.
  • getLast: Hämtar det sista objektet i kön.
  • isEmpty: Kontrollerar om deque är tom.
  • isFull: Kontrollerar om deque är full.

Deque Illustration

En tom deque representeras på följande sätt:

Därefter infogar vi element 1 längst fram.

Nu sätter vi in element 3 på baksidan.

Därefter lägger vi till element 5 på framsidan och när det ökas pekar framsidan på 4.

Sedan infogar vi elementen 7 längst bak och 9 längst fram. Deque-filen kommer att se ut som nedan.

Därefter tar vi bort ett element från framsidan.

Vi ser alltså att när elementen sätts in i framsidan minskas den främre positionen medan den ökas när ett element tas bort. För den bakre delen ökas positionen vid insättning och minskas vid borttagning. .

Genomförande av Deque

Implementering av C++ Deque

Vi kan implementera en deque i C++ med hjälp av matriser och länkade listor. Dessutom har Standard Template Library (STL) en klass "deque" som implementerar alla funktioner för denna datastruktur.

Arrayimplementationen av deque ges nedan. Eftersom det är en kö med dubbla ändar har vi använt cirkulära arrayer för implementationen. 

 #include  using namespace std; #define MAX_size 10 // Maximal storlek på array eller Dequeue // Deque-klass class class Deque { int array[MAX_size]; int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operationer på Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Kontrollera om Deque ärfull bool isFull() return ((front == 0 && rear == size-1) // Kontrollera om kö är tom bool isEmpty(){ return (front == -1); } } }; // Infoga ett element längst fram i kön void Deque::insertfront(int key) { if (isFull())) { cout <<"Overflow!!\n" <<<endl; return; } } // Om kön är tom till en början, ställ in front=rear=0; början av kön om (front == -1) { front = 0; rear = 0; } else if(front == 0) // front är första positionen i kön front = size - 1 ; else // decrement front 1 position front = front-1; array[front] = key ; // infoga aktuellt element i Deque } // infoga element i bakre änden av deque void Deque ::insertrear(int key) { if (isFull())) { cout <<<" Overflow!!\n " <<<endl; return; } // Om kön är tom till en början, sätt front=rear=0; början av deque if(front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear är på sista positionen i kön rear = 0; else // öka rear med 1 position rear = rear+1; array[rear] = key ; // infoga aktuellt element i Deque } // Ta bort elementet längst fram i Deque void Deque ::deletefront() { if (isEmpty())) { cout <<<"Queue Underflow!!\n" <<<endl; return ; } // Deque har bara ett element if(front == rear) { front = -1; rear = -1; } else // tillbaka till utgångspositionen if (front == size -1) front = 0; else // ta bort aktuellt frontvärde från Deque; öka front med 1 front = front+1; } // radera elementet i den bakre delen av Deque void Deque::deleterear() { if (isEmpty())) { cout <<" Underflow!!\n" <<<endl ; return ; } // Deque har bara ett element if (front == rear) { front = -1;rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // hämtar det främre elementet i Deque int Deque::getFront() { if (isEmpty()) { cout <<" Underflow!!\n" <<endl; return -1 ; } return array[front]; } // hämtar det bakre elementet i Deque int Deque::getRear() { if(isEmpty()//huvudprogram int main() { Deque dq(5); cout <<"Infoga element 1 i bakre änden \n"; dq.insertrear(1); cout <<"infoga element 3 i bakre änden \n"; dq.insertrear(3); cout <<"bakre element i deque " <<" " <<dq.getRear() <<endl; dq.deleterear(); cout <<"Efter deleterear, bakre = " <<dq.getRear() <<endl; cout <<"infoga element 5 vidfront end \n"; dq.insertfront(5); cout <<"front element of deque " <<" " <<" <<dq.getFront() <<endl; dq.deletefront(); cout <<"After deletefront, front = " <<dq.getFront() <<endl; return 0; }

Utgång:

Sätt in element 1 i den bakre änden.

sätta in element 3 i den bakre änden

bakre element i deque 3

Efter deleterear, bakre =

Insättning av element 5 i den främre delen.

första elementet i deque 5

Efter deletefront, front =

Java Deque-implementering

Deque-gränssnittet i Java, "java.util.Deque", härstammar från gränssnittet "java.util.Queue". Deque kan användas som en kö (First In, First Out) eller som en stapel (Last In, First Out). Dessa implementationer fungerar snabbare än den länkade listan.

Nedan visas hierarkin för Deque-gränssnittet i Java.

Vi måste komma ihåg några saker om Deque-gränssnittet i Java:

  • Genomförandet är inte trådsäkert eftersom det inte finns någon extern synkronisering.
  • Deque stöder inte samtidighet mellan flera trådar.
  • Deque's som implementeras med hjälp av matriser tillåter inte användning av NULL-element.
  • Arrayer kan växa i enlighet med kraven, och de två viktigaste funktionerna är obegränsad kapacitet och stöd för omställningsbara arrayer.

Följande är de olika metoder som stöds av Deque-gränssnittet:

Nej. Metod Beskrivning
1 add(element) Lägger till ett element till svansen.
2 addFirst(element) Lägger till ett element till huvudet/framsidan.
3 addLast(element) Lägger till ett element till svansen/baksidan.
4 erbjudande(element) Lägger till ett element i svansen; returnerar ett boolskt värde för att ange om insättningen lyckades.
5 offerFirst(element) Lägger till ett element till huvudet; returnerar ett boolskt värde för att ange om insättningen lyckades.
6 offerLast(element) Lägger till ett element i svansen; returnerar ett boolskt värde för att ange om insättningen lyckades.
7 iterator() Återger en iterator för deque.
8 descendingIterator() Återger en iterator som har den omvända ordningen för denna deque.
9 push(element) Lägger till ett element i huvudet av deque.
10 pop(element) Tar bort ett element från huvudet av deque och returnerar det.
11 removeFirst() Tar bort elementet i huvudet av deque.
12 removeLast() Tar bort elementet i slutet av deque.
13 omröstning() Hämtar och tar bort det första elementet i deque (representerat av huvudet i deque); returnerar NULL om deque är tom.
14 pollFirst() Hämtar och tar bort det första elementet i denna deque; returnerar null om denna deque är tom.
15 pollLast() Hämtar och tar bort det sista elementet i denna deque; returnerar null om denna deque är tom.
16 peek() Hämtar huvudet (det första elementet i köen) i den kö som representeras av denna kö; returnerar noll om denna kö är tom.

Observera: Denna åtgärd tar inte bort elementet.

17 peekFirst() Hämtar det första elementet i denna deque; returnerar null om denna deque är tom.

Observera: Denna åtgärd tar inte bort elementet.

18 peekLast() Hämtar det sista elementet i denna deque, eller returnerar null om den är tom.

Observera: Denna åtgärd tar inte bort elementet.

Följande Java-implementering visar de olika operationer som diskuterats ovan. 

 import java.util.*; class Main { public static void main(String[] args) { Deque  deque = ny LinkedList  (); // Vi kan lägga till element i kön på olika sätt deque.add(1); // lägga till i slutet deque.addFirst(3); deque.addLast(5); deque.push(7); // lägga till i början deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println("The deque : " + deque + "\n"); // Iterera genom köelementen. System.out.println("Standard Iterator"); Iterator iterator = deque.iterator(); while(iterator.hasNext()) System.out.print(" " + iterator.next())); // Iterator i omvänd ordning Iterator reverse = deque.descendingIterator(); System.out.println("\nReverse Iterator"); while (reverse.hasNext()) System.out.print(" " + reverse.next())); // Peek returnerar huvudet utan att radera // det från deque System.out.println("\n\nPeek " + deque.peek()); System.out.println("Efter peek: " + deque);// Pop returnerar huvudet och tar bort det från // deque System.out.println("\nPop " + deque.pop()); System.out.println("Efter pop: " + deque); // Vi kan kontrollera om ett visst element finns // i deque System.out.println("\nInnehåller element 3?: " + deque.contains(3)); // Vi kan ta bort det första/sista elementet. deque.removeFirst(); deque.removeLast(); System.out.println("Deque efter borttagning av "+ "första och sista element: " + deque); } }

Utgång:

Deque : [11, 7, 3, 1, 5, 9, 13]

Standard Iterator

11 7 3 1 5 9 13

Omvänd Iterator

13 9 5 1 3 7 1

Titta på 11

Efter tiken: [11, 7, 3, 1, 5, 9, 13]

Pop 11

Efter pop: [7, 3, 1, 5, 9, 13]

Innehåller element 3?: sant

Deque efter att ha tagit bort första och sista elementet: [3, 1, 5, 9]

I programmet ovan har vi använt Java-gränssnittet Deque och definierat en deque med heltalselement. Sedan har vi utfört olika operationer på denna deque och resultaten av dessa operationer visas.

Tillämpningar

Deque kan användas i några av följande tillämpningar.

#1) Schemaläggningsalgoritm: En schemaläggningsalgoritm, "A-steal scheduling algorithm", implementerar schemaläggning av uppgifter för olika processorer i ett multiprocessorsystem. I denna implementering används deque och processorn hämtar det första elementet från deque för utförande.

#2) Ångra listan över aktiviteter: I programvarutillämpningar har vi många åtgärder. En av dem är "ångra". När vi har utfört ångra åtgärder många gånger lagras alla dessa åtgärder i en lista. Listan upprätthålls som en deque så att vi lätt kan lägga till/ta bort poster från vilken ände som helst.

#3) Ta bort posterna efter en tid: Appar uppdaterar poster i sin lista, t.ex. appar som listar lagerposter etc. Dessa appar tar bort posterna efter en viss tid och lägger även in nya poster. Detta görs med hjälp av en deque.

Slutsats

Deque är en kö med dubbla ändar som gör det möjligt att lägga till eller ta bort element från båda ändarna, dvs. från köens främre och bakre del. Deque kan implementeras med hjälp av matriser eller länkade listor. Vi har dock också en klass i Standard Template Library (STL) som implementerar de olika operationerna i Deque.

I Java har vi ett Deque-gränssnitt som ärvs från queue-gränssnittet för att implementera Deque. Förutom de grundläggande standardoperationerna för Deque stöder detta gränssnitt olika andra operationer som kan utföras på Deque.

Deque används i allmänhet för tillämpningar som kräver att man lägger till eller tar bort element från båda ändarna. Den används också oftast vid schemaläggning av processorer i flerprocessorsystem.

Kolla in den kompletta C++-utbildningsserien

Scrolla till toppen