Naskládejte se C++ STL s příkladem

Co je std::stack?

Zásobník je datová struktura, která funguje na základě techniky LIFO (Last In First Out). Stack std::stack umožňuje přidávat a odebírat prvky pouze z jednoho konce.

Třída std::stack je adaptér kontejneru. Objekty kontejneru obsahují data podobného datového typu. Zásobník můžete vytvořit z různých kontejnerů sekvencí. Pokud není zadán žádný kontejner, bude standardně použit kontejner deque. Adaptéry kontejnerů nepodporují iterátory, takže je nelze použít k manipulaci s daty.

Syntaxe zásobníku

Abychom vytvořili zásobník, musíme zahrnout hlavičkový soubor v našem kódu. Tuto syntaxi pak použijeme k definování std::stack:

template <class Type, class Container = deque<Type> > class stack;

• Typ – je typ prvku obsaženého v std::stack. Může být jakákoli platná C++ typu nebo dokonce uživatelem definovaný typ.
• Kontejner – je typ podkladového objektu kontejneru.

Typy členů

Zde jsou typy členů zásobníku:

• typ_hodnoty– První parametr šablony, T. Označuje typy prvků.
• typ_kontejneru– Druhý parametr šablony, Kontejner. Označuje podkladový typ kontejneru.
• typ_velikosti– Typ integrálního čísla bez znaménka.

Operav Stack

A C++ stack podporuje následující základní operace:

• tlačit – Přidá/vloží položku do zásobníku.
• pop – Odebere/vybere položku ze zásobníku.
• peek – Vrátí nejvyšší položku zásobníku bez jejího odstranění.
• jePlný – Zkontroluje, zda je zásobník plný.
• je prázdný – Zkontroluje, zda je zásobník prázdný.

Implementace zásobníku

Následující kroky ukazují, jak se vrchol zásobníku posouvá při vkládání a následném vysouvání položek:

Krok 1) Zpočátku máme prázdný zásobník. Vrchol prázdného zásobníku je nastaven na -1.

Krok 2) Dále jsme do zásobníku vložili prvek 5. Vrchol zásobníku bude ukazovat na prvek 5.

Krok 3) Dále jsme do zásobníku vložili prvek 50. Vrchol zásobníku se posune a ukazuje na prvek 50.

Krok 4) Poté jsme provedli operaci vyjmutí, čímž jsme ze zásobníku odstranili nejvyšší prvek. Prvek 50 je ze zásobníku vyjmut. Vrchol zásobníku nyní ukazuje na prvek 5.

push() a pop()

Funkce stack::push() přidá novou položku na začátek zásobníku. Velikost zásobníku se po vložení zvětší o 1. Funkce má tuto syntaxi:

stack.push(value)

Hodnota je položka, která se má vložit do zásobníku.

Funkce stack::pop() odstraní nejvyšší prvek zásobníku. Jedná se o nejnovější prvek zásobníku. Velikost zásobníku se po odstranění zmenší o 1. Syntaxe funkce je následující:

stack.pop()

Funkce nemá žádné parametry.

Příklad 1:

#include <iostream> 
#include <stack> 
using namespace std;
int main() {
	stack<int> 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();
	}
}

Výstup:

Zde je snímek obrazovky kódu:

Code Vysvětlení:

1. Chcete-li používat jeho funkce, zahrňte do našeho kódu hlavičkový soubor iostream.
2. Chcete-li používat jeho funkce, zahrňte do našeho kódu soubor záhlaví zásobníku.
3. Zahrňte do našeho kódu jmenný prostor std, abyste mohli používat jeho třídy bez jeho volání.
4. Zavolejte funkci main(). Do této funkce by měla být přidána programová logika.
5. Vytvořte zásobník st pro uložení celočíselných hodnot.
6. Pomocí funkce push() vložte hodnotu 10 do zásobníku.
7. Pomocí funkce push() vložte hodnotu 20 do zásobníku.
8. Pomocí funkce push() vložte hodnotu 30 do zásobníku.
9. Pomocí funkce push() vložte hodnotu 40 do zásobníku.
10. Pomocí funkce pop() odeberte horní prvek ze zásobníku, tedy 40. Horní prvek se nyní změní na 30.
11. Pomocí funkce pop() odeberte horní prvek ze zásobníku, tedy 30. Horní prvek se nyní změní na 20.
12. Použijte cyklus while a funkci empty() ke kontrole, zda zásobník NENÍ prázdný. ! je operátor NOT.
13. Tisk aktuálního obsahu zásobníku na konzole.
14. Zavolejte funkci pop() na zásobníku.
15. Konec těla smyčky while.
16. Konec těla funkce main().

