>
Meni

Struktura podatkov skladov v C ++ z ilustracijo

  • Glavni
  • Drugo
  • Struktura podatkov skladov v C ++ z ilustracijo

stack data structure c with illustration

spletna mesta za ogled anime angleščine, sinhronizirane

Vse, kar morate vedeti o skladu v C ++.

Stack je temeljna podatkovna struktura, ki se uporablja za linearno shranjevanje elementov.

Sledi sklad LIFO (zadnji vstop, prvi izstop) vrstni red ali pristop, v katerem se izvajajo operacije. To pomeni, da bo element, ki je bil nazadnje dodan v sklad, prvi element, ki bo odstranjen iz sklada.

=> Obiščite tukaj, da si ogledate celotno serijo C ++ usposabljanj za vse.

ZLOG

Kaj se boste naučili:

Zložite v C ++

Sklop je podoben resničnemu skladu ali kupu stvari, ki jih zložimo eno nad drugo.

Spodaj je slikovna predstavitev Stacka.

slikovni prikaz sklada

Kot je prikazano zgoraj, je kup plošč, zloženih ena na drugo. Če mu želimo dodati še en element, ga dodamo na vrh sklada, kot je prikazano na zgornji sliki (leva stran). Ta postopek dodajanja elementa v sklad se imenuje » Potisni '.

Na desni strani smo prikazali nasprotno operacijo, torej odstranimo element iz sklada. To se naredi tudi z istega konca, to je z vrha sklada. Ta operacija se imenuje Pop '.

Kot je prikazano na zgornji sliki, vidimo, da se potiskanje in popuščanje izvajata z istega konca. Tako je sklad skladen z vrstnim redom LIFO. Položaj ali konec, s katerega se predmeti potiskajo ali izstopajo v / iz sklada, se imenuje „ Vrh sklada '.

Ko na vrhu ni elementov, je vrh sklada nastavljen na -1. Ko v sklad dodamo element, se vrh sklada poveča za 1, kar pomeni, da je element dodan. V nasprotju s tem se zgornji del sklada zmanjša za 1, ko element izskoči iz sklada.

Nato bomo videli nekaj osnovnih operacij strukture podatkov sklada, ki jih bomo potrebovali med izvajanjem sklada.

Osnovne operacije

Sledijo osnovne operacije, ki jih podpira sklad.

  • potisni - Doda ali potisne element v sklad.
  • pop - Odstrani ali izvleče element iz sklada.
  • pokukati - Pridobi zgornji element sklada, vendar ga ne odstrani.
  • je polna - Preizkusi, ali je sklad poln.
  • je prazno - Preizkusi, ali je sklad prazen.

Ilustracija

Ilustracija sklada

Zgornja ilustracija prikazuje zaporedje operacij, ki se izvajajo na skladišču. Sprva je kup prazen. Za prazen kup je vrh sklada nastavljen na -1.

Nato potisnemo element 10 v sklad. Vidimo, da zgornji del sklada zdaj kaže na element 10.

Nato izvedemo še eno potiskanje z elementom 20, zaradi česar je zgornji del sklada zdaj usmerjen na 20. To stanje je tretja slika.

Zdaj na zadnji sliki izvedemo operacijo pop (). Kot rezultat operacije pop se element, usmerjen na vrh sklada, odstrani iz sklada. Na sliki torej vidimo, da je element 20 odstranjen iz sklada. Tako zgornji del sklada zdaj kaže na 10.

Na ta način lahko zlahka razberemo pristop LIFO, ki ga uporablja stack.

Izvajanje

# 1) Uporaba nizov

Sledi izvedba sklada C ++ z uporabo nizov:

#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<

Izhod:

Potiskanje sklada

dva

4.

6.

Stack Pop:

6.

4.

dva

Na izhodu lahko vidimo, da so elementi v enem vrstnem redu potisnjeni v sklad in v obratnem vrstnem redu izpuščeni iz sklada. To prikazuje pristop LIFO (zadnji vstop, prvi izhod) za sklad.

Za zgornjo izvedbo niza nizov lahko sklepamo, da je to zelo enostavno izvesti, saj ni vključenih nobenih kazalcev. Toda hkrati je velikost sklada statična in sklad ne more dinamično rasti ali krčiti.

Nato bomo sklad izvedli z uporabo nizov v programskem jeziku 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()); } } }

Izhod:

Potiskanje sklada:

1.

3.

5.

Stack Pop:

5.

3.

1.

Logika izvajanja je enaka kot pri izvedbi C ++. Rezultat prikazuje tehniko LIFO za potiskanje in pojavljanje elementov v / iz sklada.

Kot je že bilo navedeno, je izvedba skladov z nizi najpreprostejša izvedba, vendar je statične narave, saj sklada ne moremo dinamično rasti ali krčiti.

# 2) Uporaba povezanega seznama

Nato izvajamo operacije skladov z uporabo povezanega seznama v C ++ in Java. Najprej bomo prikazali izvedbo 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:'<

Izhod:

Potiskanje sklada:

100

200

300

Zgornji element je 300

Stack Pop:

300

200

100

Zgornji element je -1

Nato z uporabo povezanega seznama predstavimo Java izvedbo sklada.

