LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

> 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 20265×

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

pridej.cz

 

DISKUZE

#include "stdio.h" 11.11.2010 07:34 Jan Němec
|- Re: #include "stdio.h" 11.11.2010 11:04 Petr Sklenička
L Re: #include "stdio.h" 26.11.2010 12:10 Aleš Hakl
std c++ knihovna 11.11.2010 10:22 Radim Kolář




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1

12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář

6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář

18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business. Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář

12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář

16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

31.7.2023 14:13 / Linda Graham
iPhone Services

30.11.2022 9:32 / Kyle McDermott
Hosting download unavailable

13.12.2018 10:57 / Jan Mareš
Re: zavináč

2.12.2018 23:56 / František Kučera
Sraz

5.10.2018 17:12 / Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2024) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze