Stabel datastruktur er en lineær datastruktur som følger LIFO-prinsippet (sist inn først ut). , så det siste elementet som er satt inn er det første som blir spratt ut. I denne artikkelen vil vi dekke alt det grunnleggende om Stack, Operations on Stack, implementeringen, fordeler, ulemper som vil hjelpe deg med å løse alle problemene basert på Stack.

Innholdsfortegnelse

• Hva er stabeldatastruktur?
• Grunnleggende operasjoner på stabeldatastruktur
• isEmpty-operasjon i stabeldatastruktur
• Implementering av Stack Data Structure ved hjelp av Linked List
• Kompleksitetsanalyse av operasjoner på stabeldatastruktur
• Fordeler med stabeldatastruktur
• Ulemper med stabeldatastruktur
• Anvendelser av stabeldatastruktur

Hva er stabeldatastruktur?

Stable er en lineær datastruktur basert på LIFO (Last In First Out)-prinsippet der innsetting av et nytt element og fjerning av et eksisterende element skjer i samme ende representert som topp av stabelen.

For å implementere stabelen, er det nødvendig å vedlikeholde pekeren til toppen av stabelen , som er det siste elementet som skal settes inn fordi vi kan bare få tilgang til elementene på toppen av stabelen.

Representasjon av stabeldatastruktur:

Stack følger LIFO (Last In First Out)-prinsippet, slik at elementet som skyves sist, sprettes først.

Stabel med fast størrelse : Som navnet antyder, har en stabel med fast størrelse en fast størrelse og kan ikke vokse eller krympe dynamisk. Hvis stabelen er full og det gjøres et forsøk på å legge til et element i den, oppstår det en overløpsfeil. Hvis stabelen er tom og det gjøres et forsøk på å fjerne et element fra den, oppstår det en underflytfeil.

Dynamisk størrelse stabel : En stabel med dynamisk størrelse kan vokse eller krympe dynamisk. Når stabelen er full, øker den automatisk størrelsen for å få plass til det nye elementet, og når stabelen er tom, reduseres størrelsen. Denne typen stabel er implementert ved hjelp av en koblet liste, da det gjør det enkelt å endre størrelse på stabelen.

Grunnleggende operasjoner på stabelen Data struktur :

For å gjøre manipulasjoner i en stabel, er det visse operasjoner gitt til oss.

• trykk() for å sette inn et element i stabelen
• pop() for å fjerne et element fra stabelen
• topp() Returnerer det øverste elementet i stabelen.
• er tom() returnerer true hvis stabelen er tom, ellers usann.
• er full() returnerer sant hvis stabelen er full ellers usann.

Algoritme for push-operasjon:

• Før vi skyver elementet til stabelen, sjekker vi om stabelen er full .
• Hvis stabelen er full (øverst == kapasitet-1) , deretter Stack Overflows og vi kan ikke sette inn elementet i stabelen.
• Ellers øker vi verdien av topp med 1 (topp = topp + 1) og den nye verdien settes inn på topplassering .
• Elementene kan skyves inn i stabelen til vi når kapasitet av stabelen.

Algoritme for popoperasjon:

• Før vi spretter elementet fra stabelen, sjekker vi om stabelen er tømme .
• Hvis stabelen er tom (øverst == -1), så Stack Underflows og vi kan ikke fjerne noe element fra stabelen.
• Ellers lagrer vi verdien øverst, reduserer verdien av topp med 1 (topp = topp – 1) og returner den lagrede toppverdien.

Algoritme for toppoperasjon:

• Før vi returnerer toppelementet fra stabelen, sjekker vi om stabelen er tom.
• Hvis stabelen er tom (øverst == -1), skriver vi bare ut Stabelen er tom.
• Ellers returnerer vi elementet lagret kl indeks = topp .

Algoritme for isEmpty Operation :

• Sjekk for verdien av topp i stabel.
• Hvis (øverst == -1) , så er stabelen tømme så kom tilbake ekte .
• Ellers er ikke stabelen tom, så returner falsk .

