Gegevensstructuur stapelen is een lineaire datastructuur dat volgt LIFO-principe (Last In First Out). , dus het laatst ingevoegde element is het eerste dat eruit springt. In dit artikel behandelen we alle basisprincipes van Stack, Operations on Stack, de implementatie ervan, de voordelen en nadelen die u zullen helpen alle problemen op basis van Stack op te lossen.

Inhoudsopgave

• Wat is de stapelgegevensstructuur?
• Basisbewerkingen op de stapelgegevensstructuur
• isLege bewerking in stapelgegevensstructuur
• Implementatie van Stack Data Structure met behulp van Linked List
• Complexiteitsanalyse van bewerkingen op de stapelgegevensstructuur
• Voordelen van Stack Data Structure
• Nadelen van de stapelgegevensstructuur
• Toepassingen van Stack Data Structure

Wat is de stapelgegevensstructuur?

Stapel is een lineaire datastructuur gebaseerd op LIFO-principe (Last In First Out). waarin het inbrengen van een nieuw element en het verwijderen van een bestaand element plaatsvindt aan hetzelfde uiteinde dat wordt weergegeven als de bovenkant van de stapel.

Om de stapel te implementeren, is het nodig om de aanwijzer naar de bovenkant van de stapel , wat het laatste element is dat moet worden ingevoegd omdat we hebben alleen toegang tot de elementen bovenaan de stapel.

Vertegenwoordiging van de stapelgegevensstructuur:

De stapel volgt het LIFO-principe (Last In First Out), dus het element dat als laatste wordt ingedrukt, wordt als eerste gepoft.

Stapel met vast formaat : Zoals de naam al doet vermoeden, heeft een stapel met een vaste grootte een vaste grootte en kan deze niet dynamisch groeien of krimpen. Als de stapel vol is en er wordt geprobeerd een element eraan toe te voegen, treedt er een overflow-fout op. Als de stapel leeg is en er wordt geprobeerd een element eruit te verwijderen, treedt er een onderstroomfout op.

Dynamische formaatstapel : Een stapel met dynamische afmetingen kan dynamisch groeien of krimpen. Wanneer de stapel vol is, wordt deze automatisch groter om plaats te bieden aan het nieuwe element, en wanneer de stapel leeg is, wordt deze kleiner. Dit type stapel wordt geïmplementeerd met behulp van een gekoppelde lijst, omdat het formaat van de stapel eenvoudig kan worden aangepast.

Basisbewerkingen op Stack Data structuur :

Om manipulaties in een stapel uit te voeren, zijn er bepaalde bewerkingen aan ons beschikbaar.

met volledige vorm

• duw() om een ​​element in de stapel te plaatsen
• knal() om een ​​element van de stapel te verwijderen
• bovenkant() Geeft het bovenste element van de stapel terug.
• is leeg() retourneert waar als de stapel leeg is, anders onwaar.
• is vol() retourneert true als de stapel vol is, anders false.

Algoritme voor push-bediening:

• Voordat we het element naar de stapel duwen, controleren we of de stapel dat wel is vol .
• Als de stapel vol is (boven == capaciteit-1) , Dan Stapeloverlopen en we kunnen het element niet in de stapel plaatsen.
• Anders verhogen we de waarde van top met 1 (boven = boven + 1) en de nieuwe waarde wordt ingevoegd op toppositie .
• De elementen kunnen in de stapel worden geduwd totdat we de capaciteit van de stapel.

Algoritme voor popbediening:

• Voordat we het element van de stapel halen, controleren we of de stapel dat wel is leeg .
• Als de stapel leeg is (bovenste == -1), dan Stapel onderstromen en we kunnen geen enkel element van de stapel verwijderen.
• Anders slaan we de waarde bovenaan op en verlagen we de waarde van bovenaan met 1 (boven = boven – 1) en retourneer de opgeslagen topwaarde.

Algoritme voor topbediening:

