Stacks yra konteinerio adapterių tipas, veikiantis LIFO (Last In First Out), kai viename gale (viršuje) pridedamas naujas elementas, o elementas pašalinamas tik iš to galo. Stack naudoja bet kurio objekto kapsuliuotą objektą vektorius arba deque (pagal nutylėjimą) arba sąrašą (nuosekliojo konteinerio klasė) kaip pagrindinį konteinerį, suteikiantį konkretų narių funkcijų rinkinį, kad būtų galima pasiekti jo elementus.
Šarvanandas
Jei kyla painiavos prisimenant pagrindinį skirtumą tarp krūvos ir eilės, tiesiog turėkite realų šio skirtumo pavyzdį. Jei norite sukrauti, sukrauti knygas, galime lengvai paimti aukščiausią knygą, o eilės atveju prisiminkite, kada turite stovėti eilėje priekyje. bankomato grynųjų pinigų paėmimui, tada pirmas šalia bankomato esantis asmuo turi pirmą galimybę pasiimti pinigus iš bankomato. Taigi, eilė yra FIFO (pirmas į pirmą išeinantis) tipas.
Stack sintaksė: -
Norėdami sukurti krūvą, į savo kodą turime įtraukti antraštės failą. Tada mes naudojame šią sintaksę norėdami apibrėžti std::stack:
| šabloną |
Tipas – yra elemento tipas, esantis std::stack. Tai gali būti bet koks tinkamas C++ tipas arba net vartotojo nustatytas tipas.
Konteineris – yra pagrindinio konteinerio objekto tipas.
Narių tipai: -
value_type- pirmasis šablono parametras T. Jis žymi elementų tipus.
konteinerio tipas – antrasis šablono parametras, konteineris. Tai žymi pagrindinio konteinerio tipą.
size_type- Unsigned integral type.
Su kaminu susijusios funkcijos yra šios:
tuščias() – grąžina, ar krūva tuščia – Laiko sudėtingumas: O(1)
dydis() – grąžina krūvos dydį – Laiko sudėtingumas: O(1)
top() – grąžina nuorodą į aukščiausią krūvos elementą – Laiko sudėtingumas: O(1)
push(g) – krūvos viršuje prideda elementą „g“ – Laiko sudėtingumas: O(1)
pop() – ištrina naujausią įvestą krūvos elementą – Laiko sudėtingumas: O(1)
C++
#include> #include> using> namespace> std;> int> main() {> >stack<>int>>krūva;> >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();> >}> }> |
>
>Išvestis
cinamonas vs mate
22 21>
Laiko sudėtingumas: Šios programos laiko sudėtingumas yra O(N), kur N yra bendras elementų skaičius krūvoje. Ciklas while kartojasi N kartų, iškeldamas elementus iš krūvos ir spausdindamas juos.
Erdvės sudėtingumas: Šios programos erdvės sudėtingumas yra O(N), kur N yra bendras elementų skaičius krūvoje. Stacko duomenų struktūra naudoja erdvę, proporcingą joje saugomų elementų skaičiui. Šiuo atveju didžiausias krūvos dydis yra 5, todėl erdvės sudėtingumas yra pastovus ir gali būti laikomas O(1).
Kodo paaiškinimas:
- Įtraukite „iostream“ antraštės failą arba į mūsų kodą, kad galėtumėte naudoti jo funkcijas.
- Įtraukite dėklo antraštės failą į mūsų kodą, kad galėtumėte naudoti jo funkcijas, jei jau įtraukta, tada dėklo antraštės failo nereikia, nes jame jau yra integruota funkcija.
- Įtraukite std vardų erdvę į mūsų kodą, kad galėtumėte naudoti jos klases jos neiškvietę.
- Iškvieskite funkciją main(). Programos logika turėtų būti įtraukta į šią funkciją.
- Sukurkite krūvą sveikųjų skaičių reikšmėms saugoti.
- Naudokite funkciją push () norėdami įterpti reikšmę 21 į krūvą.
- Naudokite funkciją push () norėdami įterpti reikšmę 22 į krūvą.
- Naudokite funkciją push () norėdami įterpti reikšmę 24 į krūvą.
- Naudokite funkciją push () norėdami įterpti reikšmę 25 į krūvą.
- Norėdami įvesti kintamojo reikšmę, naudokite sveikąjį kintamojo skaičių. Čia jo reikšmė yra 0, bet mes galime priskirti bet kokią sveikojo skaičiaus reikšmę naudodami cin>> num.
- Norėdami įterpti kintamojo skaičių reikšmę, naudokite funkciją push().
- Naudokite pop() funkciją, kad pašalintumėte viršutinį elementą iš krūvos, ty 25. Viršutinis elementas dabar tampa 24.
- Naudokite pop() funkciją, kad pašalintumėte viršutinį elementą iš krūvos, ty 24. Viršutinis elementas dabar tampa 22.
- Norėdami patikrinti, ar dėklas NĖRA tuščias, naudokite trumpą kilpą ir tuščią () funkciją. ! yra NE operatorius. Taigi, kai kaminas nėra tuščias, funkcija empty() grąžins false, o operatorius NOT konvertuos jį į teisingą, o ciklas while veikia toliau. Tačiau, kai kaminas tampa tuščias, funkcija tuščias () grąžins teisingą, o operatorius NOT padarys jį klaidingu ir ciklas baigsis.
- Dabartinio krūvos turinio spausdinimas konsolėje.
- Iškvieskite funkciją pop() rietuvėje.
- Nors ciklo korpuso pabaiga.
- Pagrindinės() funkcijos korpuso pabaiga.
Stack funkcijų sąrašas:
- stack::top() C++ STL
- stack::empty() ir stack::size() C++ STL
- stack::push() ir stack::pop() C++ STL
- stack::swap() C++ STL
- stack::emplace() C++ STL
- Naujausi straipsniai apie C++ Stack