Stak i C ++ STL med eksempel

Indholdsfortegnelse:

Anonim

Hvad er std :: stack?

En stak er en datastruktur, der fungerer baseret på LIFO (Last In First Out) teknik. Std :: stack giver kun mulighed for at tilføje og fjerne elementer fra den ene ende.

Std :: stack-klassen er en containeradapter. Containerobjekter indeholder data af en lignende datatype. Du kan oprette en stak fra forskellige sekvensbeholdere. Hvis der ikke leveres nogen container, bruges deque containe som standard. Containeradaptere understøtter ikke iteratorer, så det kan ikke bruges til at manipulere data.

I denne C ++ tutorial lærer du

  • Hvad er std :: stack?
  • Stak-syntaks
  • Medlemstyper
  • Funktioner i stak
  • Stakimplementering
  • skub () og pop ()
  • tom (), størrelse (), top ()
  • emplace () og swap ()
  • Stak i STL

Stak-syntaks

For at oprette en stak skal vi medtage headerfilen i vores kode. Vi bruger derefter denne syntaks til at definere std :: stack:

template  > class stack;
  • Type - er typen af ​​element indeholdt i std :: stack. Det kan være en hvilken som helst gyldig C ++ - type eller endda en brugerdefineret type.
  • Container - er typen af ​​underliggende containerobjekt.

Medlemstyper

Her er stakmedlemstyper:

  • value_type- Den første skabelonparameter, T. Det angiver elementtyperne.
  • container_type - Den anden skabelonparameter, Container. Det angiver den underliggende containertype.
  • size_type - usigneret integraltype.

Funktioner i stak

En C ++ stack understøtter følgende grundlæggende operationer:

  • push - Det tilføjer / skubber et element ind i stakken.
  • pop - Det fjerner / popper et element fra stakken.
  • peek - Returnerer det øverste element i stakken uden at fjerne det.
  • isFull - Kontrollerer, om en stak er fuld.
  • isEmpty - Kontrollerer, om en stak er tom.

Stakimplementering

Trin 1) Vi har oprindeligt en tom stak. Toppen af ​​en tom stak er indstillet til -1.

Trin 2) Dernæst har vi skubbet elementet 5 ind i stakken. Den øverste del af stakken peger på elementet 5.

Trin 3) Dernæst har vi skubbet elementet 50 ind i stakken. Den øverste del af stakken skifter og peger på elementet 50.

Trin 4) Vi har derefter udført en popoperation, der fjerner det øverste element fra stakken. Elementet 50 springes fra stakken. Den øverste del af stakken peger nu på elementet 5.

skub () og pop ()

Funktionerne stak :: push () tilføjer nyt element til toppen af ​​stakken. Stakkens størrelse øges med 1 efter indsættelsen. Funktionen tager denne syntaks:

stack.push(value)

Værdien er det element, der skal indsættes i stakken.

Stakken :: pop () -funktionen fjerner det øverste element i stakken. Dette er det nyeste element i stakken. Stakkens størrelse reduceres med 1 efter fjernelsen. Her er funktionssyntaxen:

stack.pop()

Funktionen tager ingen parametre.

Eksempel 1:

#include #include using namespace std;int main() {stack st;st.push(10);st.push(20);st.push(30);st.push(40);st.pop();st.pop();while (!st.empty()) {cout << ' ' << st.top();st.pop();}}

Produktion:

Her er et screenshot af koden:

Kode Forklaring:

  1. Inkluder iostream header-filen i vores kode for at bruge dens funktioner.
  2. Inkluder stack header-filen i vores kode for at bruge dens funktioner.
  3. Inkluder std navneområdet i vores kode for at bruge dets klasser uden at kalde det.
  4. Ring til hovedfunktionen (). Programmets logik skal tilføjes inden for denne funktion.
  5. Opret en stak st for at gemme heltal værdier.
  6. Brug push () -funktionen til at indsætte værdien 10 i stakken.
  7. Brug funktionen push () til at indsætte værdien 20 i stakken.
  8. Brug push () -funktionen til at indsætte værdien 30 i stakken.
  9. Brug funktionen push () til at indsætte værdien 40 i stakken.
  10. Brug pop () -funktionen til at fjerne det øverste element fra stakken, det vil sige 40. Det øverste element bliver nu 30.
  11. Brug pop () -funktionen til at fjerne det øverste element fra stakken, det vil sige 30. Det øverste element bliver nu 20.
  12. Brug en while-loop og tom () funktion til at kontrollere, om stakken IKKE er tom. Det ! er IKKE operatør.
  13. Udskrivning af det aktuelle indhold af stakken på konsollen.
  14. Ring til pop () -funktionen på stakken.
  15. Slutningen af ​​mens sløjfen er i kroppen.
  16. Slutningen af ​​hovedfunktionsorganet ().