empty(), size(), top()

Zásobníky mají vestavěné funkce, které můžete použít k hraní si se zásobníkem a jeho hodnotami. Tyto zahrnují:

• prázdný()– kontroluje, zda je zásobník prázdný nebo ne.
• velikost()– vrací velikost zásobníku, tj. počet prvků v zásobníku.
• top()– přistupuje k prvku zásobníku nahoře.

Příklad 2:

#include <iostream> 
#include <stack>  
using namespace std;
void createStack(stack <int> mystack)
{
	stack <int> ms = mystack;
	while (!ms.empty())
	{
		cout << '\t' << ms.top();
		ms.pop();
	}
	cout << '\n';
}
int main()
{
	stack <int> 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;
}

Výstup:

Zde je snímek obrazovky kódu:

Code Vysvětlení:

1. Zahrňte hlavičkový soubor iostream do našeho kódu, abyste mohli používat jeho funkce.
2. Zahrňte do našeho kódu soubor záhlaví zásobníku, abyste mohli používat jeho funkce.
3. Zahrňte do našeho programu jmenný prostor std, abyste mohli používat jeho třídy bez jeho volání.
4. Vytvořte funkci createStack, kterou můžeme použít k vytvoření zásobníku mystack. Zásobník bude obsahovat sadu celých čísel.
5. Začátek těla funkce createStack.
6. Vytvořte instanci datového typu mystack a pojmenujte ji ms.
7. Pomocí cyklu while a funkce empty() zkontrolujte, zda je zásobník prázdný.
8. Začátek těla smyčky while.
9. Použijte funkci top() uloženou v horní části zásobníku. Znak \t vytvoří novou kartu.
10. Pomocí funkce pop() odstraňte prvek v horní části zásobníku.
11. Konec těla smyčky while.
12. Vytiskněte na konzole prázdný řádek.
13. Konec těla funkce createStack.
14. Zavolejte funkci main(). Logika programu by měla být přidána do těla funkce main().
15. Začátek těla funkce main().
16. Vytvořte objekt zásobníku st.
17. Pomocí funkce push() vložte prvek 32 do zásobníku.
18. Pomocí funkce push() vložte prvek 21 do zásobníku.
19. Pomocí funkce push() vložte prvek 39 do zásobníku.
20. Pomocí funkce push() vložte prvek 89 do zásobníku.
21. Pomocí funkce push() vložte prvek 25 do zásobníku.
22. Vytiskněte nějaký text na konzoli.
23. Chcete-li provést výše uvedené operace vložení do zásobníku, zavolejte funkci createStack.
24. Vytiskněte velikost stohu na konzole vedle jiného textu.
25. Vytiskněte prvek v horní části zásobníku na konzole.
26. Vytiskněte nějaký text na konzoli.
27. Odstraňte prvek v horní části zásobníku. Poté vrátí prvky zbývající v zásobníku.
28. Chcete-li provést výše uvedené operace, zavolejte funkci createStack.
29. Program musí po úspěšném dokončení vrátit hodnotu.
30. Konec těla funkce main().

emplace() a swap()

Toto jsou další vestavěné funkce zásobníku:

• umístit()– konstrukce poté vloží nový prvek na začátek zásobníku.
• výměna()– vyměňuje obsah zásobníku s obsahem jiného zásobníku.

Příklad 3:

#include <iostream>    
#include <stack>
#include <cstdlib>
using namespace std;
int main() {
	stack<int> st1;
	stack<int> 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();
	}
}

Výstup:

Zde je snímek obrazovky kódu:

Code Vysvětlení:

1. Chcete-li používat jeho funkce, zahrňte do našeho kódu hlavičkový soubor iostream.
2. Chcete-li používat jeho funkce, zahrňte do našeho kódu soubor záhlaví zásobníku.
3. Chcete-li používat jeho funkce, zahrňte do našeho kódu hlavičkový soubor cstdlib.
4. Zahrňte do našeho kódu jmenný prostor std, abyste mohli používat jeho třídy bez jeho volání.
5. Zavolejte funkci main(). Programová logika bude přidána do těla této funkce.
6. Deklarujte zásobník s názvem st1 pro ukládání celočíselných hodnot.
7. Deklarujte zásobník s názvem st2 pro ukládání celočíselných hodnot.
8. Pomocí funkce emplace() vložte celé číslo 12 do zásobníku s názvem st1.
9. Pomocí funkce emplace() vložte celé číslo 19 do zásobníku s názvem st1.
10. Pomocí funkce emplace() vložte celé číslo 20 do zásobníku s názvem st2.
11. Pomocí funkce emplace() vložte celé číslo 23 do zásobníku s názvem st2.
12. Pomocí funkce swap() zaměňte obsah dvou zásobníků, st1 a st2. Obsah zásobníku st1 by se měl přesunout do zásobníku st2. Obsah zásobníku st2 by se měl přesunout do zásobníku st1.
13. Vytiskněte nějaký text na konzoli.
14. Pomocí příkazu while a funkce empty() zkontrolujte, zda není zásobník st1 prázdný.
15. Vytiskněte obsah zásobníku st1 na konzole. „ “ přidává mezeru mezi prvky zásobníku při jejich tisku na konzole.
16. Spusťte funkci pop() na zásobníku st1, abyste odstranili horní prvek.
17. Konec těla příkazu while.
18. Vytiskněte nějaký text na konzoli. Konec je a C++ klíčové slovo pro koncový řádek. Přesune kurzor myši na další řádek a začne tisknout odtud.
19. Pomocí příkazu while a funkce empty() zkontrolujte, zda není zásobník st2 prázdný.
20. Vytiskněte obsah zásobníku st2 na konzole. „ “ přidává mezeru mezi prvky zásobníku při jejich tisku na konzole.
21. Spusťte funkci pop() na zásobníku st2, abyste odstranili horní prvek.
22. Konec těla příkazu while.
23. Konec těla funkce main().

Zásobník v STL

STL (Standard Template Library) přichází s třídami šablon, které poskytují společné C++ datové struktury. Proto lze zásobník implementovat i v STL. Tuto knihovnu jednoduše zahrneme do našeho kódu a použijeme ji k definování zásobníku.

stack<T> st; 

Výše uvedená syntaxe deklaruje stack st k prvkům datového typu T.

Příklad 4:

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

Výstup:

Zde je snímek obrazovky kódu:

Code Vysvětlení:

1. Chcete-li používat jeho funkce, zahrňte do našeho kódu hlavičkový soubor iostream.
2. Chcete-li používat jeho funkce, zahrňte do našeho kódu soubor záhlaví zásobníku.
3. Chcete-li používat jeho funkce, zahrňte do našeho kódu hlavičkový soubor cstdlib.
4. Zahrňte do našeho kódu jmenný prostor std, abyste mohli používat jeho třídy bez jeho volání.
5. Zavolejte funkci main(). Programová logika by měla být přidána do těla této funkce.
6. Deklarujte stack st pro ukládání celočíselných dat.
7. Přidejte prvek 12 do zásobníku.
8. Přidejte prvek 19 do zásobníku.
9. Přidejte prvek 20 do zásobníku.
10. Vytiskněte prvek v horní části zásobníku na konzole.
11. Vytiskněte velikost stohu na konzole.
12. Konec těla funkce main().

Nejčastější dotazy