stack data structure c with illustration
što je dobar davatelj usluga e-pošte
Sve što trebate znati o slogu u C ++-u.
Stog je temeljna struktura podataka koja se koristi za linearno pohranjivanje elemenata.
Slijedi stog LIFO (zadnji ulaz, prvi izlaz) redoslijed ili pristup u kojem se izvode operacije. To znači da će element koji je zadnji dodan u stog biti prvi element koji se uklanja iz stoga.
=> Posjetite ovdje da biste pogledali cijelu seriju C ++ treninga za sve.
Što ćete naučiti:
Složite u C ++
Stog je sličan stogu iz stvarnog života ili hrpi stvari koje slažemo jednu iznad druge.
Dolje je slikoviti prikaz Stacka.
Kao što je gore prikazano, postoji hrpa ploča naslaganih jedna na drugu. Ako mu želimo dodati još jednu stavku, tada je dodajemo na vrh stoga kako je prikazano na gornjoj slici (lijeva strana). Ova operacija dodavanja stavke u stog naziva se “ Gurnuti '.
S desne strane prikazali smo suprotnu operaciju, tj. Uklanjamo stavku iz hrpe. To se također radi s istog kraja, tj. Vrha stoga. Ova se operacija naziva „ Pop '.
Kao što je prikazano na gornjoj slici, vidimo da se guranje i iskakanje izvodi s istog kraja. To čini da stog slijedi LIFO red. Položaj ili kraj s kojeg se predmeti ubacuju ili iskaču u / iz hrpe naziva se „ Vrh hrpe '.
U početku, kada u hrpi nema predmeta, vrh stoga postavljen je na -1. Kad stavku dodamo stavku, vrh snopa povećava se za 1 što znači da je stavka dodana. Suprotno tome, vrh stoga smanjuje se za 1 kad se predmet iskoči iz stoga.
Dalje, vidjet ćemo neke od osnovnih operacija strukture podataka steka koje će nam trebati tijekom implementacije stoga.
Osnovne operacije
Slijede osnovne operacije koje podržava stog.
- gurati - Dodaje ili gura element u hrpu.
- pop - Uklanja ili iskače element iz gomile.
- zaviriti - Dobiva gornji element hrpe, ali ga ne uklanja.
- puno je - Ispituje je li stog pun.
- prazno je - Testira je li stog prazan.
Ilustracija
Gornja ilustracija prikazuje slijed operacija koje se izvode na stogu. U početku je stog prazan. Za prazan stog, vrh stoga postavljen je na -1.
Dalje, gurnemo element 10 u stog. Vidimo da vrh stoga sada pokazuje na element 10.
Zatim izvodimo još jednu operaciju potiskivanja s elementom 20, što rezultira time da vrh stoga sada pokazuje na 20. Ovo je stanje treća slika.
Sada na posljednjoj slici izvodimo pop () operaciju. Kao rezultat operacije pop, element usmjeren na vrh stoga uklanja se iz stoga. Stoga na slici vidimo da je element 20 uklonjen iz hrpe. Stoga vrh stoga sada pokazuje na 10.
Na taj način lako možemo uočiti LIFO pristup koji koristi stek.
Provedba
# 1) Korištenje nizova
Slijedi C ++ implementacija stoga pomoću nizova:
#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< Izlaz:
Stack push
dva
4
6
Stack pop:
6
4
dva
U izlazu možemo vidjeti da se elementi guraju u stog u jednom redoslijedu i iskaču iz stoga obrnutim redoslijedom. Ovo pokazuje LIFO (Last in, First out) pristup stogu.
Za gornju implementaciju niza niza možemo zaključiti da je to vrlo lako implementirati jer nisu uključeni pokazivači. Ali istodobno, veličina stoga je statična i stog ne može dinamički rasti ili se smanjivati.
Dalje, stog ćemo implementirati pomoću nizova u programskom 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()); } } } Izlaz:
Stack push:
jedan
3
5
Stack Pop:
5
3
jedan
Logika implementacije je ista kao u implementaciji C ++. Izlaz prikazuje LIFO tehniku guranja i iskakanja elemenata u / iz hrpe.
Kao što je već rečeno, implementacija stoga pomoću nizova je najjednostavnija implementacija, ali je statičke prirode jer ne možemo dinamički povećati ili smanjiti stog.
# 2) Korištenje povezanog popisa
Dalje, implementiramo operacije slaganja koristeći povezani popis i na C ++ i na Javi. Prvo ćemo pokazati implementaciju 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:'< Izlaz:
Stack push:
100
200
300
Gornji element je 300
Stack Pop:
300
200
100
Gornji element je -1
Dalje, predstavljamo Java implementaciju stoga pomoću povezanog popisa.
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()); } } Izlaz:
Stack push:
100
200
300
Gornji element je 300
Stack Pop:
300
200
100
kako mogu igrati swf datoteke
Stog je prazan
Gornji element je -2147483648
Upravo smo vidjeli implementacije C ++ i Jave za stog pomoću povezanih popisa. Svaki unos stoga predstavljamo kao čvor povezanog popisa. Najvažnija prednost ove provedbe je u tome što je dinamična. To znači da možemo povećati ili smanjiti veličinu hrpe prema našem zahtjevu.
To je za razliku od slučaja implementacije steka koji koristi nizove u kojima moramo prethodno deklarirati veličinu i ne možemo je dinamički mijenjati.
Protiv ove implementacije je u tome što, kako svugdje koristimo pokazivače, zauzima malo previše prostora u usporedbi s implementacijom niza.
Primjene Stacka
Razmotrimo neke od primjena strukture podataka steka. Struktura podataka stoga koristi se u nizu aplikacija u programiranju softvera, uglavnom zbog svoje jednostavnosti i jednostavnosti implementacije.
U nastavku ćemo ukratko opisati neke od primjena steka:
# 1) Infiks u postfiksne izraze
Bilo koji opći aritmetički izraz oblika je operand1 OP operand 2 .
Na temelju položaja operatora OP imamo sljedeće vrste izraza:
- Infiks - Opći oblik izraza infiksa je „ operand1 OP operand 2 '. Ovo je osnovni oblik izraza i stalno ga koristimo u matematici.
- Prefiks - Kada je operator postavljen ispred operanda, to je izraz prefiksa. Opći oblik izraza infiksa je „ OP operand1 operand2 '.
- Postfix - U postfiksnim izrazima prvo se pišu operandi, a zatim operator. Ima oblik 'operand1 operand2 OP'.
Razmotrimo izraz „a + b * c ' . Prevoditelj skenira izraz slijeva udesno ili zdesna ulijevo. Pazeći na prednost operatora i asocijativnost, prvo će skenirati izraz kako bi procijenio izraz b * c. Dalje, morat će ponovno skenirati izraz da bi se rezultat b * c dodao u a.
Kako izrazi postaju sve složeniji, takav pristup neprestanog skeniranja izraza postaje neučinkovit.
Da bismo prevladali ovu neučinkovitost, izraz pretvaramo u postfix ili prefiks tako da se mogu lako procijeniti pomoću strukture podataka steka.
# 2) Raščlanjivanje / procjena izraza
Koristeći stog, možemo provesti i stvarnu evaluaciju izraza. U tome se izraz skenira slijeva udesno, a operandi se guraju u hrpu.
Kad god se susretne operator, iskaču se operandi i operacija se izvodi. Rezultat operacije ponovno se gura u hrpu. Na taj način na koji se izraz procjenjuje pomoću steka, a konačni rezultat izraza obično je trenutni vrh stoga.
# 3) Promjene stabala
Struktura podataka stabla može se obići kako bi se na svaki način posjetio svaki čvor i ovisno o tome kada smo posjetili korijenski čvor koji imamo.
- prijelaz inOrder
- preorder prijelaz
- prijelaz postOrder
Da bismo učinkovito prelazili stablo, koristimo strukturu podataka steka kako bismo potisnuli srednje čvorove na stogu tako da održavamo redoslijed prelaska.
# 4) Algoritmi sortiranja
Algoritmi sortiranja poput brzog sortiranja mogu se učiniti učinkovitijim pomoću struktura podataka steka.
# 5) Kule Hanoja
Ovo je klasičan problem koji uključuje n broj diskova i tri tornja, a problem uključuje premještanje diskova s jednog na drugi toranj, pri čemu se treći toranj koristi kao srednji.
Ovaj se problem može učinkovito riješiti pomoću snopa dok guramo diskove koji se premještaju na snop, budući da snop u osnovi djeluje kao toranj koji se koristi za pomicanje diskova.
Zaključak
Stog je najjednostavnija struktura podataka i jednostavnija za implementaciju kao program. Koristio je pristup LIFO (zadnji ulaz, prvi izlaz) što znači da je zadnji uneseni element onaj koji se prvi uklanja. To je zato što stog koristi samo jedan kraj za dodavanje (guranje) i uklanjanje (iskakanje) elemenata.
Struktura podataka steka ima brojne primjene u programiranju softvera. Među njima je istaknuto ocjenjivanje izražavanja. Procjena izraza također uključuje pretvaranje izraza iz infiksa u postfix ili prefiks. Također uključuje vrednovanje izraza kako bi se dobio konačni rezultat.
U ovom uputstvu vidjeli smo ilustraciju i provedbu stoga kao i njegove razne operacije.
U našem predstojećem uputstvu detaljno ćemo naučiti o strukturi podataka o redu.
=> Posjetite ovdje za cjeloviti tečaj stručnjaka za C ++.
Preporučena literatura
- Struktura podataka u redu čekanja u C ++ s ilustracijom
- Kružno povezana struktura podataka popisa na C ++ s ilustracijom
- Povezana struktura podataka popisa na C ++ s ilustracijom
- Struktura podataka prioritetnog reda u C ++ s ilustracijom
- Dvostruko povezana struktura podataka popisa na C ++ s ilustracijom
- Uvod u strukture podataka na C ++
- JMeter parametalizacija podataka korištenjem korisnički definiranih varijabli
- 10+ najboljih alata za prikupljanje podataka sa strategijama prikupljanja podataka