Menu

Stohy a fronty v STK

stacks queues stl

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Naučte sa implementáciu zásobníkov a front v STK s príkladmi.

Stohy a fronty sú dva kontajnery v STL, ktoré majú veľmi základnú povahu. Sú to najjednoduchšie kontajnery, ktoré majú široké použitie v programovaní softvéru.

V tomto tutoriáli uvidíme podrobnú implementáciu oboch týchto kontajnerov v STL. Prejdeme si tiež rôzne operácie podporované zásobníkom a radom s príkladmi.

=> Dajte si pozor na jednoduchú sériu školení C ++ tu.

ZÁSOBY A fronty v STL

Čo sa dozviete:

Stohy

Stohový kontajner v STL je typ adaptéra na kontajner. Používa sa na replikáciu dátovej štruktúry zásobníka v C ++. Zásobník je sada prvkov, do ktorých sú prvky vložené na jednom konci a na rovnakom konci sú tiež odstránené.

Tento spoločný bod pridávania a vypúšťania je známy ako „Top of the stack“.

Obrázkové znázornenie zásobníka je uvedené nižšie.

stoh

Ako je znázornené na vyššie uvedenom obrázku, zásobník je kontajner, v ktorom sú pridávané a mazané prvky z rovnakého konca, ktorý sa nazýva Vrch zásobníka.

Pretože pridávanie a mazanie sa deje na rovnakom konci, môžeme povedať, že zásobníkový kontajner je typ práce LIFO (posledný dovnútra, prvý von). To znamená, že prvkom, ktorý bude pridaný ako prvý, bude posledný, ktorý bude odstránený.

Aby sme mohli implementovať zásobníkový kontajner, musíme do nášho programu zahrnúť hlavičku.

#include

Syntax všeobecnej deklarácie pre zásobníkový zásobník je:

stack stackName;

Stohové operácie

Ďalej poďme diskutovať o rôznych operáciách, ktoré podporuje zásobník v STL.

  • tam : operácia push sa používa na vloženie prvku do stohu. Táto operácia vždy pridáva prvky do hornej časti zásobníka.

Zvážte prázdny zásobník mystack typu integer .

mystack

Ďalej pridajme prvok 1 do stohu.

pridať prvok 1 do stohu

Potom do zásobníka pridáme prvok 3.

pridajte prvok 3 do stohu

Podľa znázornenia je v dôsledku operácie stlačenia pridaný prvok do hornej časti stohu. Po každej operácii stlačenia sa veľkosť stohu zvýši o 1.

  • pop : popová operácia sa používa na odstránenie prvku zo zásobníka. Odstránený prvok je ten, na ktorý ukazuje horná časť stohu. V dôsledku operácie pop sa veľkosť stohu zmenší o 1.

Pozrime sa, ako vyzerá popová operácia:

Zvážte zásobník mystack ako je uvedený vyššie, do ktorého sme už vložili 2 prvky.

mystack2

Teraz nazvime funkciu pop (). Po vykonaní tohto hovoru sa prvok v hornej časti zásobníka odstráni a vrchná časť ukazuje na nasledujúci prvok, ako je uvedené nižšie.

prvok „3“ je odstránený popovou operáciou

Ak znova zavoláme pop (), nasledujúci prvok (v tomto prípade 1) bude odstránený, čo má za následok prázdny zásobník.

prvok „1“ je odstránený - operácia zásobníka

rozdiel medzi stromom b a stromom b +
  • hore : Vráti najvrchnejší prvok stohu.
  • prázdny : Skontroluje, či je stoh prázdny alebo nie.
  • veľkosť: Vráti veľkosť stohu, tj počet prvkov v stohu.

Ďalej je uvedený príklad implementácie Stacku na lepšie pochopenie operácií.

#include #include using namespace std; void printStack(stack stk) { while (!stk.empty()) { cout << ' ' << stk.top(); stk.pop(); } cout << ' '; } int main () { stack oddstk; oddstk.push(1); oddstk.push(3); oddstk.push(5); oddstk.push(7); oddstk.push(9); cout << 'The stack is : '; printStack(oddstk); cout << ' Size of stack: ' << oddstk.size(); cout << ' Top of stack: ' << oddstk.top(); cout << ' oddstk.pop() : '; oddstk.pop(); printStack(oddstk); cout<<' Another pop(): '; oddstk.pop(); printStack(oddstk); return 0; }

