Menu

Skladať dátovú štruktúru v C ++ s ilustráciou

  • Hlavná
  • Iné
  • Skladať dátovú štruktúru v C ++ s ilustráciou

stack data structure c with illustration

android interview otázky a odpovede pdf

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

Všetko, čo potrebujete vedieť o zásobníku v C ++.

Zásobník je základná dátová štruktúra, ktorá sa používa na lineárne ukladanie prvkov.

Nasleduje stoh LIFO (posledný dovnútra, prvý von) poradie alebo prístup, v ktorom sa operácie vykonávajú. To znamená, že prvok, ktorý bol do stohu pridaný ako posledný, bude prvým prvkom, ktorý bude zo stohu odstránený.

=> Navštívte tu a pozrite si celú sériu školení pre C ++ pre všetkých.

STOH

Čo sa dozviete:

Skladanie v C ++

Zásobník je podobný zásobníku v reálnom živote alebo hromade vecí, ktoré skladáme jeden nad druhým.

Ďalej je uvedené obrázkové znázornenie Stacku.

obrazové znázornenie zásobníka

Ako je znázornené vyššie, existuje hromada tanierov naukladaných na sebe. Ak k nej chceme pridať ďalšiu položku, pridáme ju do hornej časti stohu, ako je to znázornené na obrázku vyššie (ľavá strana). Táto operácia pridania položky do zásobníka sa nazýva „ Tam “.

Na pravej strane sme si ukázali opačnú operáciu, tj. Odstránime položku zo stohu. Toto sa tiež deje z rovnakého konca, tj. Z vrchu stohu. Táto operácia sa nazýva „ Pop “.

Ako je znázornené na vyššie uvedenom obrázku, vidíme, že push a pop sa uskutočňujú z rovnakého konca. Toto umožňuje zásobníku sledovať objednávku LIFO. Poloha alebo koniec, z ktorého sú položky tlačené dovnútra alebo vyskakované do / zo stohu, sa nazýva „ Horná časť stohu “.

Spočiatku, keď v zásobníku nie sú žiadne položky, je horná časť zásobníka nastavená na -1. Keď pridáme položku do stohu, horná časť stohu sa zvýši o 1, čo naznačuje, že položka bola pridaná. Na rozdiel od toho sa horná časť stohu zníži o 1, keď sa položka zo stohu vysunie.

Ďalej uvidíme niektoré základné operácie dátovej štruktúry zásobníka, ktoré budeme vyžadovať pri implementácii zásobníka.

Základné operácie

Nasledujú základné operácie, ktoré zásobník podporuje.

  • tam - Pridá alebo vloží prvok do stohu.
  • pop - Odstráni alebo vysunie prvok zo stohu.
  • nakuknúť - Získava horný prvok zásobníka, ale neodstraňuje ho.
  • je plný - Testuje sa, či je zásobník plný.
  • je prázdny - Testuje sa, či je zásobník prázdny.

Ilustrácia

Hromadná ilustrácia

Vyššie uvedený obrázok zobrazuje postupnosť operácií, ktoré sa vykonávajú na zásobníku. Spočiatku je zásobník prázdny. Pre prázdny zásobník je horná časť stohu nastavená na -1.

Ďalej vtlačíme prvok 10 do stohu. Vidíme, že horná časť stohu teraz smeruje k prvku 10.

Ďalej vykonáme ďalšiu operáciu stlačenia s prvkom 20, v dôsledku čoho teraz vrchná časť stohu ukazuje na 20. Tento stav je tretím obrázkom.

Teraz na poslednom obrázku vykonáme operáciu pop (). V dôsledku popovej operácie je prvok nasmerovaný na hornú časť stohu odstránený zo stohu. Na obrázku teda vidíme, že prvok 20 je odstránený zo stohu. Horná časť stohu teda teraz ukazuje na 10.

Týmto spôsobom môžeme ľahko rozlíšiť prístup LIFO, ktorý používa zásobník.

Implementácia

# 1) Používanie polí

Nasleduje implementácia C ++ balíka pomocou polí:

#include using namespace std; #define MAX 1000 //max size for stack class Stack { int top; public: int myStack(MAX); //stack array Stack() { top = -1; } bool push(int x); int pop(); bool isEmpty(); }; //pushes element on to the stack bool Stack::push(int item) { if (top >= (MAX-1)) { cout << 'Stack Overflow!!!'; return false; } else { myStack(++top) = item; cout<

Výkon:

The Stack Push

dva

4

6

The Stack Pop:

6

4

dva

