Stackar är en typ av containeradaptrar med LIFO (Last In First Out) typ av arbete, där ett nytt element läggs till i ena änden (överst) och ett element tas bort endast från den änden. Stack använder ett inkapslat objekt av endera vektor eller deque (som standard) eller lista (sekventiell containerklass) som dess underliggande container, vilket ger en specifik uppsättning medlemsfunktioner för att komma åt dess element.
lista sortera java
Om det finns förvirring i att komma ihåg den grundläggande skillnaden mellan stack och kö, ta bara ett verkligt exempel för denna differentiering, för stapling, stapling av böcker kan vi enkelt ta den översta boken och för kö kom ihåg när du måste stå i kö framför av bankomat för att ta ut pengarna, då har den första personen nära bankomaten första chansen att ta ut pengarna från bankomat. Så, kö är typen FIFO (First In First Out) som fungerar.
Stacksyntax:-
För att skapa en stack måste vi inkludera rubrikfilen i vår kod. Vi använder sedan denna syntax för att definiera std::stack:
| mall |
Typ – är den typ av element som finns i std::stacken. Det kan vara vilken giltig C++-typ som helst eller till och med en användardefinierad typ.
Behållare – är Typ av underliggande containerobjekt.
Medlemstyper:-
value_type- Den första mallparametern, T. Den anger elementtyperna.
container_type- Den andra mallparametern, Container. Det anger den underliggande behållartypen.
size_type- Osignerad integraltyp.
Funktionerna associerade med stack är:
empty() – Returnerar om stacken är tom – Tidskomplexitet: O(1)
size() – Returnerar storleken på stacken – Tidskomplexitet : O(1)
top() – Returnerar en referens till det översta elementet i stacken – Tidskomplexitet : O(1)
push(g) – Lägger till elementet 'g' överst i stacken – Tidskomplexitet: O(1)
pop() – Tar bort det senast inmatade elementet i stacken – Tidskomplexitet: O(1)
C++
#include> #include> using> namespace> std;> int> main() {> >stack<>int>>stack;> >stack.push(21);>// The values pushed in the stack should be of the same data which is written during declaration of stack> >stack.push(22);> >stack.push(24);> >stack.push(25);> >int> num=0;> >stack.push(num);> >stack.pop();> >stack.pop();> >stack.pop();> > >while> (!stack.empty()) {> >cout << stack.top() <<>' '>;> >stack.pop();> >}> }> |
>
>Produktion
25 c till k
22 21>
Tidskomplexitet: Tidskomplexiteten för detta program är O(N), där N är det totala antalet element i stacken. While-slingan itererar N gånger, plockar element från stapeln och skriver ut dem.
Utrymmes komplexitet: Utrymmeskomplexiteten för detta program är O(N), där N är det totala antalet element i stacken. Stackdatastrukturen använder utrymme proportionellt mot antalet element som lagras i den. I det här fallet är den maximala storleken på stacken 5, så rymdkomplexiteten är konstant och kan också betraktas som O(1).
Kodförklaring:
- Inkludera iostream-huvudfilen eller i vår kod för att använda dess funktioner.
- Inkludera stackheader-filen i vår kod för att använda dess funktioner om den redan är inkluderad, då behövs ingen stack-header-fil eftersom den redan har inbyggd funktion i den.
- Inkludera std-namnområdet i vår kod för att använda dess klasser utan att anropa det.
- Anropa main()-funktionen. Programlogiken bör läggas till i denna funktion.
- Skapa en stack för att lagra heltalsvärden.
- Använd push()-funktionen för att infoga värdet 21 i stacken.
- Använd push()-funktionen för att infoga värdet 22 i stacken.
- Använd push()-funktionen för att infoga värdet 24 i stacken.
- Använd push()-funktionen för att infoga värdet 25 i stacken.
- Använd en heltalsvariabel num för att ange ett variabelvärde. Här är dess värde 0, men vi kan tilldela vilket heltalsvärde som helst med cin>> num.
- Använd push()-funktionen för att infoga värdet på num-variabeln.
- Använd pop()-funktionen för att ta bort det översta elementet från stacken, det vill säga 25. Det översta elementet blir nu 24.
- Använd pop()-funktionen för att ta bort det översta elementet från stacken, det vill säga 24. Det översta elementet blir nu 22.
- Använd en while loop och empty() funktion för att kontrollera om stacken INTE är tom. Den ! är NOT-operatören. Så när stacken inte är tom kommer funktionen empty() att returnera false och NOT-operatorn konverterar den till true och while-loopen fortsätter att köras. Men när stacken blir tom kommer funktionen empty() att returnera true och NOT-operatorn kommer att göra den falsk och slingan tar slut.
- Skriver ut det aktuella innehållet i stapeln på konsolen.
- Anropa pop()-funktionen i stacken.
- Slutet på while-loopens kropp.
- Slutet på huvuddelen () funktion.
Lista över funktioner i Stack:
- stack::top() i C++ STL
- stack::empty() och stack::size() i C++ STL
- stack::push() och stack::pop() i C++ STL
- stack::swap() i C++ STL
- stack::emplace() i C++ STL
- Nya artiklar om C++ Stack