• Voordat we het bovenste element van de stapel terugplaatsen, controleren we of de stapel leeg is.
• Als de stapel leeg is (boven == -1), printen we eenvoudigweg Stapel is leeg.
• Anders retourneren we het element dat is opgeslagen op index = bovenaan .

Algoritme voor isEmpty-bewerking :

• Controleer de waarde van bovenkant op stapel.
• Als (boven == -1) , dan is de stapel leeg dus terug WAAR .
• Anders is de stapel niet leeg, dus retour vals .

Algoritme voor isvolledige werking:

• Controleer de waarde van bovenkant op stapel.
• Als (boven == capaciteit-1), dan is de stapel vol dus terug WAAR .
• Anders is de stapel niet vol, dus retourneer vals .

Implementatie van Stapel Data structuur :

De basisbewerkingen die op een stapel kunnen worden uitgevoerd, zijn onder meer push, pop en peek. Er zijn twee manieren om een ​​stapel te implementeren:

• Array gebruiken
• Gekoppelde lijst gebruiken

In een array-gebaseerde implementatie wordt de push-operatie geïmplementeerd door de index van het bovenste element te verhogen en het nieuwe element op die index op te slaan. De pop-bewerking wordt geïmplementeerd door de waarde terug te geven die is opgeslagen in de topindex en vervolgens de index van het topelement te verlagen.

In een op een gekoppelde lijst gebaseerde implementatie wordt de push-operatie geïmplementeerd door een nieuw knooppunt te creëren met het nieuwe element en de volgende pointer van het huidige bovenste knooppunt naar het nieuwe knooppunt te plaatsen. De pop-operatie wordt geïmplementeerd door de volgende pointer van het huidige bovenste knooppunt naar het volgende knooppunt te zetten en de waarde van het huidige bovenste knooppunt terug te geven.

/* C++-programma om de basisstack te implementeren activiteiten */ #erbij betrekken #erbij betrekken gebruik makend van naamruimte soa; #define MAX 1000 klas Stapel { int bovenkant; openbaar: int A[MAX]; // Maximale stapelgrootte Stapel() { bovenkant = -1; } bool duw(int X); int knal(); int kijkje(); bool is leeg(); }; bool Stapel::duwen(int X) { als (bovenkant >= (MAX - 1)) { uit << 'stack=''overloop'<='' span=''>; opbrengst vals; } anders { A[++bovenkant] = X; uit << X << ' in de stapel geduwdN'; opbrengst WAAR; } } int Stapel::pop() { als (bovenkant < 0) { uit << 'Stapelonderstroom'; opbrengst 0; } anders { int X = A[bovenkant--]; opbrengst X; } } int Stapel::kijkje() { als (bovenkant < 0) { uit << 'Stapel is leeg'; opbrengst 0; } anders { int X = A[bovenkant]; opbrengst X; } } bool Stapel::isLeeg() { opbrengst (bovenkant < 0); } // Stuurprogramma om bovenstaande functies te testen int voornaamst() { klas Stapel S; S.duw(10); S.duw(twintig); S.duw(30); uit << S.knal() << ' Van de stapel gepluktN'; //print het bovenste element van de stapel na het knallen uit << 'Topelement is: ' << S.kijkje() << eindl; //print alle elementen in stapel: uit <<'Elementen aanwezig in stapel: '; terwijl(!S.is leeg()) { // druk het bovenste element in de stapel af uit << S.kijkje() <<''; // verwijder het bovenste element in de stapel S.knal(); } opbrengst 0; } //Code is aangepast door Vinay PandeyC

