double ended queue c with examples
En djupgående handledning om Deque eller dubbelkö i C ++. Självstudien förklarar vad som är Deque, Basic Operations, C ++ & Java Implementation and Applications:
Dubbel slutad kö eller helt enkelt kallad “Deque” är en generaliserad version av kö.
Skillnaden mellan kö och Deque är att den inte följer FIFO-metoden (First In, First Out). Det andra inslaget i Deque är att vi kan sätta in och ta bort element från antingen främre eller bakre ändar.
=> Läs igenom Easy C ++ Training Series
Vad du kommer att lära dig:
- Dubbelavslutad köklassificering
- Grundläggande pekfunktioner
- och Illustration
- och Implementering
- Applikationer
- Slutsats
- Rekommenderad läsning
Dubbelavslutad köklassificering
Deque kan klassificeras enligt följande:
Inmatning med begränsad beröring; I ingångsbegränsat kan radering göras från båda ändarna men insättning kan endast göras i den bakre änden av kön.
Output-begränsad Deque: I den utgångsbegränsade kön kan insättning göras från båda ändarna, men borttagning görs endast i ena änden, dvs den främre änden av kön.
Vi kan också implementera stackar och köer med deque.
Grundläggande pekfunktioner
Följande är de grundläggande operationerna som kan utföras på deque.
- infoga front: Sätt in eller lägg till ett föremål längst fram på deken.
- insertLast: Sätt i eller lägg till ett föremål på baksidan av dekalen.
- deleteFront: Ta bort eller ta bort objektet från kön framför.
- ta bort sista: Ta bort eller ta bort objektet från baksidan av kön.
- getFront: Hämtar det främre föremålet i deken.
- getLast: Hämtar det sista objektet i kön.
- är tom: Kontrollerar om deken är tom.
- är full: Kontrollerar om deken är full.
och Illustration
En tom deque representeras enligt följande:
bra gratis brandvägg för Windows 10
Därefter sätter vi in element 1 på framsidan.
Nu sätter vi in element 3 på baksidan.
Därefter lägger vi till element 5 fram och när det ökas pekar fronten till 4.
Sedan sätter vi in element 7 på baksidan och 9 på framsidan. Dekken ser ut som visas nedan.
Låt oss sedan ta bort ett element framifrån.
metod som tar in en matris
Således ser vi att när elementen sätts in framifrån minskas det främre läget medan det ökas när ett element tas bort. För den bakre änden ökas läget för insättning och minskas för borttagning .
och Implementering
100 ++ touch Implementering
Vi kan implementera en deque i C ++ med hjälp av arrays samt en länkad lista. Bortsett från detta har Standard Template Library (STL) en klass 'deque' som implementerar alla funktioner för denna datastruktur.
Arrayimplementeringen av deken har ges nedan. Eftersom det är en dubbelkö har vi använt cirkulära matriser för implementering.
#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; } Produktion:
Sätt in element 1 på baksidan
sätt in element 3 i bakänden
bakre elementet i deque 3
Efter fördröjning, bakre = 1
insättningselement 5 vid framänden
främre elementet i deque 5
Efter borttagning, front = 1
Omräkning av Java-implementering
Deque-gränssnittet i Java, 'java.util.Deque' härrör från 'java.util.Queue' -gränssnittet. Deque kan användas som en kö (First In, First Out) eller en stack (Last In, First Out). Dessa implementeringar 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 punkter om Deque-gränssnittet i Java:
- Implementeringen är inte trådsäker eftersom det inte finns någon extern synkronisering.
- Deque stöder inte samtidighet med flera trådar.
- Deques implementerade med arrays tillåter inte användning av NULL-element.
- Arrayer får växa enligt kraven, med begränsningsfri kapacitet och stöd för storleksändring av array är de två viktigaste funktionerna.
Nedan följer de olika metoderna som stöds av Deque-gränssnittet:
c ++ insättningssorteringskod
| Låt bli. | Metod | Beskrivning |
|---|---|---|
| 7 | iterator () | Returnerar en iterator för deken. |
| 1 | lägg till (element) | Lägger till ett element i svansen. |
| två | addFirst (element) | Lägger till ett element i huvudet / fronten. |
| 3 | addLast (element) | Lägger till ett element i svansen / baksidan. |
| 4 | erbjudande (element) | Lägger till ett element i svansen; returnerar ett booleskt värde för att ange om insättningen lyckades. |
| 5 | offerFirst (element) | Lägger till ett element i huvudet; returnerar ett booleskt värde för att ange om insättningen lyckades. |
| 6 | offerLast (element) | Lägger till ett element i svansen; returnerar ett booleskt värde för att ange om insättningen lyckades. |
| 8 | fallandeIterator () | Returnerar en iterator som har omvänd ordning för denna deque. |
| 9 | tryck (element) | Lägger till ett element i deque-huvudet. |
| 10 | pop (element) | Tar bort ett element från huvudet på deken och returnerar det. |
| elva | removeFirst () | Tar bort elementet på toppen av deken. |
| 12 | ta bortLast () | Tar bort elementet på baksidan av deken. |
| 13 | opinionsundersökning() | Hämtar och tar bort det första elementet i deken (representerat av deque-huvudet); returnerar NULL om deketten är tom. |
| 14 | pollFirst () | Hämtar och tar bort det första elementet i denna deque; returnerar null om den här deken är tom. |
| femton | pollLast () | Hämtar och tar bort det sista elementet i denna deque; returnerar null om den här deken är tom. |
| 16 | titt() | Hämtar huvudet (första elementet i deken) i kön som representeras av denna deque; returnerar null om denna deque är tom. Obs! Den här åtgärden tar inte bort elementet. |
| 17 | peekFirst () | Hämtar det första elementet i denna deque; returnerar null om den här deken är tom. Obs! Den här åtgärden tar inte bort elementet. |
| 18 | peekLast () | Hämtar det sista elementet i denna deque, eller returnerar null om denna deque är tom. Obs! Den här åtgärden tar inte bort elementet. |
Följande Java-implementering visar de olika operationerna som diskuterats ovan.
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); } } Produktion:
Och (11, 7, 3, 1, 5, 9, 13)
Standardterator
11 7 3 1 5 9 13
Omvänd Iterator
13 9 5 1 3 7 11
Titta 11
Efter kik: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Efter pop: (7, 3, 1, 5, 9, 13)
Innehåller element 3 ?: sant
Deque efter borttagning av första och sista element: (3, 1, 5, 9)
I ovanstående program har vi använt Deque-gränssnittet för Java och vi definierade en deque av heltalselement. Sedan utförde vi olika operationer på denna deque och resultat resultatet av dessa operationer visas.
Applikationer
Deque kan användas i några av följande applikationer.
# 1) Schemaläggningsalgoritm: En schemaläggningsalgoritm, 'A-stjäla schemaläggningsalgoritm' implementerar uppgiftsschemaläggning för olika processorer i multiprocessorsystemet. Denna implementering använder deque och processorn får det första elementet från deque för körning.
# 2) Ångra listan över aktiviteter: I programvaran har vi många åtgärder. En är 'ångra'. När vi har utfört ångra åtgärder många gånger lagras alla dessa åtgärder i en lista. Denna lista upprätthålls som en dekal så att vi enkelt kan lägga till / ta bort poster från alla ändar.
# 3) Ta bort posterna efter en tid: Appar uppdaterar poster i sin lista som appar som listar lagerposter osv. Dessa appar tar bort posterna efter en tid och infogar också nya poster. Detta görs med hjälp av en deque.
Slutsats
Deque är en dubbelsidig kö som tillåter oss att lägga till / ta bort element från båda ändarna, dvs. främre och bakre delen av kön. Deque kan implementeras med arrays eller länkade listor. Vi har dock också en STL-klass (Standard Template Library) som implementerar de olika operationerna i Deque.
I Java har vi ett Deque-gränssnitt som ärvs från kögränssnittet för att implementera Deque. Bortsett från Deques grundläggande standardoperationer stöder detta gränssnitt olika andra operationer som kan utföras på Deque.
Deque används vanligtvis för applikationer som kräver tillsats / borttagning av element från båda ändarna. Det används också mestadels vid schemaläggning av processorer i flerprocessorsystem.
=> Kolla in hela C ++ träningsserien