testni primeri v primerih testiranja programske opreme
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()); } }

Izhod:

Potiskanje sklada:

100

200

300

Zgornji element je 300

Stack Pop:

300

200

100

Sklad je prazen

Zgornji element je -2147483648

Pravkar smo videli izvedbe C ++ in Java za sklad, ki uporablja povezane sezname. Vsak vnos sklada predstavljamo kot vozlišče povezanega seznama. Najpomembnejša prednost te izvedbe je, da je dinamična. To pomeni, da lahko povečamo ali zmanjšamo velikost skladov v skladu z našimi zahtevami.

To je za razliko od primera izvajanja skladov z uporabo nizov, v katerih moramo velikost predhodno navesti in je ne moremo dinamično spremeniti.

Naloga pri tej izvedbi je v tem, da, ko povsod uporabljamo kazalce, zavzame malo preveč prostora v primerjavi z izvajanjem matrike.

Aplikacije Stacka

Pogovorimo se o nekaterih aplikacijah strukture podatkovnega sklada. Struktura podatkovnega sklada se uporablja v številnih aplikacijah pri programiranju programske opreme, predvsem zaradi enostavnosti in enostavnosti izvedbe.

Spodaj bomo na kratko opisali nekaj aplikacij sklada:

# 1) Infix To Postfix Expressions

Vsak splošen aritmetični izraz je oblike operand1 OP operand 2 .

Glede na položaj operaterja OP imamo naslednje vrste izrazov:

  • Infix - Splošna oblika izraza infix je „ operand1 OP operand 2 '. To je osnovna oblika izraza in jo v matematiki ves čas uporabljamo.
  • Predpona - Ko je operator pred operandi, je to izraz predpone. Splošna oblika izraza infix je „ OP operand1 operand2 '.
  • Postfix - V izrazih postfix operandi najprej zapišejo operande, nato pa operator. Ima obliko 'operand1 operand2 OP'.

Razmislite o izrazu 'a + b * c ' . Prevajalnik skenira izraz od leve proti desni ali od desne proti levi. Skrb za prednost operatorja in asociativnost bo najprej skeniral izraz, da bo ovrednotil izraz b * c. Nato bo moral spet pregledati izraz, da bo rezultat b * c dodal v a.

Ko izrazi postajajo vedno bolj zapleteni, postane tak način vedno znova skeniranja izraza neučinkovit.

Da bi premagali to neučinkovitost, izraz pretvorimo v postfix ali predpono, tako da jih je mogoče enostavno ovrednotiti s pomočjo podatkovne strukture skladov.

# 2) Razčlenjevanje / vrednotenje izraza

S pomočjo sklada lahko izvedemo tudi dejansko oceno izraza. Pri tem se izraz optično prebere od leve proti desni in operande potisne na sklad.

Kadarkoli naletimo na operaterja, se izkažejo operandi in operacija se izvede. Rezultat operacije je spet potisnjen v sklad. Na ta način je izraz ovrednoten z uporabo sklada, končni rezultat izraza pa je ponavadi trenutni vrh sklada.

# 3) Prehodi dreves

Drevesno podatkovno strukturo je mogoče obiskati tako, da vsako vozlišče obišče na več načinov in odvisno od tega, kdaj smo obiskali korensko vozlišče, ki ga imamo.

  • prehod inOrder
  • preorder za preorder
  • prehod postOrder

Za učinkovito prečkanje drevesa uporabljamo strukturo podatkov sklada, da potisnemo vmesna vozlišča v sklad, tako da ohranjamo vrstni red prečkanja.

# 4) Algoritmi za razvrščanje

Algoritme za razvrščanje, kot je hitro sortiranje, lahko z uporabo struktur podatkovnih skladov naredimo učinkovitejše.

# 5) Hanojski stolpi

To je klasična težava, ki vključuje n števila diskov in tri stolpe, težava pa je premikanje diskov z enega stolpa na drugega, tretji stolp pa je vmesni.

Te težave je mogoče učinkovito rešiti s pomočjo sklada, ko potisnemo diske, ki jih je treba premakniti v sklad, saj sklad v osnovi deluje kot stolp, ki se uporablja za premikanje diskov.

Zaključek

Sklop je najpreprostejša podatkovna struktura in jo je lažje implementirati kot program. Uporabil je pristop LIFO (zadnji vhod, prvi izhod), kar pomeni, da je zadnji vneseni element tisti, ki se najprej odstrani. To pa zato, ker sklad uporablja samo en konec za dodajanje (potiskanje) in odstranjevanje (pop) elementov.

Struktura podatkovnega sklada ima veliko uporab pri programiranju programske opreme. Med njimi najbolj izstopajo ocene izražanja. Vrednotenje izraza vključuje tudi pretvorbo izraza iz infix v postfix ali predpono. Vključuje tudi vrednotenje izraza, da dobimo končni rezultat.

V tej vadnici smo videli ilustracijo in izvedbo sklada ter njegove različne operacije.

V naši prihajajoči vadnici bomo podrobno spoznali strukturo podatkov čakalne vrste.

=> Obiščite tukaj za celoten tečaj strokovnjakov za C ++.

Priporočeno branje

^