Na výstupe vidíme, že prvky sa tlačia do zásobníka v jednom poradí a v opačnom poradí sa zo zásobníka vysunú. Toto vykazuje prístup LIFO (Last in, First out) pre zásobník.

Pre vyššie uvedenú implementáciu poľa zásobníka môžeme konštatovať, že je veľmi ľahké ho implementovať, pretože tu nie sú zahrnuté žiadne ukazovatele. Ale zároveň je veľkosť stohu statická a nemôže sa dynamicky zväčšovať alebo zmenšovať.

Ďalej budeme implementovať zásobník pomocou polí v programovacom jazyku Java.

class Stack { static final int MAX = 1000; // Maximum Stack size int top; int myStack() = new int(MAX); boolean isEmpty() { return (top = (MAX-1)) { System.out.println('Stack Overflow'); return false; } else { myStack(++top) = item; System.out.println(item); return true; } } int pop() { if (top <0) { System.out.println('Stack Underflow'); return 0; } else { int item = myStack(top--); return item; } } } //Main class code class Main { public static void main(String args()) { Stack stack = new Stack(); System.out.println('Stack Push:'); stack.push(1); stack.push(3); stack.push(5); System.out.println('Stack Pop:'); while(!stack.isEmpty()) { System.out.println(stack.pop()); } } }

Výkon:

Stack Push:

1

3

5

Stack Pop:

5

3

1

Logika implementácie je rovnaká ako v implementácii C ++. Výstup ukazuje techniku ​​LIFO vtláčania a vyskakovania prvkov do / zo zásobníka.

Ako už bolo uvedené, implementácia zásobníka pomocou polí je najjednoduchšia implementácia, ale má statický charakter, pretože nemôžeme zásobník dynamicky zväčšovať alebo zmenšovať.

# 2) Používanie prepojeného zoznamu

Ďalej implementujeme operácie zásobníka pomocou prepojeného zoznamu v C ++ aj Java. Najskôr si ukážeme implementáciu v C ++.

#include using namespace std; // class to represent a stack node class StackNode { public: int data; StackNode* next; }; StackNode* newNode(int data) { StackNode* stackNode = new StackNode(); stackNode->data = data; stackNode->next = NULL; return stackNode; } int isEmpty(StackNode *root) { return !root; } void push(StackNode** root, int new_data){ StackNode* stackNode = newNode(new_data); stackNode->next = *root; *root = stackNode; cout<data; free(temp); return popped; } int peek(StackNode* root) { if (isEmpty(root)) return -1; return root->data; } int main() { StackNode* root = NULL; cout<<'Stack Push:'<

Výkon:

Stack Push:

100

200

300

Vrchný prvok je 300

Stack Pop:

300

200

100

Najvyšší prvok je -1

Ďalej uvádzame implementáciu zásobníka Java pomocou prepojeného zoznamu.

class LinkedListStack { StackNode root; static class StackNode { int data; StackNode next; StackNode(int data) { this.data = data; } } public boolean isEmpty() { if (root == null) { return true; } else return false; } public void push(int new_data) { StackNode newNode = new StackNode(new_data); if (root == null) { root = newNode; } else { StackNode temp = root; root = newNode; newNode.next = temp; } System.out.println(new_data); } public int pop() { int popped = Integer.MIN_VALUE; if (root == null) { System.out.println('Stack is Empty'); } else { popped = root.data; root = root.next; } return popped; } public int peek() { if (root == null) { System.out.println('Stack is empty'); return Integer.MIN_VALUE; } else { return root.data; } } } class Main{ public static void main(String() args) { LinkedListStack stack = new LinkedListStack(); System.out.println('Stack Push:'); stack.push(100); stack.push(200); stack.push(300); System.out.println('Top element is ' + stack.peek()); System.out.println('Stack Pop:'); while(!stack.isEmpty()){ System.out.println(stack.pop()); } System.out.println('Top element is ' + stack.peek()); } }

Výkon:

Stack Push:

100

200

300

Vrchný prvok je 300

Stack Pop:

300

200

100

Zásobník je prázdny

Vrchný prvok je -2147483648

Práve sme videli implementácie C ++ a Java pre zásobník pomocou prepojených zoznamov. Každú položku zásobníka reprezentujeme ako uzol prepojeného zoznamu. Najdôležitejšou výhodou tejto implementácie je, že je dynamická. To znamená, že môžeme zväčšiť alebo zmenšiť veľkosť stohu podľa našich požiadaviek.

Je to na rozdiel od prípadu implementácie zásobníka pomocou polí, v ktorých musíme vopred deklarovať veľkosť a nemôžeme ju dynamicky meniť.

Nevýhodou pre túto implementáciu je, že keďže všade používame ukazovatele, v porovnaní s implementáciou poľa to zaberá trochu príliš veľa miesta.

Ako môžem zobraziť súbor eps

Aplikácie Stack

Poďme diskutovať o niektorých aplikáciách dátovej štruktúry zásobníka. Skladba dátovej štruktúry sa používa v rade aplikácií v softvérovom programovaní hlavne kvôli jej jednoduchosti a ľahkej implementácii.

Ďalej stručne opíšeme niektoré aplikácie zásobníka:

# 1) Infix do výrazov Postfix

Akýkoľvek všeobecný aritmetický výraz má tvar operand1 OP operand 2 .

Na základe pozície operátora OP máme tieto typy výrazov:

