C++ Datová struktura zásobník
V tomto článku se podíváme na to, co je to zásobník, jak funguje a jak jej lze naimplementovat. Ukážeme
si také krátký příklad, ve kterém zásobník využijeme. Veškerá implementace bude provedena v jazyce C++,
proto se předpokládá alespoň základní znalost syntaxe a znalost objektově orientovaného programování.
11.11.2010 00:00 |
Petr Sklenička
| Články autora
| přečteno 15785×
Co je to zásobník a jak funguje
Zásobník, neboli anglicky stack, je datová struktura, u níž je přesně určen způsob přidávání a odebírání prvků.
U zásobníku je uplatněn způsob LIFO (last in, first out), česky "první dovnitř, poslední ven". Přesným opakem
zásobníku je fronta, kde je uplatně způsob FIFO (first in, first out), o tom ale článek není. Pro lepší pochopení, jak
zásobník funguje, si představte zásobník u pistole. Budeme-li do tohoto zásobníku ukládat náboje, vezmeme první, dáme jej do
zásobníku a náboj spadne na dno zásobníku. Vezmeme druhý náboj, vložíme do zásobníku a druhý náboj zůstane ležet na prvním
náboji. Celý tento postup opakujeme do doby, než bude zásobník pistole plný. Poslední náboj, který jsme do pistole vložili, bude
tedy v zásobníku úplně nahoře. Způsob přidávání prvků do zásobníku jakožto do datové struktury je úplně stejný. Co se týče
odebírání prvků ze zásobníku, opět jde o stejný způsob jako o odebrání (vystřelení) náboje ze zásobníku pistole. Vložíme-li
zásobník do pistole a stiskneme-li spoušť, jako první vyletí námi naposledy přidaný náboj. Náboj, který jsme vložili jako
první, přijde na řadu až jako poslední. V tom je tedy ukryt onen způsob LIFO. Námi první vložený náboj opustí zásobník až jako
poslední a není jiná možnost, jak jej vyjmout předtím, než odstraníme náboje nad ním.
Nyní se seznámíme s několika pojmy, které se u zásobníku používají. Začneme ukazatelem na aktální prvek v zásobníku (to je
ten, který jsme vložili jako poslední, čili je na vrcholu zásobníku), který se nazývá vrchol zásobníku, anglicky stack
pointer. Metoda, určená pro přidávání prvků do zásobníku, se většinou nazývá push. Metodu, která se stará o vyjmutí
prvků, nazýváme nejčastěji pop. Počet prvků v zásobníku je víceméně neomezený, jedinným omezením nám může být
paměť počítače.
Jak lze zásobník implementovat
Způsob, jak implementovat zásobník, není víceméně dán nějak striktně, důležité pouze je, aby splňoval vlastnosti, které jsme
si uvedli výše. Proto řešení, které uvádím zde, rozhodně není jediné, možností je více. Moje řešení spočívá v tom, že jsem si
napsal třídu Stack, která vypadá takto:
Takto jednoduše by mohla vypadat třída, reprezentující zásobník. Do tohoto zásobníku je možné ukládat pouze čísla typu int, nicméně
pro pochopení by to mělo stačit. Věřím, že po přečtení článku budete schopni sami implementovat zásobník, do kterého
bude možno uložit něco jiného.
Členská proměnná stackPointer si pamatuje číslo prvku, který byl přidán naposled. Slouží tedy jako vrchol zásobníku.
Pointer items ukazuje na pole prvků zásobníku (v tuto chvíli ještě ne, po zavolání konstruktoru třídy však ano). Do proměnné
maxSize se uloží velikost zásobníku. Nyní se tedy podívejme na těla metod a na tělo konstruktoru.
Konstruktor má jeden parametr, který určuje maximální velikost zásobníku. Tato hodnota se uloží do proměnné maxSize.
Dále se v konstruktoru stanou dvě věci - alokuje se pole typu int o velikosti maxSize a proměnná stackPointer se nastaví na nulu,
neboť právě vytvořený zásobník neobsahuje žádný prvek. Co se týče metody push, není na ní nic těžkého. Do pole items se uloží prvek x a
hodnota proměnné stackPointer se zvýší o jedničku. Stejně jednoduchá jako metoda Push je jednoduchá i metoda Pop. Hodnota
proměnné stackPointer se snižuje o jedničku, neboť prvek vyzvedáváme ze zásobníku. Všimněte si, že vyjmutý prvek v poli
zůstane, nebude možné k němu však již přistoupit a při přidání nového prvku se tento prvek přepíše. V obou metodách je přidána
podmínka, která ověřuje, jestli zásobník není prázdný, resp. plný.
Zásobník v praxi
Pevně věřím tomu, že jste pochopili, jak zásobník funguje a jak jej lze implementovat. Nezmínil jsem se však, kdy se nám
zásobník může hodit. Úplně jednoduchým příkladem může být program, který umí vyhodnotit výraz v postfixové notaci. Pokud nevíte,
jak postfixová notace vypadá, doporučuji se podívat zde.
Velmi zjednodušeně by se dal algoritmus popsat takto: celý řetězec (řetezcem je myšlen uživatelem zadaný výraz) si rozložíme
na jednotlivá čísla a operátory, přičemž je
budeme postupně procházet. Přečteme tedy první znak (buď číslo, nebo operátor) a pokud to bude číslo, uložíme jej na zásobník.
V opačném případě se musí jednat o operátor, což pro nás znamená, že musíme provést nějakou operaci (záleží na tom, o jaký
operátor se bude jednat). Předpokládejme, že se jedná o operátor plus. Vyzvedeme tedy ze zásobníku dvě čísla, která sečteme a
výsledek uložíme zpět na zásobník. Celý tento postup budeme opakovat tak dlouho, dokud neprojdeme celý, uživatelem zadaný
řetězec. Výsledek celého výrazu bude uložen v zásobníku. Zavoláme tedy metodu Pop a získáme konečný výsledek. Pro
dokonalé pochopení si zkusme nyní vyhodnotit výraz 3 5 + 4 -.
Přečteme tedy první znak, to je číslo 3. Vzhledem k tomu, že je to číslo, uložíme jej na zásobník. Následuje číslo
5, které také uložíme na zásobník. V zásobníku tedy máme číslo 3 a nad ním číslo 5. Dalším znakem je operátor plus,
takže potřebujeme ze zásobníku vyzvednout dvě hodnoty. Dostaneme číslo 3 a číslo 5. Pozor - je nutné si
uvědomit, že v tuto chvíli je zásobník prázdný! Čísla 3 a 5 sečteme a výsledek (8) uložíme opět na zásobník.
Nyní tedy máme v zásobníku jednu hodnotu, konkrétně číslo 8. Dalším znakem je číslo 4, uložíme jej na zásobník. Posledním
znakem je operátor minus. Vezmeme dvě čísla ze zásobníku, tedy čísla 8 a 4 a provedeme výpočet 8 - 4, což je 4.
Tuto hodnotu uložíme opět na zásobník. Další znaky v řetězci nemáme, proto zavoláme metodu Pop, která nám vyzvedne
prvek ze záobníku, který je výsledkem celého výrazu - jde o číslo 4, což je správný výsledek.
Pozn.: Celý algoritmus bude správně fungovat pouze za předpokladu, že uživatel zadá výraz správně. Zachycení výjimek
není žádná složitá věc a k použití zásobníku se nevztahuje, proto jsem to zde nezmiňoval.
Pokud jste pochopili způsob vyhodnocování postfixového výrazu, určitě zvládnete výše uvedený algoritmus přepsat na zdrojový kód,
nicméně i přesto si jej můžete stáhnout a podívat se, jak by to mohlo vypadat. Jen ještě jednou opakuji, program není ošetřen
proti nesprávným vstupům a akceptuje pouze operátory plus a minus. Způsob, jakým dopsat chybějící operátory je velmi snadný,
víceméně podobný jako způsob, jakým jsou napsány operátory plus a minus.
Zdrojové kódy: Postfix.rar
Verze pro tisk
|
Příspívat do diskuze mohou pouze registrovaní uživatelé.
|
|