výstup implementácie zásobníka

Vyššie uvedený príklad jasne ukazuje operáciu push, ktorá generuje zásobník. Ukazuje tiež zásobník po dvoch po sebe idúcich operáciách popu.

Takto sme videli zásobník a jeho operácie v STL. Ďalej v tomto tutoriále uvidíme podrobnú implementáciu ešte jedného jednoduchého kontajnera STL, ktorým je „Queue“.

Fronta

Fronta je ďalším kontajnerom v STL, ktorý je tiež veľmi jednoduchý a užitočný. Kontajner frontu je replikou dátovej štruktúry frontu v C ++. Na rozdiel od stohu sú v kontajneri frontu dva konce, teda predný a zadný.

Prvky sa do fronty pridávajú zozadu, zatiaľ čo sa odstránia z prednej časti frontu. Vo všeobecnosti sa vo fronte používa typ usporiadania FIFO (prvý vstup, prvý výstup).

Aby sme mohli implementovať frontový kontajner do programu, musíme do kódu zahrnúť hlavičku.

#include

Všeobecná syntax pre vyhlásenie frontu je:

fronta queue_name;

Kontajner frontu deklarujeme takto:

Queue myqueue;

Fronta operácií

Teraz uvidíme rôzne operácie podporované frontou.

  • tam: Funkcia „push“ pridá prvok na koniec poradia, tzn. Na jeho koniec.
  • pop: Funkcia „pop“ odstráni prvý prvok vo fronte, tj. Prvok pred frontom.

Pochopme funkcie push a pop frontu.

Zvážte prázdny rad vyhlásený nad myqueue. Teraz posunieme párne číslo 2 do poradia s operáciou

myqueue.push (2);

Teraz bude fronta vyzerať takto:

myqueue.pop ();

Ďalej do poradia pridáme „4“ s volaním „myqueue.push (4)“.

kde je kľúč zabezpečenia siete na mojom smerovači

Teraz fronta vyzerá takto:

myqueue.push (4)

Ako je vidieť vyššie, prvky sú tlačené do fronty zo zadného konca alebo zozadu.

Teraz otvorme operáciu myqueue.

myqueue.pop ();

myqueue.pop ();

Ako teda vidíme, pri volaní pop () je odstránený prvok pred frontou. To znamená, že prvý prvok, ktorý je zaradený do poradia, je prvým prvkom, ktorý je mimo poradia.

  • predná strana: Táto funkcia vráti odkaz na prvý prvok frontu.
  • späť: Back vráti odkaz na posledný prvok vo fronte.
  • prázdny: Skontroluje, či je rad prázdny.
  • veľkosť: Vráti veľkosť frontu, t. J. Počet prvkov vo fronte.

Nižšie je uvedený príkladový program, ktorý demonštruje operácie používané v kontajneri frontu.

#include #include using namespace std; void printQueue(queue myqueue) { queue secqueue = myqueue; while (!secqueue.empty()) { cout << ' ' << secqueue.front(); secqueue.pop(); } cout << ' '; } int main() { queue myqueue; myqueue.push(2); myqueue.push(4); myqueue.push(6); myqueue.push(8); cout << 'The queue myqueue is : '; printQueue(myqueue); cout << ' myqueue.size() : ' << myqueue.size(); cout << ' myqueue.front() : ' << myqueue.front(); cout << ' myqueue.back() : ' << myqueue.back(); cout << ' myqueue.pop() : '; myqueue.pop(); printQueue(myqueue); return 0; }

Výkon:

Myqueue frontu je: 2 4 6 8

myqueue.size (): 4

myqueue.front (): 2

myqueue.back (): 8

myqueue.pop (): 4 6 8

Ako je uvedené vyššie, najskôr deklarujeme kontajner frontu. Potom pomocou operácie push do nej pridáme prvé štyri párne čísla. Potom vysunieme prvok z frontu a zobrazíme zmenený front.

kontajner fronty

Záver

Týmto sme sa dostali na koniec tohto tutoriálu o zásobníkoch a radoch. Ako už bolo spomenuté, jedná sa o najjednoduchšie kontajnery, ktoré máme v STL. Ďalšia variácia kontajnera frontu je známa ako „Prioritný front“.

V našom pripravovanom výučbe sa budeme zaoberať viac o prioritnej fronte v STL !!

=> Navštívte tu a dozviete sa C ++ od nuly.

Odporúčané čítanie

^