  • Infix - Všeobecná forma výrazu infix je „ operand1 OP operand 2 “. Toto je základná forma výrazu, ktorú v matematike používame stále.
  • Predpona - Keď je operátor umiestnený pred operandmi, je to predponový výraz. Všeobecná forma infixového výrazu je „ OP operand1 operand2 “.
  • Postfix - Vo výrazoch postfix sa najskôr zapíšu operandy a potom operátor. Má formu „operand1 operand2 OP“.

Zvážte výraz „a + b * c „ . Kompilátor skenuje výraz zľava doprava alebo sprava doľava. Ak sa postaráme o prednosť operátora a asociativitu, najskôr naskenuje výraz, aby vyhodnotil výraz b * c. Ďalej bude musieť znova naskenovať výraz a pridať výsledok b * c do a.

Ako sú výrazy čoraz zložitejšie, stáva sa tento druh prístupu k opakovanému skenovaniu výrazu neefektívnym.

Aby sme prekonali túto neefektívnosť, prevedieme výraz na postfix alebo prefix, aby ich bolo možné ľahko vyhodnotiť pomocou dátovej štruktúry zásobníka.

# 2) Analýza / vyhodnotenie výrazov

Pomocou zásobníka môžeme vykonať aj samotné vyhodnotenie výrazu. V tomto sa výraz skenuje zľava doprava a operandy sa posúvajú do zásobníka.

Kedykoľvek sa vyskytne operátor, operandy sa vyskakujú a operácia sa vykoná. Výsledok operácie sa opäť posunie do zásobníka. Týmto spôsobom sa výraz hodnotí pomocou zásobníka a konečným výsledkom výrazu je zvyčajne aktuálna horná časť zásobníka.

# 3) Traverzy stromov

Stromovú dátovú štruktúru je možné prechádzať, aby sme navštívili každý uzol mnohými spôsobmi a v závislosti od toho, kedy je navštívený koreňový uzol, ktorý máme.

  • priechod objednávky
  • predobjednať Traversal
  • priechod objednávky

Aby sme mohli efektívne prechádzať stromom, využívame dátovú štruktúru zásobníka, aby sme tlačili medziľahlé uzly na zásobníku, aby sme udržali poradie priechodu.

# 4) Triediace algoritmy

Algoritmy na triedenie ako quicksort je možné zefektívniť pomocou dátových štruktúr zásobníka.

# 5) Hanojské veže

Toto je klasický problém zahŕňajúci n počet diskov a tri veže a problém spočíva v premiestňovaní diskov z jednej veže do druhej, pričom tretia veža sa používa ako medziľahlá.

Tento problém je možné efektívne vyriešiť použitím stohu, keď tlačíme na disky, ktoré sa majú presunúť, do stohu, pretože stoh v zásade funguje ako veža slúžiaca na presun diskov.

Záver

Zásobník je najjednoduchšia dátová štruktúra a ľahšie sa implementuje ako program. Využilo to prístup LIFO (posledný dovnútra, prvý von), čo znamená, že naposledy zadaný prvok je ten, ktorý sa odstráni ako prvý. Je to preto, že zásobník používa na pridávanie (tlačenie) a odstraňovanie (vyskakovanie) prvkov iba jeden koniec.

Skladba dátovej štruktúry má mnoho využití v programovaní softvéru. Najvýznamnejším z nich je hodnotenie expresie. Hodnotenie výrazov zahŕňa aj prevod výrazu z infixu na postfix alebo prefix. Zahŕňa to aj vyhodnotenie výrazu, aby sa dosiahol konečný výsledok.

V tomto tutoriáli sme videli ilustráciu a implementáciu zásobníka, ako aj jeho rôzne operácie.

V našom pripravovanom výučbe sa podrobne dozvieme o štruktúre údajov frontu.

=> Navštívte tu kompletný kurz C ++ od odborníkov.

Odporúčané čítanie

^