Menu

Stak datastruktur i C ++ med illustration

stack data structure c with illustration

hvordan man åbner SWF-fil på Chrome

Prøv Vores Instrument Til At Fjerne Problemer

Alt hvad du behøver at vide om stack i C ++.

Stack er en grundlæggende datastruktur, der bruges til at gemme elementer på en lineær måde.

Stak følger LIFO (sidste ind, først ud) rækkefølge eller tilgang, hvor operationerne udføres. Dette betyder, at det element, der blev tilføjet sidst til stakken, vil være det første element, der fjernes fra stakken.

=> Besøg her for at se hele C ++ træningsserien for alle.

STAK

Hvad du lærer:

Stak i C ++

En stak svarer til den virkelige stak eller en bunke ting, som vi stabler over hinanden.

Nedenfor er en billedlig gengivelse af Stack.

billedlig gengivelse af stakken

Som vist ovenfor er der en bunke plader stablet oven på hinanden. Hvis vi vil tilføje et andet emne til det, tilføjer vi det øverst i stakken som vist i ovenstående figur (venstre side). Denne operation for at tilføje et element til stakken kaldes “ Skubbe ”.

På højre side har vi vist en modsat handling, dvs. vi fjerner et element fra stakken. Dette gøres også fra samme ende, dvs. toppen af ​​stakken. Denne operation kaldes “ Pop ”.

Som vist i ovenstående figur ser vi, at push og pop udføres fra samme ende. Dette får stakken til at følge LIFO-ordren. Den position eller ende, hvorfra genstandene skubbes ind eller poppes ud til / fra stakken, kaldes “ Øverst på stakken ”.

Oprindeligt, når der ikke er nogen elementer i stakken, er toppen af ​​stakken indstillet til -1. Når vi tilføjer et element til stakken, forøges toppen af ​​stakken med 1, hvilket indikerer, at elementet er tilføjet. I modsætning til dette mindskes toppen af ​​stakken med 1, når en genstand poppes ud af stakken.

Dernæst vil vi se nogle af de grundlæggende operationer i stack-datastrukturen, som vi skal bruge, når vi implementerer stacken.

Grundlæggende funktioner

Følgende er de grundlæggende operationer, der understøttes af stakken.

  • skubbe - Tilføjer eller skubber et element ind i stakken.
  • pop - Fjerner eller springer et element ud af stakken.
  • kigge - Får det øverste element i stakken, men fjerner det ikke.
  • er fuld - Tester, om stakken er fuld.
  • er tom - Tester, om stakken er tom.

Illustration

Stakillustration

Ovenstående illustration viser rækkefølgen af ​​operationer, der udføres på stakken. Oprindeligt er stakken tom. For en tom stak er toppen af ​​stakken indstillet til -1.

Dernæst skubber vi elementet 10 ind i stakken. Vi ser, at toppen af ​​stakken nu peger på element 10.

Dernæst udfører vi en anden skubbehandling med elementet 20, hvorved toppen af ​​stakken nu peger på 20. Denne tilstand er den tredje figur.

Nu i den sidste figur udfører vi en pop () operation. Som et resultat af popoperationen fjernes elementet, der peger på toppen af ​​stakken, fra stakken. Derfor ser vi i figuren, at element 20 fjernes fra stakken. Således viser toppen af ​​stakken nu til 10.

På denne måde kan vi nemt finde ud af LIFO-metoden, der bruges af stack.

Implementering

# 1) Brug af arrays

Følgende er C ++ implementering af stack ved hjælp af arrays:

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

Produktion:

Stakskubben

to

4

6

Stack Pop:

6

4

to

I output kan vi se, at elementerne skubbes ind i stakken i en rækkefølge og poppes ud af stakken i omvendt rækkefølge. Dette viser LIFO (Last in, First out) tilgang til stakken.

Til ovenstående arrayimplementering af stakken kan vi konkludere, at dette er meget let at implementere, da der ikke er nogen henvisninger involveret. Men på samme tid er stakkens størrelse statisk, og stakken kan ikke vokse eller krympe dynamisk.

Dernæst implementerer vi stakken ved hjælp af arrays i Java-programmeringssprog.

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()); } } }

Produktion:

Stakskub:

en

3

5

Stakpop:

5

3

en

Implementeringslogikken er den samme som i C ++ implementering. Outputtet viser LIFO-teknikken til at skubbe ind og poppe ud af elementerne til / fra stakken.

Som allerede nævnt er stakimplementering ved hjælp af arrays den enkleste implementering, men er af statisk karakter, da vi ikke dynamisk kan vokse eller formindske stakken.

# 2) Brug af en sammenkædet liste

Dernæst implementerer vi stakoperationer ved hjælp af en linket liste i både C ++ og Java. Først demonstrerer vi C ++ implementeringen.

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

Produktion:

Stakskub:

100

200

300

Topelementet er 300

Stakpop:

300

200

100

Topelement er -1

Dernæst præsenterer vi Java-implementeringen af ​​stakken ved hjælp af en linket liste.

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()); } }

