Stacky jsou typem adaptérů kontejnerů s typem práce LIFO (Last In First Out), kde je nový prvek přidán na jeden konec (nahoře) a prvek je odstraněn pouze z tohoto konce. Stack používá zapouzdřený objekt obou vektor nebo deque (standardně) popř seznam (třída sekvenčního kontejneru) jako jeho základní kontejner, který poskytuje specifickou sadu členských funkcí pro přístup k jeho prvkům.
js dekódování base64
Pokud existuje zmatek při zapamatování základního rozdílu mezi zásobníkem a frontou, pak si vezměte reálný příklad pro toto rozlišení, pro stohování, skládání knih můžeme snadno vzít horní knihu a pro frontu si zapamatovat, kdy musíte stát ve frontě vpředu bankomatu pro výběr hotovosti, pak má první osoba v blízkosti bankomatu první šanci peníze z bankomatu vybrat. Fronta tedy funguje typu FIFO (First In First Out).
Syntaxe zásobníku:-
Pro vytvoření zásobníku musíme do našeho kódu zahrnout hlavičkový soubor. Tuto syntaxi pak použijeme k definování std::stack:
| šablona |
Typ – je typ prvku obsaženého v std::stack. Může to být jakýkoli platný typ C++ nebo dokonce uživatelsky definovaný typ.
Kontejner – je typ podkladového objektu kontejneru.
Typy členů: -
value_type- První parametr šablony, T. Označuje typy prvků.
container_type- Druhý parametr šablony, kontejner. Označuje základní typ kontejneru.
size_type- Integrální typ bez znaménka.
Funkce spojené se zásobníkem jsou:
empty() – Vrací, zda je zásobník prázdný – Časová složitost: O(1)
size() – Vrátí velikost zásobníku – Časová složitost: O(1)
top() – Vrací odkaz na nejvyšší prvek zásobníku – Časová složitost: O(1)
push(g) – Přidá prvek „g“ na vrchol zásobníku – Časová složitost: O(1)
pop() – Odstraní naposledy zadaný prvek zásobníku – Časová složitost: O(1)
C++
ve srovnání s metodou java
#include> #include> using> namespace> std;> int> main() {> >stack<>int>>zásobník;> >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();> >}> }> |
>
>Výstup
22 21>
Časová složitost: Časová složitost tohoto programu je O(N), kde N je celkový počet prvků v zásobníku. Smyčka while se Nkrát iteruje, vyjme prvky ze zásobníku a vytiskne je.
Složitost prostoru: Prostorová složitost tohoto programu je O(N), kde N je celkový počet prvků v zásobníku. Datová struktura zásobníku využívá prostor úměrný počtu prvků v ní uložených. V tomto případě je maximální velikost zásobníku 5, takže prostorová složitost je konstantní a lze ji považovat také za O(1).
Vysvětlení kódu:
- Chcete-li používat jeho funkce, zahrňte soubor záhlaví iostream nebo do našeho kódu.
- Zahrňte do našeho kódu soubor záhlaví zásobníku, abyste mohli používat jeho funkce, pokud jsou již zahrnuty, pak soubor záhlaví zásobníku nepotřebujete, protože má již vestavěnou funkci.
- Zahrňte do našeho kódu jmenný prostor std, abyste mohli používat jeho třídy bez jeho volání.
- Zavolejte funkci main(). Do této funkce by měla být přidána programová logika.
- Vytvořte zásobník pro ukládání celočíselných hodnot.
- Pomocí funkce push() vložte hodnotu 21 do zásobníku.
- Pomocí funkce push() vložte hodnotu 22 do zásobníku.
- Pomocí funkce push() vložte hodnotu 24 do zásobníku.
- Pomocí funkce push() vložte hodnotu 25 do zásobníku.
- K zadání hodnoty proměnné použijte celočíselnou proměnnou num. Zde je jeho hodnota 0, ale můžeme přiřadit libovolnou celočíselnou hodnotu pomocí cin>> num.
- Pomocí funkce push() vložte hodnotu proměnné num.
- Použijte funkci pop() k odstranění horního prvku ze zásobníku, tedy 25. Horní prvek se nyní změní na 24.
- Použijte funkci pop() k odstranění horního prvku ze zásobníku, tedy 24. Horní prvek se nyní změní na 22.
- Použijte cyklus while a funkci empty() ke kontrole, zda zásobník NENÍ prázdný. ! je operátor NOT. Když tedy zásobník není prázdný, funkce empty() vrátí hodnotu false a operátor NOT ji převede na hodnotu true a cyklus while bude pokračovat. Ale když se zásobník vyprázdní, funkce empty() vrátí hodnotu true a operátor NOT ji nastaví na hodnotu false a smyčka skončí.
- Tisk aktuálního obsahu zásobníku na konzole.
- Zavolejte funkci pop() na zásobníku.
- Konec těla smyčky while.
- Konec těla funkce main().
Seznam funkcí Stack:
- stack::top() v C++ STL
- stack::empty() a stack::size() v C++ STL
- stack::push() a stack::pop() v C++ STL
- stack::swap() v C++ STL
- stack::emplace() v C++ STL
- Nedávné články o C++ Stack