stack data structure c with illustration
salesforce intervjufrågor och svar för erfarna utvecklare
Allt du behöver veta om stack i C ++.
Stack är en grundläggande datastruktur som används för att lagra element på ett linjärt sätt.
Stack följer LIFO (sista in, först ut) ordning eller tillvägagångssätt där operationerna utförs. Detta innebär att det element som läggs till sist i stacken blir det första elementet som tas bort från stacken.
=> Besök här för att se hela C ++ träningsserien för alla.
Vad du kommer att lära dig:
Stack i C ++
En stack liknar den verkliga stacken eller en hög med saker som vi staplar över varandra.
Nedan följer en bildrepresentation av Stack.
Som visas ovan finns en hög med plattor staplade ovanpå varandra. Om vi vill lägga till ytterligare ett objekt till det lägger vi till det högst upp på stacken som visas i figuren ovan (vänster sida). Denna operation för att lägga till ett objekt till stack kallas “ Skjuta på ”.
På höger sida har vi visat en motsatt operation, dvs. vi tar bort ett objekt från stacken. Detta görs också från samma ände, dvs toppen av stacken. Denna operation kallas “ Pop ”.
Som visas i figuren ovan ser vi att push och pop utförs från samma ände. Detta gör att stacken följer LIFO-order. Positionen eller änden från vilken föremålen trycks in eller poppar ut till / från stacken kallas ” Överst på stacken ”.
Inledningsvis, när det inte finns några objekt i stacken, är toppen av stacken inställd på -1. När vi lägger till ett objekt i stacken ökas toppen av stacken med 1 vilket indikerar att objektet har lagts till. Till skillnad från detta minskas stapelns topp med 1 när ett objekt poppar ut ur stacken.
Därefter kommer vi att se några av de grundläggande operationerna i stackdatastrukturen som vi kommer att behöva när vi implementerar stacken.
Grundläggande funktioner
Följande är de grundläggande operationerna som stöds av stacken.
- skjuta på - Lägger till eller skjuter in ett element i stacken.
- pop - Tar bort eller dyker upp ett element ur stacken.
- kika - Hämtar toppelementet i stacken men tar inte bort det.
- är full - Testar om stacken är full.
- är tom - Testar om stacken är tom.
Illustration
Ovanstående illustration visar sekvensen av operationer som utförs på stacken. Inledningsvis är stacken tom. För en tom stack är toppen av stacken inställd på -1.
Därefter skjuter vi in elementet 10 i stacken. Vi ser att toppen av stacken nu pekar på element 10.
Därefter utför vi ytterligare en tryckoperation med elementet 20, varigenom toppen av stacken nu pekar på 20. Detta tillstånd är den tredje figuren.
Nu i den sista figuren utför vi en pop () -operation. Som ett resultat av popoperationen avlägsnas elementet som pekar på toppen av stacken från stacken. Följaktligen ser vi i figuren att elementet 20 tas bort från stapeln. Således pekar toppen på stapeln nu till 10.
På detta sätt kan vi enkelt ta reda på LIFO-metoden som används av stack.
Genomförande
# 1) Använda arrays
Följande är C ++ implementering av stack med 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:
Stack Push
två
4
6
Stackpop:
6
4
två
I utgången kan vi se att elementen skjuts in i stacken i en ordning och poppar ut ur stacken i omvänd ordning. Detta visar LIFO (Last in, First out) -metoden för stacken.
För ovanstående arrayimplementering av stacken kan vi dra slutsatsen att detta är väldigt enkelt att implementera eftersom det inte finns några pekare inblandade. Men samtidigt är stackens storlek statisk och stacken kan inte växa eller krympa dynamiskt.
Därefter implementerar vi stacken med matriser i Java-programmeringsspråk.
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:
Stack Push:
ett
3
5
Stackpop:
5
3
ett
Implementeringslogiken är densamma som i C ++ implementering. Utgången visar LIFO-tekniken för att trycka in och poppa ut från elementen till / från stacken.
Som redan nämnts är stackimplementering med arrays den enklaste implementeringen men är av statisk karaktär eftersom vi inte dynamiskt kan växa eller krympa stacken.
# 2) Använda en länkad lista
Därefter implementerar vi stackoperationer med hjälp av en länkad lista i både C ++ och Java. Först kommer vi att demonstrera 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:
Stack Push:
100
200
300
Toppelementet är 300
Stackpop:
300
200
100
Toppelementet är -1
Därefter presenterar vi Java-implementeringen av stacken med hjälp av en länkad lista.
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:
Stack Push:
100
200
300
Toppelementet är 300
Stackpop:
bästa gratis DVD-rippning programvara windows
300
200
100
Stack är tom
Toppelementet är -2147483648
Vi har just sett C ++ och Java-implementeringar för en stack med länkade listor. Vi representerar varje stackpost som en nod i den länkade listan. Den viktigaste fördelen med denna implementering är att den är dynamisk. Detta innebär att vi kan växa eller krympa stapelstorleken enligt vårt krav.
Detta skiljer sig från fallet med stackimplementering med matriser där vi måste förklara storleken i förväg och inte kan ändra den dynamiskt.
Nackdelen med denna implementering är att när vi använder pekare överallt tar det lite för mycket utrymme jämfört med arrayimplementering.
Tillämpningar av Stack
Låt oss diskutera några av applikationerna för stapeldatastrukturen. Stapeldatastrukturen används i en rad applikationer i programvaruprogrammering främst på grund av dess enkelhet och enkel implementering.
Vi kommer kort att beskriva några av applikationerna i stacken nedan:
# 1) Infix till Postfix-uttryck
Alla allmänna aritmetiska uttryck har formen operand1 OP operand 2 .
Baserat på positionen för operatören OP har vi följande typer av uttryck:
- Infix - Den allmänna formen av infixuttryck är “ operand1 OP operand 2 ”. Detta är den grundläggande formen av uttrycket och vi använder i matematik hela tiden.
- Prefix - När en operatör placeras före operanderna är det ett prefixuttryck. Den allmänna formen av infixuttryck är ” OP operand1 operand2 ”.
- Postfix - I postfix-uttryck skrivs operander först följda av operatören. Den har formen ”operand1 operand2 OP”.
Tänk på uttrycket “a + b * c ' . Kompilatorn skannar uttrycket antingen från vänster till höger eller höger till vänster. Om man tar hand om operatörens företräde och associativitet skannar det först uttrycket för att utvärdera uttrycket b * c. Därefter måste det igen skanna uttrycket för att lägga till resultatet av b * c till a.
När uttrycken växer mer och mer komplex blir denna typ av metod att om och om igen skanna uttrycket ineffektiv.
För att övervinna denna ineffektivitet konverterar vi uttrycket till postfix eller prefix så att de enkelt kan utvärderas med hjälp av en stapeldatastruktur.
# 2) Expression Parsing / Evaluation
Med hjälp av stack kan vi också göra en faktisk utvärdering av uttrycket. I detta skannas uttrycket från vänster till höger och operander trycks vidare till stacken.
Närhelst en operatör stöter på poppar operander ut och operationen utförs. Resultatet av operationen skjuts åter in i stacken. Detta sätt på vilket uttrycket utvärderas med hjälp av stack och slutresultatet av uttrycket är vanligtvis den aktuella toppen av stacken.
# 3) Trädkorsningar
Träddatastrukturen kan passeras för att besöka varje nod på många sätt och beroende på när den rotnod vi har besöks.
- in Order traversal
- förbeställning genomgång
- postOrder traversal
För att effektivt korsa trädet använder vi stapeldatastrukturen för att skjuta mellanliggande noder på stapeln så att vi behåller ordningen för traversal.
# 4) Sorteringsalgoritmer
Sorteringsalgoritmer som quicksort kan effektiviseras med hjälp av stackdatastrukturerna.
# 5) Towers of Hanoi
Detta är ett klassiskt problem som involverar ett antal skivor och tre torn och problemet innebär att skivorna flyttas från ett torn till ett annat med det tredje tornet som mellanliggande.
Detta problem kan hanteras effektivt med hjälp av stacken när vi trycker på skivorna som ska flyttas till stacken eftersom stacken i grunden fungerar som ett torn som används för att flytta skivorna.
Slutsats
Stapeln är den enklaste datastrukturen och lättare att implementera som ett program. Den använde LIFO-metoden (sist in, först ut), vilket betyder att det element som matades in senast är det som tas bort först. Detta beror på att stack endast använder en ände för att lägga till (push) och ta bort (pop) element.
Stapeldatastrukturen har många användningsområden för programvaruprogrammering. Den framstående bland dem är uttrycksvärderingar. Uttrycksutvärdering inkluderar också konvertering av uttrycket från infix till postfix eller prefix. Det innebär också att utvärdera uttrycket för att producera det slutliga resultatet.
I denna handledning har vi sett illustrationen och implementeringen av stacken liksom dess olika operationer.
I vår kommande handledning lär vi oss mer om ködatastrukturen i detalj.
=> Besök här för en komplett C ++ - kurs från experter.
Rekommenderad läsning
- Kodatastruktur i C ++ med illustration
- Cirkulär länkad datastruktur i C ++ med illustration
- Länkad listdatastruktur i C ++ med illustration
- Prioriterad ködatastruktur i C ++ med illustration
- Dubbelt länkad datastruktur i C ++ med illustration
- Introduktion till datastrukturer i C ++
- JMeter-dataparameterisering med användardefinierade variabler
- 10+ bästa datainsamlingsverktyg med strategier för datainsamling