tom (), størrelse (), top ()

Stakke har indbyggede funktioner, som du kan bruge til at lege med stakken og dens værdier. Disse inkluderer:

  • tom () - kontrollerer, om en stak er tom eller ej.
  • størrelse () - returnerer størrelsen på stakken, dvs. antallet af elementer i en stak.
  • top () - åbner stakelementet øverst.

Eksempel 2:

#include #include using namespace std;void createStack(stack  mystack){stack  ms = mystack;while (!ms.empty()){cout << '\t' << ms.top();ms.pop();}cout << '\n';}int main(){stack  st;st.push(32);st.push(21);st.push(39);st.push(89);st.push(25);cout << "The stack st is: ";createStack(st);cout << "\n st.size() : " << st.size();cout << "\n st.top() : " << st.top();cout << "\n st.pop() : ";st.pop();createStack(st);return 0;}

Produktion:

Her er et screenshot af koden:

Kode Forklaring:

  1. Inkluder iostream header-filen i vores kode for at kunne bruge dens funktioner.
  2. Inkluder stack header-filen i vores kode for at kunne bruge dens funktioner.
  3. Inkluder std navneområdet i vores program for at kunne bruge dets klasser uden at kalde det.
  4. Opret funktionen createStack, som vi kan bruge til at oprette stack mystack. Stakken indeholder et sæt heltal.
  5. Begyndelsen på kroppen af ​​createStack-funktionen.
  6. Opret en forekomst af mystack-datatypen, og giv den navnet ms.
  7. Brug while-løkken og den tomme () funktion til at kontrollere, om stakken er tom.
  8. Starten af ​​kroppen af ​​mens loop.
  9. Brug den øverste () funktion gemt øverst i stakken. Tegnet \ t opretter en ny fane.
  10. Brug pop () -funktionen til at slette elementet øverst i stakken.
  11. Slutningen af ​​mens sløjfen er i kroppen.
  12. Udskriv en tom linje på konsollen.
  13. Slutningen af ​​kroppen til createStack-funktionen.
  14. Ring til hovedfunktionen (). Programmets logik skal tilføjes inden for hovedfunktionens () -funktion.
  15. Starten af ​​hoveddelen af ​​funktionen main ().
  16. Opret en stakobjekt st.
  17. Brug push () -funktionen til at indsætte elementet 32 ​​i stakken.
  18. Brug push () -funktionen til at indsætte elementet 21 i stakken.
  19. Brug push () -funktionen til at indsætte elementet 39 i stakken.
  20. Brug funktionen push () til at indsætte elementet 89 i stakken.
  21. Brug push () -funktionen til at indsætte elementet 25 i stakken.
  22. Udskriv tekst på konsollen.
  23. Ring til createStack-funktionen for at udføre ovenstående indsætningsoperationer i stakken.
  24. Udskriv størrelsen på stakken på konsollen sammen med anden tekst.
  25. Udskriv elementet øverst på stakken på konsollen.
  26. Udskriv tekst på konsollen.
  27. Slet elementet øverst i stakken. Derefter returnerer de resterende elementer i stakken.
  28. Ring til createStack-funktionen for at udføre ovenstående operationer.
  29. Programmet skal returnere værdi efter vellykket afslutning.
  30. Slutningen af ​​hoveddelen af ​​funktionen ().

emplace () og swap ()

Dette er andre indbyggede stakfunktioner:

  • emplace () - konstruktioner indsætter derefter nyt element øverst på stakken.
  • swap () - udveksler stackindhold med en anden stacks indhold.

Eksempel 3:

#include #include #include using namespace std;int main() {stack st1;stack st2;st1.emplace(12);st1.emplace(19);st2.emplace(20);st2.emplace(23);st1.swap(st2);cout << "st1 = ";while (!st1.empty()) {cout << st1.top() << " ";st1.pop();}cout << endl << "st2 = ";while (!st2.empty()) {cout << st2.top() << " ";st2.pop();}}

Produktion:

Her er et screenshot af koden:

