double ended queue c with examples
Een diepgaande zelfstudie over Deque of een dubbele wachtrij in C ++. Tutorial legt uit wat Deque, basisbewerkingen, C ++ en Java-implementatie en toepassingen zijn:
Dubbelzijdige wachtrij of simpelweg 'Deque' genoemd is een gegeneraliseerde versie van Wachtrij.
Het verschil tussen Queue en Deque is dat het niet de FIFO-benadering (First In, First Out) volgt. Het tweede kenmerk van Deque is dat we elementen aan de voor- of achterkant kunnen invoegen en verwijderen.
Lees de Easy C ++ Training Series door
Wat je leert:
- Classificatie van dubbele wachtrijen
- Basisaanraakbewerkingen
- en illustratie
- en implementatie
- Toepassingen
- Gevolgtrekking
- Aanbevolen literatuur
Classificatie van dubbele wachtrijen
Deque kan als volgt worden ingedeeld:
Invoer met beperkte aanraking; Bij invoerbeperkt kan worden verwijderd vanaf beide uiteinden, maar kan alleen worden ingevoegd aan de achterkant van de wachtrij.
Output-beperkte Deque: In de wachtrij met beperkte uitvoer kan worden ingevoegd vanaf beide uiteinden, maar het verwijderen gebeurt slechts aan één uiteinde, d.w.z. aan de voorkant van de wachtrij.
We kunnen ook stapels en wachtrijen implementeren met behulp van deque.
Basisaanraakbewerkingen
Hieronder volgen de basisbewerkingen die op deque kunnen worden uitgevoerd.
- insert voorkant: Plaats of voeg een item toe aan de voorkant van de deque.
- laatste invoegen: Plaats of voeg een item toe aan de achterkant van de kaart.
- deleteFront: Verwijder of verwijder het item vooraan in de wachtrij.
- laatste verwijderen: Verwijder of verwijder het item van de achterkant van de wachtrij.
- getFront: Haalt het voorste item in de deque op.
- word laatste: Haalt het laatste item in de wachtrij op.
- is leeg: Controleert of de kaart leeg is.
- is vol: Controleert of de kaart vol is.
en illustratie
Een leeg kaartspel wordt als volgt weergegeven:
wat is een .7z-bestand
Vervolgens plaatsen we element 1 aan de voorkant.
Nu plaatsen we element 3 aan de achterkant.
Vervolgens voegen we element 5 toe aan de voorkant en bij verhoging de voorste punten naar 4.
Vervolgens plaatsen we de elementen 7 aan de achterkant en 9 aan de voorkant. De deque ziet eruit zoals hieronder weergegeven.
Laten we vervolgens een element van de voorkant verwijderen.
We zien dus dat wanneer de elementen aan de voorkant worden geplaatst, de positie aan de voorkant wordt verlaagd, terwijl deze wordt verhoogd wanneer een element wordt verwijderd. Voor het achterste uiteinde wordt de positie verhoogd voor inbrengen en verlaagd voor verwijdering
en implementatie
100 ++ touch-implementatie
We kunnen een deque in C ++ implementeren met behulp van arrays en een gekoppelde lijst. Afgezien hiervan heeft de Standard Template Library (STL) een klasse “deque” die alle functies voor deze datastructuur implementeert.
De array-implementatie van de deque wordt hieronder gegeven. Omdat het een dubbele wachtrij is, hebben we circulaire arrays gebruikt voor implementatie.
Uitgang:
Element 1 aan de achterkant plaatsen
inzetstuk 3 aan achterzijde
achterelement van deque 3
Vragen en antwoorden over het testen van Java-automatiseringstesten
Na het wissen, achter = 1
element 5 aan de voorkant inbrengen
frontelement van deque 5
Na deletefront, front = 1
Herstel van de Java-implementatie
De deque-interface in Java, 'java.util.Deque', is afgeleid van de 'java.util.Queue' -interface. Deque kan worden gebruikt als wachtrij (First In, First Out) of stapel (Last In, First Out). Deze implementaties werken sneller dan de gekoppelde lijst.
Hieronder wordt de hiërarchie weergegeven voor de Deque-interface in Java.
We moeten een paar punten onthouden over de Deque-interface in Java:
- De implementatie is niet thread-safe omdat er geen externe synchronisatie is.
- Deque ondersteunt geen gelijktijdigheid door meerdere threads.
- Deque's geïmplementeerd met arrays staan het gebruik van NULL-elementen niet toe.
- Arrays mogen groeien volgens de vereisten, waarbij beperkingsvrije capaciteit en aanpasbare arrayondersteuning de twee belangrijkste kenmerken zijn.
Hieronder volgen de verschillende methoden die worden ondersteund door de Deque-interface:
gratis videoconverters voor Windows 10
| Niet doen. | Methode | Omschrijving |
|---|---|---|
| 7 | iterator () | Retourneert een iterator voor de deque. |
| 1 | add (element) | Voegt een element toe aan de staart. |
| twee | addFirst (element) | Voegt een element toe aan het hoofd / front. |
| 3 | addLast (element) | Voegt een element toe aan de achterkant / achterkant. |
| 4 | aanbieding (element) | Voegt een element toe aan de staart; geeft een booleaanse waarde terug om aan te geven of het invoegen is gelukt. |
| 5 | offerFirst (element) | Voegt een element toe aan het hoofd; geeft een booleaanse waarde terug om aan te geven of het invoegen is gelukt. |
| 6 | offerLast (element) | Voegt een element toe aan de staart; geeft een booleaanse waarde terug om aan te geven of het invoegen is gelukt. |
| 8 | aflopendIterator () | Retourneert een iterator die de omgekeerde volgorde heeft voor deze deque. |
| 9 | push (element) | Voegt een element toe aan de kop van de deque. |
| 10 | pop (element) | Verwijdert een element uit de kop van de deque en geeft het terug. |
| elf | removeFirst () | Verwijdert het element aan de kop van de deque. |
| 12 | removeLast () | Verwijdert het element aan de achterkant van de deque. |
| 13 | poll () | Haalt en verwijdert het eerste element van de kaart (vertegenwoordigd door de kop van de kaart); geeft NULL terug als de kaart leeg is. |
| 14 | pollFirst () | Haalt en verwijdert het eerste element van deze deque; geeft null terug als deze kaart leeg is. |
| vijftien | pollLast () | Haalt en verwijdert het laatste element van deze deque; geeft null terug als deze kaart leeg is. |
| 16 | kijkje() | Haalt het hoofd (eerste element van de kaart) op van de wachtrij die door deze kaart wordt vertegenwoordigd; geeft null terug als deze kaart leeg is. Opmerking: deze handeling verwijdert het element niet. |
| 17 | peekFirst () | Haalt het eerste element van deze deque op; geeft null terug als deze kaart leeg is. Opmerking: deze handeling verwijdert het element niet. |
| 18 | peekLast () | Haalt het laatste element van deze deque op, of retourneert null als deze deque leeg is. Opmerking: deze handeling verwijdert het element niet. |
De volgende Java-implementatie demonstreert de verschillende bewerkingen die hierboven zijn besproken.
Uitgang:
En de (11, 7, 3, 1, 5, 9, 13)
Standaard Iterator
11 7 3 1 5 9 13
Omgekeerde Iterator
13 9 5 1 3 7 11
Gluren 11
Na een kijkje: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Na pop: (7, 3, 1, 5, 9, 13)
Bevat element 3 ?: waar
Deque na het verwijderen van het eerste en laatste element: (3, 1, 5, 9)
In het bovenstaande programma hebben we de Deque-interface van Java gebruikt en hebben we een deque van integer-elementen gedefinieerd. Vervolgens hebben we verschillende bewerkingen op dit deque uitgevoerd en de resultaten van deze bewerkingen weergegeven.
Toepassingen
Deque kan worden gebruikt in enkele van de volgende toepassingen.
# 1) Planningsalgoritme: Een planningsalgoritme, 'A-steal scheduling algoritme', implementeert taakplanning voor verschillende processors in het multiprocessorsysteem. Deze implementatie gebruikt deque en de processor haalt het eerste element uit de deque voor uitvoering.
# 2) Lijst met activiteiten ongedaan maken: In softwareapplicaties hebben we veel acties. Een daarvan is 'ongedaan maken'. Als we vaak een actie ongedaan maken hebben uitgevoerd, worden al deze acties in een lijst opgeslagen. Deze lijst wordt bijgehouden als een deque, zodat we gemakkelijk items van elk uiteinde kunnen toevoegen / verwijderen.
# 3) Verwijder de vermeldingen na enige tijd: Apps vernieuwen vermeldingen in hun lijst zoals apps die de voorraadvermeldingen vermelden, enz. Deze apps verwijderen de vermeldingen na enige tijd en voegen ook nieuwe vermeldingen in. Dit wordt gedaan met behulp van een deque.
Gevolgtrekking
Deque is een wachtrij met twee uiteinden waarmee we elementen aan beide uiteinden, d.w.z. aan de voor- en achterkant, van de wachtrij kunnen toevoegen / verwijderen. Deque kan worden geïmplementeerd met behulp van arrays of gekoppelde lijsten. We hebben echter ook een klasse Standard Template Library (STL) die de verschillende bewerkingen van Deque implementeert.
In Java hebben we een Deque-interface die is overgenomen van de wachtrij-interface om Deque te implementeren. Afgezien van de standaard standaardbewerkingen van Deque, ondersteunt deze interface verschillende andere bewerkingen die op Deque kunnen worden uitgevoerd.
Deque wordt over het algemeen gebruikt voor toepassingen waarbij elementen aan beide uiteinden moeten worden toegevoegd / verwijderd. Het wordt ook meestal gebruikt bij de planning van processors in multiprocessorsystemen.
Bekijk de complete C ++ trainingsserie
Aanbevolen literatuur
- Prioriteitswachtrij in STL
- Wat is vergelijkende testen (leren met voorbeelden)
- Python DateTime-zelfstudie met voorbeelden
- Shell-sortering in C ++ met voorbeelden
- Snijd Commando in Unix met voorbeelden
- Unix Cat Command Syntax, opties met voorbeelden
- Gebruik van Cursor in MongoDB met voorbeelden
- Ls Command in Unix met voorbeelden