Produktion:

Stakskub:

100

200

300

Topelementet er 300

Stakpop:

300

200

100

Stakken er tom

Topelement er -2147483648

c ++ udefineret referencefejl

Vi har lige set C ++ og Java-implementeringer til en stak ved hjælp af sammenkædede lister. Vi repræsenterer hver stakpost som en node på den linkede liste. Den vigtigste fordel ved denne implementering er, at den er dynamisk. Dette betyder, at vi kan vokse eller formindske stakkens størrelse i henhold til vores krav.

Dette er i modsætning til tilfældet med stakimplementering ved hjælp af arrays, hvor vi på forhånd skal erklære størrelsen og ikke kan ændre den dynamisk.

Ulempen ved denne implementering er, at når vi bruger pegepinde overalt, tager det lidt for meget plads sammenlignet med arrayimplementering.

Anvendelser af Stack

Lad os diskutere nogle af anvendelserne af stack-datastrukturen. Stakedatastrukturen bruges i en række applikationer i softwareprogrammering, hovedsageligt på grund af dens enkelhed og nem implementering.

Vi vil kort beskrive nogle af applikationerne i stakken nedenfor:

# 1) Infix til Postfix-udtryk

Ethvert generelt aritmetisk udtryk er af formen operand1 OP operand 2 .

Baseret på positionen for operatør OP har vi følgende typer udtryk:

  • Infix - Den generelle form for infix-udtryk er “ operand1 OP operand 2 ”. Dette er den grundlæggende form for udtrykket, og vi bruger hele tiden i matematik.
  • Præfiks - Når en operatør placeres foran operanderne, er det et præfiksudtryk. Den generelle form for infix-udtryk er “ OP operand1 operand2 ”.
  • Postfix - I postfix-udtryk skrives først operander efterfulgt af operatøren. Den har formen “operand1 operand2 OP”.

Overvej udtrykket “a + b * c ' . Compileren scanner udtrykket enten fra venstre til højre eller højre mod venstre. Ved at tage sig af operatorens forrang og associativitet scannes det først udtrykket for at evaluere udtrykket b * c. Derefter bliver det igen nødt til at scanne udtrykket for at tilføje resultatet af b * c til a.

Efterhånden som udtrykkene vokser mere og mere komplekse, bliver denne form for tilgang til igen og igen scanning af udtrykket ineffektiv.

For at overvinde denne ineffektivitet konverterer vi udtrykket til postfix eller præfiks, så de let kan evalueres ved hjælp af en stack-datastruktur.

# 2) Ekspression Parsing / Evaluering

Ved hjælp af stack kan vi også udføre faktisk ekspressionsevaluering. I dette scannes udtrykket fra venstre mod højre, og operander skubbes videre til stakken.

Hver gang en operatør støder på, poppes operander ud, og operationen udføres. Resultatet af operationen skubbes igen ind i stakken. Denne måde, hvorpå udtrykket evalueres ved hjælp af stakken, og det endelige resultat af udtrykket er normalt den aktuelle top af stakken.

# 3) Træovergange

Trædatastrukturen kan krydses for at besøge hver node på mange måder og afhængigt af, hvornår den rodnode, vi har, er besøgt.

  • i Bestil gennemgang
  • forudbestil gennemgang
  • postOrder traversal

For effektivt at krydse træet bruger vi stakdatastruktur for at skubbe mellemliggende noder på stakken, så vi opretholder rækkefølgen af ​​traversal.

# 4) Sorteringsalgoritmer

Sorteringsalgoritmer som quicksort kan gøres mere effektive ved hjælp af stack-datastrukturer.

# 5) Tårne i Hanoi

Dette er et klassisk problem, der involverer n antal diske og tre tårne, og problemet involverer at flytte diske fra et tårn til et andet med det tredje tårn brugt som mellemliggende.

Dette problem kan tackles effektivt ved hjælp af stakken, når vi skubber skiverne, der skal flyttes til stakken, da stakken dybest set fungerer som et tårn, der bruges til at flytte skiverne.

Konklusion

Stakken er den enkleste datastruktur og lettere at implementere som et program. Det brugte LIFO-tilgangen (sidste ind, først ud), hvilket betyder, at elementet, der sidst blev indtastet, er det, der fjernes først. Dette skyldes, at stack kun bruger den ene ende til at tilføje (push) og fjerne (pop) elementer.

Stakens datastruktur har mange anvendelser i softwareprogrammering. Den fremtrædende blandt dem er ekspressionsevalueringer. Ekspressionsevaluering inkluderer også konvertering af udtrykket fra infix til postfix eller præfiks. Det indebærer også evaluering af udtrykket for at producere det endelige resultat.

I denne vejledning har vi set illustrationen og implementeringen af ​​stakken såvel som dens forskellige operationer.

I vores kommende tutorial lærer vi mere om kødatastrukturen i detaljer.

=> Besøg her for det komplette C ++ kursus fra eksperter.

Anbefalet læsning

^