Vyhledávání software

Vyhledávání článků
17.4.2018 0:46 /František Kučera Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář
16.3.2018 22:01 /František Kučera Kulatý OpenAlt sraz v Praze oslavíme klasicky: u limonády a piva! Přijďte si posedět, dát si dobré jídlo a vybrat z mnoha piv do restaurace Kulový blesk, který najdete v centru Prahy nedaleko metra I. P. Pavlova na adrese Sokolská 13, Praha 2. Sraz se koná ve čtvrtek 22. března a začínáme v 18:00. Heslo: OpenAlt. Vezměte s sebou svoje hračky! Uvítáme, když si s sebou na sraz vezmete svoje oblíbené hračky. Jestli máte nějaký drobný projekt postavený na Arduinu, nějakou zajímavou elektronickou součástku, či třeba i pěkný úlovek z crowdfundingové akce, neváhejte. Oslníte ostatní a o zábavu bude postaráno.
Přidat komentář
13.2.2018 0:41 /František Kučera Únorový pražský sraz OpenAltu se koná 15. 2. 2018 a tentokrát se vydáme na návštěvu do jednoho pražského datacentra. Sejdeme se v 17:50 v severovýchodní části nástupiště tramvajové zastávky Koh-I-Noor. Po exkurzi se přesuneme do restaurace U Pštrosa (Moskevská 49), kde probereme tradiční témata (svobodný software a hardware, DIY, CNC, SDR, 3D tisk…) a tentokrát bude k vidění i IoT brána od The Things Network.
Přidat komentář
11.2.2018 23:11 /Petr Ježek Hledáte lehký a rychlý prolížeč PDF souborů? Pokud vás již omrzelo čekat na načítání stránek či jiné nešvary, zkuste xreader.
Přidat komentář
11.2.2018 20:35 /Redakce Linuxsoft.cz Třetí ročník odborné IT konference na téma Cloud computing v praxi proběhne ve čtvrtek 1. března 2018 v konferenčním centru Vavruška, v paláci Charitas, Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00 hod. dopoledne do cca 16 hod. odpoledne. Konference o trendech v oblasti cloud computingu nabídne i informace o konkrétních možnostech využívání cloudů a řešení vybraných otázek souvisejících s provozem IT infrastruktury.
Přidat komentář
15.1.2018 0:51 /František Kučera První letošní pražský sraz se koná již tento čtvrtek 18. ledna od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Vítáni jsou všichni příznivci svobodného softwaru a hardwaru, ESP32, DIY, CNC, SDR nebo dobrého piva. Prvních deset účastníků srazu obdrží samolepku There Is No Cloud… just other people's computers. od Free Software Foundation.
Přidat komentář
14.11.2017 16:56 /František Kučera Máš rád svobodný software a hardware nebo se o nich chceš něco dozvědět? Zajímá tě DIY, CNC, SDR nebo morseovka? Přijď na sraz spolku OpenAlt – tradičně první čtvrtek před třetím pátkem v měsíci: 16. listopadu od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5).
Přidat komentář
12.11.2017 11:06 /Redakce Linuxsoft.cz PR: 4. ročník odborné IT konference na téma Datová centra pro business proběhne již ve čtvrtek 23. listopadu 2017 v konferenčním centru Vavruška, v paláci Charitas, Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00. Konference o návrhu, budování, správě a efektivním využívání datových center nabídne odpovědi na aktuální a často řešené otázky, např Jaké jsou aktuální trendy v oblasti datových center a jak je využít pro vlastní prospěch? Jak zajistit pro firmu či jinou organizaci odpovídající služby datových center? Podle jakých kritérií vybrat dodavatele služeb? Jak volit součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně spravovat datové centrum? Jak eliminovat možná rizika? apod.
Přidat komentář
Více ...
Přidat zprávičku
 Poslední diskuze
20.2.2018 18:48 /
Ivan Majer portal
20.2.2018 15:57 /
Jan Havel Jak využíváte služby cloudu v podnikání?
16.1.2018 1:08 /
Ivan Pittner verejna ip od o2 ubuntu
15.1.2018 17:26 /
Mira Harvalik Re: Jak udělat HTML/Javascript swiping gallery do mobilu?
30.12.2017 20:16 /
Michal Knoll odmocnina
Více ...
|