Algoritme for isFull Operation:

• Sjekk for verdien av topp i stabel.
• Hvis (øverst == kapasitet-1), da er stabelen full så kom tilbake ekte .
• Ellers er ikke stabelen full, så returner falsk .

Implementering av Stack Data struktur :

De grunnleggende operasjonene som kan utføres på en stabel inkluderer push, pop og peek. Det er to måter å implementere en stack –

• Bruker Array
• Bruker koblet liste

I en array-basert implementering implementeres push-operasjonen ved å øke indeksen til toppelementet og lagre det nye elementet ved den indeksen. Pop-operasjonen implementeres ved å returnere verdien som er lagret i toppindeksen og deretter redusere indeksen til toppelementet.

I en koblet listebasert implementering implementeres push-operasjonen ved å opprette en ny node med det nye elementet og sette neste peker for den nåværende toppnoden til den nye noden. Pop-operasjonen implementeres ved å sette den neste pekeren til den nåværende toppnoden til den neste noden og returnere verdien til den gjeldende toppnoden.

; komme tilbake falsk ; } ellers { en [ ++ topp ] = x ; cout < < x < < ' dyttet inn i stabelen ' ; komme tilbake ekte ; } } int Stack::pop () { hvis ( topp < 0 ) { cout < < 'Stack Underflow' ; komme tilbake 0 ; } ellers { int x = en [ topp -- ]; komme tilbake x ; } } int Stack::kikke () { hvis ( topp < 0 ) { cout < < 'Stakken er tom' ; komme tilbake 0 ; } ellers { int x = en [ topp ]; komme tilbake x ; } } bool Stabel::er tom () { komme tilbake ( topp < 0 ); } // Driverprogram for å teste funksjonene ovenfor int hoved- () { klasse Stable s ; s . trykk ( 10 ); s . trykk ( tjue ); s . trykk ( 30 ); cout < < s . pop () < < ' Spratt fra stabelen ' ; //skriv ut det øverste elementet i stabelen etter sprett cout < < 'Toppelement er:' < < s . titt () < < endl ; //skriv ut alle elementene i stabelen: cout < < 'Elementer tilstede i stabel :' ; samtidig som ( ! s . er tom ()) { // print toppelement i stabel cout < < s . titt () < < ' ' ; // fjern toppelementet i stabelen s . pop (); } komme tilbake 0 ; } //Koden er endret av Vinay Pandey C

// C program for array implementation of stack #include  #include  #include  // A structure to represent a stack struct Stack {  int top;  unsigned capacity;  int* array; }; // function to create a stack of given capacity. It initializes size of // stack as 0 struct Stack* createStack(unsigned capacity) {  struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));  stack->kapasitet = kapasitet;  stack->top = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  retur stabelen; } // Stack er full når toppen er lik siste indeks int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Stack er tom når toppen er lik -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funksjon for å legge til et element i stabelen. Den øker toppen med 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = element;  printf('%d presset til stabel
', element); } // Funksjon for å fjerne et element fra stabelen. Den reduserer toppen med 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // Funksjon for å returnere toppen fra stabelen uten å fjerne den int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top]; } // Driverprogram for å teste funksjonene ovenfor int main() { struct Stack* stack = createStack(100);  push(stabel, 10);  push(stabel, 20);  push(stabel, 30);  printf('%d spratt fra stabel
', pop(stabel));  returner 0; } 

Java