// 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->capaciteit = capaciteit;  stapel->boven = -1;  stapel->array = (int*)malloc(stapel->capaciteit * groottevan(int));  retourstapel; } // Stapel is vol als top gelijk is aan de laatste index int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Stapel is leeg als top gelijk is aan -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Functie om een ​​item aan de stapel toe te voegen. Het verhoogt de top met 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stapel->array[++stapel->top] = item;  printf('%d naar stapel geduwd
', item); } // Functie om een ​​item uit de stapel te verwijderen. Het verlaagt de top met 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stapel->array[stapel->top--]; } // Functie om de bovenkant van de stapel terug te brengen zonder deze te verwijderen int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stapel->array[stapel->top]; } // Stuurprogramma om bovenstaande functies te testen int main() { struct Stack* stack = createStack(100);  duwen(stapel, 10);  duwen(stapel, 20);  duwen(stapel, 30);  printf('%d uit stapel gehaald
', pop(stapel));  retour 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('Stack Overflow');  retour vals;  } anders { a[++top] = x;  System.out.println(x + 'in stapel geduwd');  retourneer waar;  } } 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--){ Systeem.out.print(' '+ a[i]);  } } } // Stuurprogrammacodeklasse 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() + 'Uit stapel gehaald');  System.out.println('Bovenste element is:' + s.peek());  System.out.print('Elementen aanwezig in stapel:');  sprint();  } } //Deze code is aangepast door 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('Stack Overflow');  retour vals;  } anders { t+=1;  a[t] = x;    console.log(x + ' in stapel geduwd ');  retourneer waar;  } } functie 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; ik--) { console.log(' ' + a[i]);  } } druk(10);  duwen(20);  duwen(30);  console.log(pop() + 'Uit stapel gehaald');  console.log(' Bovenste element is :' + peek());  console.log(' Elementen aanwezig in stapel: ');  afdrukken(); // Deze code is bijgedragen door Rajput-Ji>

Uitvoer

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>

Voordelen van array-implementatie:

• Eenvoudig te implementeren.
• Het geheugen wordt opgeslagen omdat er geen verwijzingen bij betrokken zijn.

Nadelen van array-implementatie:

• Het is niet dynamisch, dat wil zeggen dat het niet groeit of krimpt, afhankelijk van de behoeften tijdens runtime. [Maar in het geval van arrays van dynamische grootte zoals vector in C++, list in Python, ArrayList in Java, kunnen stapels ook groeien en krimpen met array-implementatie].
• De totale grootte van de stapel moet vooraf worden gedefinieerd.

// C++ programma voor gekoppelde lijstimplementatie van stapel #erbij betrekken gebruik makend van naamruimte soa; // Een structuur om een ​​stapel weer te geven klas StackNode { openbaar: int gegevens; StackNode* volgende; }; StackNode* nieuwNode(int gegevens) { StackNode* stapelNode = nieuw StackNode(); stapelNode->gegevens = gegevens; stapelNode->volgende = NUL; opbrengst stapelNode; } int is leeg(StackNode* wortel) { opbrengst !wortel; } leegte duw(StackNode** wortel, int gegevens) { StackNode* stapelNode = nieuwNode(gegevens); stapelNode->volgende = *wortel; *wortel = stapelNode; uit << gegevens << 'push='' naar='' stapel<='' span=''>N'; } int knal(StackNode** wortel) { als (is leeg(*wortel)) opbrengst INT_MIN; StackNode* temperatuur = *wortel; *wortel = (*wortel)->volgende; int knalde = temperatuur->gegevens; vrij(temperatuur); opbrengst knalde; } int kijkje(StackNode* wortel) { als (is leeg(wortel)) opbrengst INT_MIN; opbrengst wortel->gegevens; } // Stuurprogrammacode int voornaamst() { StackNode* wortel = NUL; duw(&wortel, 10); duw(&wortel, twintig); duw(&wortel, 30); uit << knal(&wortel) << ' knalde van de stapelN'; uit << 'Topelement is' << kijkje(wortel) << eindl; uit <<'Elementen aanwezig in stapel: '; //print alle elementen in stapel: terwijl(!is leeg(wortel)) { // druk het bovenste element in de stapel af uit << kijkje(wortel) <<''; // verwijder het bovenste element in de stapel knal(&wortel); } opbrengst 0; } // Dit is code die is bijgedragen door rathbhupendraC