Kode Forklaring:

  1. Inkluder iostream header-filen i vores kode for at bruge dens funktioner.
  2. Inkluder stack header-filen i vores kode for at bruge dens funktioner.
  3. Inkluder cstdlib headerfilen i vores kode for at bruge dens funktioner.
  4. Inkluder std navneområdet i vores kode for at bruge dets klasser uden at kalde det.
  5. Ring til hovedfunktionen (). Programlogikken tilføjes i selve denne funktion.
  6. Erklær en stak med navnet st1 til at gemme heltalværdier.
  7. Erklær en stak med navnet st2 til at gemme heltalværdier.
  8. Brug emplace () -funktionen til at indsætte heltal 12 i stakken med navnet st1.
  9. Brug funktionen emplace () til at indsætte heltal 19 i stakken med navnet st1.
  10. Brug funktionen emplace () til at indsætte heltal 20 i stakken med navnet st2.
  11. Brug funktionen emplace () til at indsætte heltal 23 i stakken med navnet st2.
  12. Brug swap () -funktionen til at bytte indholdet af de to stakke, st1 og st2. Indholdet af stakken st1 skal flyttes til stakken st2. Indholdet af stakken st2 skal flyttes til stakken st1.
  13. Udskriv tekst på konsollen.
  14. Brug while-sætningen og den tomme () funktion til at kontrollere, om stakken st1 ikke er tom.
  15. Udskriv indholdet af stakken st1 på konsollen. "" Tilføjer plads mellem stakelementerne, når de udskrives på konsollen.
  16. Udfør pop () -funktionen på stakken st1 for at fjerne det øverste element.
  17. Slutningen af ​​kroppens udsagn.
  18. Udskriv tekst på konsollen. Endl er et C ++ nøgleord til slutlinjen. Den flytter musemarkøren til den næste linje for at begynde at udskrive derfra.
  19. Brug while-sætningen og den tomme () funktion til at kontrollere, om stakken st2 ikke er tom.
  20. Udskriv indholdet af stakken st2 på konsollen. "" Tilføjer plads mellem stakelementerne, når de udskrives på konsollen.
  21. Udfør pop () -funktionen på stakken st2 for at fjerne det øverste element.
  22. Slutningen af ​​kroppens udsagn.
  23. Slutningen af ​​hovedfunktionens () krop.

Stak i STL

STL (Standard Template Library) leveres med skabelonklasser, der giver fælles C ++ datastrukturer. Derfor kan en stak også implementeres i STL. Vi inkluderer blot dette bibliotek i vores kode og bruger det til at definere en stak.

stack st;

Ovenstående syntaks erklærer en stak st til elementer af datatype T.

Eksempel 3:

#include #include #include using namespace std;int main() {stack st;st.push(12);st.push(19);st.push(20);cout << st.top();cout << st.size();}

Produktion:

Her er et screenshot af koden:

Kode Forklaring:

  1. Inkluder iostream header-filen i vores kode for at bruge dens funktioner.
  2. Inkluder stack header-filen i vores kode for at bruge dens funktioner.
  3. Inkluder cstdlib headerfilen i vores kode for at bruge dens funktioner.
  4. Inkluder std navneområdet i vores kode for at bruge dets klasser uden at kalde det.
  5. Ring til hovedfunktionen (). Programmets logik skal tilføjes inden for denne funktion.
  6. Erklær en stak st til at gemme heltalsdata.
  7. Føj elementet 12 til stakken.
  8. Føj elementet 19 til stakken.
  9. Føj elementet 20 til stakken.
  10. Udskriv elementet øverst på stakken på konsollen.
  11. Udskriv størrelsen på stakken på konsollen.
  12. Slutningen af ​​hoveddelen af ​​funktionen main ().

Resumé:

  • En stak er en datastruktur, der fungerer baseret på LIFO-teknikken (Last In first Out).
  • Std :: stack tillader kun, at elementer tilføjes og fjernes fra den ene ende.
  • Std :: stack-klassen er en containeradapter, der indeholder emner af samme datatype.
  • En stak kan oprettes fra forskellige sekvensbeholdere.
  • Hvis du ikke leverer en container, bruges deque-containeren som standard.
  • Push () -funktionen er til indsættelse af genstande i stakken.
  • Pop () -funktionen er til at fjerne det øverste element fra trinnet.
  • Den tomme () funktion er til at kontrollere, om en stak er tom eller ej.