/* Java program to implement basic stack operations */ class Stack {  static final int MAX = 1000;  int top;  int a[] = new int[MAX]; // Maximum size of Stack  boolean isEmpty()  {  return (top  < 0);  }  Stack()  {  top = -1;  }  boolean push(int x)  {  if (top>= (MAX - 1)) { System.out.println('Stakkoverflyt');  returner falsk;  } annet { a[++topp] = x;  System.out.println(x + ' dyttet inn i stabel');  return true;  } } int pop() { if (top < 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top--];  return x;  }  }  int peek()  {  if (top  < 0) {  System.out.println('Stack Underflow');  return 0;  }  else {  int x = a[top];  return x;  }  }    void print(){  for(int i = top;i>-1;i--){ System.out.print(' '+ a[i]);  } } } // Driverkodeklasse Main { public static void main(String args[]) { Stack s = new Stack();  s.push(10);  s.push(20);  s.push(30);  System.out.println(s.pop() + ' Spratt fra stabel');  System.out.println('Toppelementet er :' + s.peek());  System.out.print('Elementer tilstede i stabelen :');  s.print();  } } //Denne koden er modifisert av Vinay Pandey 

Python

# Python program for implementation of stack # import maxsize from sys module  # Used to return -infinite when stack is empty from sys import maxsize # Function to create a stack. It initializes size of stack as 0 def createStack(): stack = [] return stack # Stack is empty when stack size is 0 def isEmpty(stack): return len(stack) == 0 # Function to add an item to stack. It increases size by 1 def push(stack, item): stack.append(item) print(item + ' pushed to stack ') # Function to remove an item from stack. It decreases size by 1 def pop(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack.pop() # Function to return the top from stack without removing it def peek(stack): if (isEmpty(stack)): return str(-maxsize -1) # return minus infinite return stack[len(stack) - 1] # Driver program to test above functions  stack = createStack() push(stack, str(10)) push(stack, str(20)) push(stack, str(30)) print(pop(stack) + ' popped from stack') 

C#

// C# program to implement basic stack // operations using System; namespace ImplementStack { class Stack {  private int[] ele;  private int top;  private int max;  public Stack(int size)  {  ele = new int[size]; // Maximum size of Stack  top = -1;  max = size;  }  public void push(int item)  {  if (top == max - 1) {  Console.WriteLine('Stack Overflow');  return;  }  else {  ele[++top] = item;  }  }  public int pop()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top--];  }  }  public int peek()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return -1;  }  else {  Console.WriteLine('{0} popped from stack ',  ele[top]);  return ele[top];  }  }  public void printStack()  {  if (top == -1) {  Console.WriteLine('Stack is Empty');  return;  }  else {  for (int i = 0; i  <= top; i++) {  Console.WriteLine('{0} pushed into stack',  ele[i]);  }  }  } } // Driver program to test above functions class Program {  static void Main()  {  Stack p = new Stack(5);  p.push(10);  p.push(20);  p.push(30);  p.printStack();  p.pop();  } } } 

Javascript

/* javascript program to implement basic stack operations  */  var t = -1;  var MAX = 1000;  var a = Array(MAX).fill(0); // Maximum size of Stack  function isEmpty() {  return (t  < 0);  }  function push(x) {  if (t>= (MAX - 1)) { console.log('Stakkoverflyt');  returner falsk;  } annet { t+=1;  a[t] = x;    console.log(x + ' dyttet inn i stabelen ');  return true;  } } funksjon pop() { if (t < 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  t-=1;  return x;  }  }  function peek() {  if (t  < 0) {  console.log('Stack Underflow');  return 0;  } else {  var x = a[t];  return x;  }  }  function print() {  for (i = t; i>-1; i--) { console.log(' ' + a[i]);  } } push(10);  push(20);  push(30);  console.log(pop() + ' Spratt fra stabelen');  console.log(' Toppelement er :' + kikk());  console.log(' Elementer til stede i stabelen: ');  skrive ut(); // Denne koden er bidratt av Rajput-Ji 

Produksjon

10 pushed into stack 20 pushed into stack 30 pushed into stack 30 Popped from stack Top element is : 20 Elements present in stack : 20 10 

Fordeler med Array-implementering:

• Enkel å implementere.
• Minnet lagres da pekere ikke er involvert.

Ulemper med Array-implementering:

• Den er ikke dynamisk, dvs. den vokser og krymper ikke avhengig av behov under kjøring. [Men i tilfelle av dynamisk størrelse arrays som vektor i C++, liste i Python, ArrayList i Java, kan stabler vokse og krympe med array-implementering også].
• Den totale størrelsen på stabelen må være definert på forhånd.

' ; } int pop ( StackNode ** rot ) { hvis ( er tom ( * rot )) komme tilbake INT_MIN ; StackNode * temp = * rot ; * rot = ( * rot ) -> neste ; int spratt = temp -> data ; gratis ( temp ); komme tilbake spratt ; } int titt ( StackNode * rot ) { hvis ( er tom ( rot )) komme tilbake INT_MIN ; komme tilbake rot -> data ; } // Driverkode int hoved- () { StackNode * rot = NULL ; trykk ( & rot , 10 ); trykk ( & rot , tjue ); trykk ( & rot , 30 ); cout < < pop ( & rot ) < < ' spratt fra stabelen ' ; cout < < 'Toppelement er' < < titt ( rot ) < < endl ; cout < < 'Elementer tilstede i stabel :' ; //skriv ut alle elementene i stabelen: samtidig som ( ! er tom ( rot )) { // print toppelement i stabel cout < < titt ( rot ) < < ' ' ; // fjern toppelementet i stabelen pop ( & rot ); } komme tilbake 0 ; } // Dette er koden er bidratt av rathbhupendra C

// C program for linked list implementation of stack #include  #include  #include  // A structure to represent a stack struct StackNode {  int data;  struct StackNode* next; }; struct StackNode* newNode(int data) {  struct StackNode* stackNode =   (struct StackNode*)  malloc(sizeof(struct StackNode));  stackNode->data = data;  stackNode->neste = NULL;  return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** rot, int data) { struct StackNode* stackNode = newNode(data);  stackNode->neste = *root;  *root = stackNode;  printf('%d presset til stabel
', data); } int pop(struct StackNode** rot) { if (ertom(*root)) returner INT_MIN;  struct StackNode* temp = *root;  *root = (*root)->neste;  int popped = temp->data;  gratis(temp);  retur poppet; } int peek(struct StackNode* root) { if (erEmpty(root)) return INT_MIN;  returner root->data; } int main() { struct StackNode* rot = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d spratt fra stabelen
', pop(&root));  printf('Toppelementet er %d
', kikk(root));  returner 0; } 

Java

// Java Code for Linked List Implementation public class StackAsLinkedList {  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 data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  System.out.println(data + ' pushed to stack');  }  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;  }  }  // Driver code  public static void main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());    sll.push(10);  sll.push(20);  sll.push(30);  System.out.println(sll.pop()  + ' popped from stack');  System.out.println('Top element is ' + sll.peek());  } } 

Python

# Python program for linked list implementation of stack # Class to represent a node class StackNode: # Constructor to initialize a node def __init__(self, data): self.data = data self.next = None class Stack: # Constructor to initialize the root of linked list def __init__(self): self.root = None def isEmpty(self): return True if self.root is None else False def push(self, data): newNode = StackNode(data) newNode.next = self.root self.root = newNode print ('% d pushed to stack' % (data)) def pop(self): if (self.isEmpty()): return float('-inf') temp = self.root self.root = self.root.next popped = temp.data return popped def peek(self): if self.isEmpty(): return float('-inf') return self.root.data # Driver code stack = Stack() stack.push(10) stack.push(20) stack.push(30) print ('% d popped from stack' % (stack.pop())) print ('Top element is % d ' % (stack.peek())) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) 

C#

// C# Code for Linked List Implementation using System; public class StackAsLinkedList {  StackNode root;  public class StackNode {  public int data;  public StackNode next;  public StackNode(int data) { this.data = data; }  }  public bool isEmpty()  {  if (root == null) {  return true;  }  else  return false;  }  public void push(int data)  {  StackNode newNode = new StackNode(data);  if (root == null) {  root = newNode;  }  else {  StackNode temp = root;  root = newNode;  newNode.next = temp;  }  Console.WriteLine(data + ' pushed to stack');  }  public int pop()  {  int popped = int.MinValue;  if (root == null) {  Console.WriteLine('Stack is Empty');  }  else {  popped = root.data;  root = root.next;  }  return popped;  }  public int peek()  {  if (root == null) {  Console.WriteLine('Stack is empty');  return int.MinValue;  }  else {  return root.data;  }  }  // Driver code  public static void Main(String[] args)  {  StackAsLinkedList sll = new StackAsLinkedList();  sll.push(10);  sll.push(20);  sll.push(30);  Console.WriteLine(sll.pop() + ' popped from stack');  Console.WriteLine('Top element is ' + sll.peek());  } } /* This code contributed by PrinciRaj1992 */ 

Javascript

Produksjon

10 pushed to stack 20 pushed to stack 30 pushed to stack 30 popped from stack Top element is 20 Elements present in stack : 20 10 

Fordeler med implementering av Linked List:

• Den koblede listeimplementeringen av en stabel kan vokse og krympe i henhold til behovene ved kjøring.
• Den brukes i mange virtuelle maskiner som JVM.

Ulemper med implementering av koblet liste:

• Krever ekstra minne på grunn av involvering av pekere.
• Tilfeldig tilgang er ikke mulig i stabelen.

Kompleksitetsanalyse av operasjoner på stabeldatastruktur:

Fordeler med Stack Data struktur :

• Enkelhet: Stabler er en enkel og lettfattelig datastruktur, noe som gjør dem egnet for et bredt spekter av applikasjoner.
• Effektivitet: Push og pop-operasjoner på en stabel kan utføres i konstant tid (O(1)) , gir effektiv tilgang til data.
• Sist inn, først ut (LIFO): Stabler følger LIFO-prinsippet, og sikrer at det siste elementet som legges til stabelen er det første som fjernes. Denne virkemåten er nyttig i mange scenarier, for eksempel funksjonskall og uttrykksevaluering.
• Begrenset minnebruk: Stabler trenger bare å lagre elementene som er skjøvet på dem, noe som gjør dem minneeffektive sammenlignet med andre datastrukturer.

Ulemper med Stack Data struktur :

• Begrenset tilgang: Elementer i en stabel kan bare nås fra toppen, noe som gjør det vanskelig å hente eller endre elementer i midten av stabelen.
• Potensial for overløp: Hvis flere elementer skyves på en stabel enn den kan holde, vil det oppstå en overløpsfeil som resulterer i tap av data.
• Ikke egnet for tilfeldig tilgang: Stable s tillater ikke tilfeldig tilgang til elementer, noe som gjør dem uegnet for applikasjoner der elementer må få tilgang til i en bestemt rekkefølge.
• Begrenset kapasitet: Stabler har en fast kapasitet, noe som kan være en begrensning dersom antall elementer som må lagres er ukjent eller svært varierende.

Anvendelser av stabeldatastruktur:

• Infiks til Postfix /Prefikskonvertering
• Gjenopprett funksjoner mange steder som redaktører, photoshop.
• Forover- og bakoverfunksjoner i nettlesere
• I minneadministrasjon bruker enhver moderne datamaskin en stabel som den primære administrasjonen for et løpende formål. Hvert program som kjører i et datasystem har sine egne minnetildelinger.
• Stack hjelper også med å implementere funksjonskall på datamaskiner. Den sist kalte funksjonen fullføres alltid først.

Relaterte artikler:

• Implementer en stabel ved å bruke enkeltlenket liste
• Grunnleggende operasjoner i stabeldatastruktur med implementeringer
• Topp 50 problemer med stabeldatastruktur spurt i SDE-intervjuer
• Bruksområder, fordeler og ulemper med Stack
  
• Stabel for konkurransedyktig programmering