// 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->gegevens = gegevens;  stackNode->volgende = NULL;  retour stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->volgende = *root;  *root = stackNode;  printf('%d gepusht om te stapelen
', data); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *root = (*root)->volgende;  int popped = temp->data;  gratis(temp);  terugkeer knalde; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  retourneer root->gegevens; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d uit stapel gehaald
', pop(&root));  printf('Topelement is %d
', peek(root));  retour 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

>

Uitvoer

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>

Voordelen van de implementatie van Linked List:

• De gekoppelde lijstimplementatie van een stapel kan groeien en krimpen afhankelijk van de behoeften tijdens runtime.
• Het wordt gebruikt in veel virtuele machines zoals JVM.

Nadelen van de implementatie van gekoppelde lijsten:

• Vereist extra geheugen vanwege de betrokkenheid van pointers.
• Willekeurige toegang is niet mogelijk in de stapel.

Complexiteitsanalyse van bewerkingen op de stapelgegevensstructuur:

Voordelen van stapel Data structuur :

• Eenvoud: Stacks vormen een eenvoudige en gemakkelijk te begrijpen datastructuur, waardoor ze geschikt zijn voor een breed scala aan toepassingen.
• Efficiëntie: Push- en pop-bewerkingen op een stapel kunnen in constante tijd worden uitgevoerd (O(1)) , waardoor efficiënte toegang tot gegevens wordt geboden.
• Last-in, first-out (LIFO): Stapels volgen het LIFO-principe en zorgen ervoor dat het laatste element dat aan de stapel wordt toegevoegd, het eerste is dat wordt verwijderd. Dit gedrag is nuttig in veel scenario's, zoals functieaanroepen en expressie-evaluatie.
• Beperkt geheugengebruik: Stapels hoeven alleen de elementen op te slaan die erop zijn geplaatst, waardoor ze geheugenefficiënt zijn in vergelijking met andere datastructuren.

Nadelen van stapel Data structuur :

• Beperkte toegang: Elementen in een stapel zijn alleen vanaf de bovenkant toegankelijk, waardoor het moeilijk is om elementen in het midden van de stapel op te halen of aan te passen.
• Potentieel voor overstroming: Als er meer elementen op een stapel worden geduwd dan er plaats kunnen vinden, treedt er een overflow-fout op, wat resulteert in gegevensverlies.
• Niet geschikt voor willekeurige toegang: Stapel s staan ​​geen willekeurige toegang tot elementen toe, waardoor ze ongeschikt zijn voor toepassingen waarbij toegang tot de elementen in een specifieke volgorde nodig is.
• Beperkte capaciteit: Stapels hebben een vaste capaciteit, wat een beperking kan zijn als het aantal elementen dat moet worden opgeslagen onbekend of zeer variabel is.

Toepassingen van stapelgegevensstructuur:

• Infix naar Postfix /Voorvoegselconversie
• Functies opnieuw uitvoeren en ongedaan maken op veel plaatsen, zoals editors en Photoshop.
• Voorwaartse en achterwaartse functies in webbrowsers
• Bij geheugenbeheer gebruikt elke moderne computer een stapel als primair beheer voor lopende doeleinden. Elk programma dat op een computersysteem draait, heeft zijn eigen geheugentoewijzingen.
• Stack helpt ook bij het implementeren van functieaanroepen op computers. De laatst aangeroepen functie wordt altijd als eerste voltooid.

Gerelateerde artikelen:

• Implementeer een stapel met behulp van een enkelvoudig gekoppelde lijst
• Basisbewerkingen in de stapelgegevensstructuur met implementaties
• Top 50 problemen met de structuur van stapelgegevens die in SDE-interviews zijn gesteld
• Toepassingen, voordelen en nadelen van Stack
  
• Stack voor competitief programmeren