stacks queues stl
Leer de implementatie van stapels en wachtrijen in STL met voorbeelden.
Stapels en wachtrijen zijn twee containers in STL die erg basic van aard zijn. Het zijn de eenvoudigste containers met brede toepassingen in softwareprogrammering.
In deze tutorial zullen we een gedetailleerde implementatie van beide containers in STL zien. We zullen ook de verschillende bewerkingen doorlopen die worden ondersteund door stapel en wachtrij met voorbeelden.
Bekijk hier de eenvoudige C ++ trainingsserie.
Wat je leert:
Stapels
Stapelcontainer in STL is een soort containeradapters. Het wordt gebruikt om een stackgegevensstructuur in C ++ te repliceren. Stapelcontainer is een set elementen waarin de elementen aan het ene uiteinde worden ingevoegd en ook aan hetzelfde uiteinde worden verwijderd.
Dit gemeenschappelijke punt van toevoegen en verwijderen staat bekend als 'Top of the stack'.
De picturale weergave van stapel wordt hieronder getoond.
Zoals te zien is in de bovenstaande weergave, is de stapel een container waarin elementen worden toegevoegd en verwijderd van hetzelfde einde genaamd Top of the stack.
Omdat toevoegen en verwijderen aan hetzelfde einde plaatsvinden, kunnen we zeggen dat de stapelcontainer LIFO-werk is (last in, first out). Dit betekent dat het element dat als eerste wordt toegevoegd, het laatste is dat wordt verwijderd.
Om de stapelcontainer te implementeren, moeten we de header in ons programma opnemen.
De algemene declaratiesyntaxis voor stackcontainer is:
Stapelbewerkingen
Laten we vervolgens de verschillende bewerkingen bespreken die containers in STL-steunen stapelen.
- Duwen : push-operatie wordt gebruikt om een element in de stapel te plaatsen. Deze bewerking voegt altijd elementen toe aan de bovenkant van de stapel.
Beschouw een lege stapel mystack van het type integer
Laten we vervolgens element 1 aan de stapel toevoegen.
Vervolgens voegen we element 3 toe aan de stapel.
Volgens de voorstelling wordt als resultaat van een push-operatie een element toegevoegd aan de bovenkant van de stapel. Na elke push-operatie wordt de stapel met 1 vergroot.
- knal : pop-bewerking wordt gebruikt om een element van de stapel te verwijderen. Het verwijderde element is het element waarnaar wordt verwezen door de bovenkant van de stapel. Als gevolg van de pop-operatie wordt de stapelgrootte met 1 verkleind.
Laten we eens kijken hoe de pop-operatie eruit ziet:
Beschouw de stack mystack zoals hierboven waarin we al 2 elementen hebben geduwd.
Laten we nu de functie pop () noemen. Wanneer deze aanroep wordt uitgevoerd, wordt het element bovenaan de stapel verwijderd en wijst de ‘Top’ naar het volgende element, zoals hieronder weergegeven.
Als we weer pop () aanroepen, dan wordt het volgende element (in dit geval 1) verwijderd, wat resulteert in een lege stapel.
informatica interviewvragen en antwoorden voor 5 jaar ervaring
- top : Retourneert het bovenste element van de stapel.
- leeg : Controleert of de stapel leeg is of niet.
- grootte: Geeft de grootte van de stapel terug, d.w.z. het aantal elementen in de stapel.
Hieronder wordt een voorbeeld gegeven van Stack-implementatie om de bewerkingen beter te begrijpen.
Het bovenstaande voorbeeld toont duidelijk de push-operatie die een stapel genereert. Het toont ook de stapel na twee opeenvolgende pop-operaties.
We hebben dus stack en zijn bewerkingen in STL gezien. Verder zullen we in deze tutorial de gedetailleerde implementatie zien van nog een andere eenvoudige STL-container die 'Queue' is.
Wachtrij
De wachtrij is nog een andere container in STL die ook heel eenvoudig en handig is. Wachtrijcontainer is een replica van de wachtrijgegevensstructuur in C ++. In tegenstelling tot stack zijn er in de wachtrijcontainer twee uiteinden, namelijk de voorkant en de achterkant.
Elementen worden aan de achterkant toegevoegd aan de wachtrij terwijl ze vooraan in de wachtrij worden verwijderd. Over het algemeen gebruikt de wachtrij een FIFO-indeling (First in, First Out).
Om een wachtrijcontainer in een programma te implementeren, moeten we een header in de code opnemen.
De algemene syntaxis voor het declareren van de wachtrij is:
wachtrij wachtrijnaam;
We declareren de wachtrijcontainer als volgt:
Wachtrijbewerkingen
Nu zullen we de verschillende bewerkingen zien die door de wachtrij worden ondersteund.
- Duwen: De functie ‘push’ voegt het element toe aan het einde van de wachtrij, d.w.z. aan de achterkant van de wachtrij.
- knal: De functie ‘pop’ verwijdert het eerste element van de wachtrij, d.w.z. het element vooraan in de wachtrij.
Laten we de push- en pop-functies van de wachtrij begrijpen.
Overweeg een lege wachtrij die boven myqueue is aangegeven. Nu pushen we een even nummer 2 in de wachtrij met de operatie
myqueue.push (2);
Nu ziet de wachtrij eruit als:
Vervolgens voegen we ‘4’ toe aan de wachtrij met de oproep ‘myqueue.push (4)’.
Nu ziet de wachtrij eruit zoals hieronder weergegeven:
Zoals hierboven te zien is, worden de elementen vanaf de achterkant of achterkant in de wachtrij geduwd.
Laten we nu de operatie op myqueue zetten.
myqueue.pop ();
Dus zoals we zien, wordt het element vooraan in de wachtrij verwijderd wanneer pop () wordt aangeroepen. Dit betekent dat het eerste element dat in de wachtrij komt, het eerste element is dat uit de wachtrij komt.
- voorkant: Deze functie retourneert een verwijzing naar het eerste element van de wachtrij.
- terug: Back retourneert een verwijzing naar het laatste element in de wachtrij.
- leeg: Controleert of de wachtrij leeg is.
- grootte: Geeft als resultaat de grootte van de wachtrij, d.w.z. het aantal elementen in de wachtrij.
Hieronder ziet u een voorbeeldprogramma dat de bewerkingen laat zien die worden gebruikt door de wachtrijcontainer.
Uitgang:
hoe je een diepe kopie maakt van een array java
De wachtrij myqueue is: 2 4 6 8
myqueue.size (): 4
myqueue.front (): 2
myqueue.back (): 8
myqueue.pop (): 4 6 8
Zoals hierboven weergegeven, declareren we eerst een wachtrijcontainer. Vervolgens voegen we met behulp van de push-operatie de eerste vier even getallen toe. Daarna halen we het element uit de wachtrij en tonen we de gewijzigde wachtrij.
Gevolgtrekking
Hiermee zijn we aan het einde gekomen van deze tutorial over stapels en wachtrijen. Zoals eerder vermeld zijn dit de eenvoudigste containers die we in STL hebben. Een andere variant van de wachtrijcontainer staat bekend als 'Priority Queue'.
In onze aanstaande tutorial zullen we meer bespreken over Priority Queue in STL !!
Bezoek hier om C ++ vanaf het begin te leren.