Stapeldatenstruktur ist ein lineare Datenstruktur dass folgt LIFO-Prinzip (Last In First Out). , sodass das zuletzt eingefügte Element als erstes herausspringt. In diesem Artikel behandeln wir alle Grundlagen von Stack, Operationen auf Stack, seine Implementierung sowie Vor- und Nachteile, die Ihnen bei der Lösung aller auf Stack basierenden Probleme helfen werden.

Inhaltsverzeichnis

• Was ist eine Stack-Datenstruktur?
• Grundlegende Operationen zur Stapeldatenstruktur
• isEmpty-Operation in der Stack-Datenstruktur
• Implementierung der Stack-Datenstruktur mithilfe einer verknüpften Liste
• Komplexitätsanalyse von Operationen an der Stapeldatenstruktur
• Vorteile der Stack-Datenstruktur
• Nachteile der Stack-Datenstruktur
• Anwendungen der Stapeldatenstruktur

Was ist eine Stack-Datenstruktur?

Stapel ist ein lineare Datenstruktur bezogen auf LIFO-Prinzip (Last In First Out). bei dem das Einfügen eines neuen Elements und das Entfernen eines vorhandenen Elements am gleichen Ende erfolgt, das als dargestellt wird Spitze des Stapels.

Um den Stack zu implementieren, ist es erforderlich, den zu pflegen Zeiger auf die Oberseite des Stapels , welches das letzte Element ist, das eingefügt wird, weil Wir können nur auf die Elemente oben im Stapel zugreifen.

Darstellung der Stack-Datenstruktur:

Der Stapel folgt dem LIFO-Prinzip (Last In First Out), sodass das zuletzt verschobene Element zuerst entfernt wird.

Stapel mit fester Größe : Wie der Name schon sagt, hat ein Stapel mit fester Größe eine feste Größe und kann nicht dynamisch wachsen oder schrumpfen. Wenn der Stapel voll ist und versucht wird, ihm ein Element hinzuzufügen, tritt ein Überlauffehler auf. Wenn der Stapel leer ist und versucht wird, ein Element daraus zu entfernen, tritt ein Unterlauffehler auf.

Dynamischer Größenstapel : Ein dynamischer Größenstapel kann dynamisch wachsen oder schrumpfen. Wenn der Stapel voll ist, erhöht er automatisch seine Größe, um das neue Element aufzunehmen, und wenn der Stapel leer ist, verringert er seine Größe. Diese Art von Stapel wird mithilfe einer verknüpften Liste implementiert, da sie eine einfache Größenänderung des Stapels ermöglicht.

Grundlegende Operationen auf dem Stapel Datenstruktur :

Um Manipulationen in einem Stapel vorzunehmen, stehen uns bestimmte Operationen zur Verfügung.

Gimp-Export als JPG

• drücken() um ein Element in den Stapel einzufügen
• Pop() um ein Element vom Stapel zu entfernen
• Spitze() Gibt das oberste Element des Stapels zurück.
• ist leer() gibt „true“ zurück, wenn der Stapel leer ist, andernfalls „false“.
• ist voll() gibt „true“ zurück, wenn der Stapel voll ist, andernfalls „false“.

Algorithmus für den Push-Betrieb:

• Bevor wir das Element auf den Stapel schieben, prüfen wir, ob der Stapel vorhanden ist voll .
• Wenn der Stapel voll ist (oben == Kapazität-1) , Dann Stapelüberläufe und wir können das Element nicht in den Stapel einfügen.
• Andernfalls erhöhen wir den Wert von top um 1 (oben = oben + 1) und der neue Wert wird bei eingefügt Spitzenposition .
• Die Elemente können in den Stapel geschoben werden, bis wir den erreichen Kapazität des Stapels.

Algorithmus für die Pop-Operation:

• Bevor wir das Element vom Stapel entfernen, prüfen wir, ob der Stapel vorhanden ist leer .
• Wenn der Stapel leer ist (oben == -1), dann Stapelunterläufe und wir können kein Element vom Stapel entfernen.
• Andernfalls speichern wir den Wert oben und dekrementieren den Wert von oben um 1 (oben = oben – 1) und den gespeicherten Spitzenwert zurückgeben.

Algorithmus für Top-Operation:

• Bevor wir das oberste Element vom Stapel zurückgeben, prüfen wir, ob der Stapel leer ist.
• Wenn der Stapel leer ist (oben == -1), geben wir einfach Stapel ist leer aus.
• Andernfalls geben wir das unter gespeicherte Element zurück Index = oben .

Algorithmus für die isEmpty-Operation :

• Überprüfen Sie den Wert von Spitze im Stapel.
• Wenn (oben == -1) , dann ist der Stapel leer also zurück WAHR .
• Andernfalls ist der Stapel nicht leer, also kehren Sie zurück FALSCH .

Algorithmus für isFull-Betrieb:

• Überprüfen Sie den Wert von Spitze im Stapel.
• Wenn (oben == Kapazität-1), dann ist der Stapel voll also zurück WAHR .
• Andernfalls ist der Stapel nicht voll, also kehren Sie zurück FALSCH .

Implementierung von Stack Datenstruktur :

Zu den grundlegenden Operationen, die auf einem Stapel ausgeführt werden können, gehören Push, Pop und Peek. Es gibt zwei Möglichkeiten, einen Stack zu implementieren:

• Verwenden von Array
• Verwenden einer verknüpften Liste

In einer Array-basierten Implementierung wird der Push-Vorgang implementiert, indem der Index des obersten Elements erhöht und das neue Element an diesem Index gespeichert wird. Die Pop-Operation wird implementiert, indem der am obersten Index gespeicherte Wert zurückgegeben und dann der Index des obersten Elements dekrementiert wird.

In einer auf verknüpften Listen basierenden Implementierung wird der Push-Vorgang implementiert, indem ein neuer Knoten mit dem neuen Element erstellt und der nächste Zeiger des aktuellen obersten Knotens auf den neuen Knoten gesetzt wird. Die Pop-Operation wird implementiert, indem der nächste Zeiger des aktuellen oberen Knotens auf den nächsten Knoten gesetzt und der Wert des aktuellen oberen Knotens zurückgegeben wird.

/* C++-Programm zur Implementierung des Basis-Stacks Operationen */ #enthalten #enthalten verwenden Namensraum std; #define MAX 1000 Klasse Stapel { int Spitze; öffentlich: int A[MAX]; // Maximale Größe des Stapels Stapel() { Spitze = -1; } bool drücken(int X); int Pop(); int spähen(); bool ist leer(); }; bool Stack::push(int X) { Wenn (Spitze >= (MAX - 1)) { cout << ' stack='' Überlauf'<='' span=''>; zurückkehren FALSCH; } anders { A[++Spitze] = X; cout << X << ' in den Stapel geschobenN'; zurückkehren WAHR; } } int Stack::pop() { Wenn (Spitze < 0) { cout << „Stack-Unterlauf“; zurückkehren 0; } anders { int X = A[Spitze--]; zurückkehren X; } } int Stack::peek() { Wenn (Spitze < 0) { cout << „Stapel ist leer“; zurückkehren 0; } anders { int X = A[Spitze]; zurückkehren X; } } bool Stack::isEmpty() { zurückkehren (Spitze < 0); } // Treiberprogramm zum Testen der oben genannten Funktionen int hauptsächlich() { Klasse Stapel S; S.drücken(10); S.drücken(zwanzig); S.drücken(30); cout << S.Pop() << ' Vom Stapel aufgetauchtN'; //Oberstes Element des Stapels nach dem Popup ausgeben cout << 'Oberstes Element ist:' << S.spähen() << endl; //Alle Elemente im Stapel drucken: cout <<'Im Stapel vorhandene Elemente:'; während(!S.ist leer()) { // oberstes Element im Stapel ausgeben cout << S.spähen() <<' '; // oberstes Element im Stapel entfernen S.Pop(); } zurückkehren 0; } //Code wurde von Vinay Pandey geändertC

// 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->Kapazität = Kapazität;  stack->top = -1;  stack->array = (int*)malloc(stack->capacity * sizeof(int));  Rückgabestapel; } // Stack ist voll, wenn top gleich dem letzten Index ist int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; } // Stack ist leer, wenn top gleich -1 ist int isEmpty(struct Stack* stack) { return stack->top == -1; } // Funktion zum Hinzufügen eines Elements zum Stapel. Es erhöht top um 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return;  stack->array[++stack->top] = item;  printf('%d auf Stapel geschoben
', item); } // Funktion zum Entfernen eines Elements vom Stapel. Es verringert sich oben um 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top--]; } // Funktion zum Zurückgeben des oberen Teils vom Stapel, ohne ihn zu entfernen int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN;  return stack->array[stack->top]; } // Treiberprogramm zum Testen der oben genannten Funktionen int main() { struct Stack* stack = createStack(100);  push(stack, 10);  push(stack, 20);  push(stack, 30);  printf('%d vom Stapel gepoppt
', pop(stack));  0 zurückgeben; }>

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');  falsch zurückgeben;  } else { a[++top] = x;  System.out.println(x + 'in den Stapel geschoben');  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]);  } } } // Treibercode-Klasse 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() + ' Vom Stapel entfernt');  System.out.println('Top element is :' + s.peek());  System.out.print('Im Stapel vorhandene Elemente:');  Sprint();  } } //Dieser Code wurde von Vinay Pandey geändert>

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');  falsch zurückgeben;  } else { t+=1;  a[t] = x;    console.log(x + ' in Stapel geschoben ');  return true;  } } function 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() + 'Vom Stapel gepoppt');  console.log(' Das oberste Element ist :' + peek());  console.log(' Im Stapel vorhandene Elemente: ');  drucken(); // Dieser Code wurde von Rajput-Ji beigesteuert>

Ausgabe

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>

Vorteile der Array-Implementierung:

• Einfach umzusetzen.
• Da Zeiger nicht beteiligt sind, wird Speicherplatz gespart.

Nachteile der Array-Implementierung:

• Es ist nicht dynamisch, d. h. es wächst und schrumpft nicht abhängig von den Anforderungen zur Laufzeit. [Aber bei Arrays mit dynamischer Größe wie Vektoren in C++, Listen in Python und ArrayList in Java können Stapel mit der Array-Implementierung auch wachsen und schrumpfen.]
• Die Gesamtgröße des Stapels muss zuvor definiert werden.

// C++-Programm für die Linked-List-Implementierung des Stacks #enthalten verwenden Namensraum std; // Eine Struktur zur Darstellung eines Stapels Klasse StackNode { öffentlich: int Daten; StackNode* nächste; }; StackNode* neuer Knoten(int Daten) { StackNode* stackNode = neu StackNode(); stackNode->Daten = Daten; stackNode->nächste = NULL; zurückkehren stackNode; } int ist leer(StackNode* Wurzel) { zurückkehren !Wurzel; } Leere drücken(StackNode** Wurzel, int Daten) { StackNode* stackNode = neuer Knoten(Daten); stackNode->nächste = *Wurzel; *Wurzel = stackNode; cout << Daten << ' push='' to='' Stapel<='' span=''>N'; } int Pop(StackNode** Wurzel) { Wenn (ist leer(*Wurzel)) zurückkehren INT_MIN; StackNode* Temp = *Wurzel; *Wurzel = (*Wurzel)->nächste; int geknallt = Temp->Daten; frei(Temp); zurückkehren geknallt; } int spähen(StackNode* Wurzel) { Wenn (ist leer(Wurzel)) zurückkehren INT_MIN; zurückkehren Wurzel->Daten; } // Treibercode int hauptsächlich() { StackNode* Wurzel = NULL; drücken(&Wurzel, 10); drücken(&Wurzel, zwanzig); drücken(&Wurzel, 30); cout << Pop(&Wurzel) << ' tauchte vom Stapel aufN'; cout << „Oberstes Element ist“ << spähen(Wurzel) << endl; cout <<'Im Stapel vorhandene Elemente:'; //Alle Elemente im Stapel drucken: während(!ist leer(Wurzel)) { // oberstes Element im Stapel ausgeben cout << spähen(Wurzel) <<' '; // oberstes Element im Stapel entfernen Pop(&Wurzel); } zurückkehren 0; } // Dieser Code wurde von rathbhupendra beigesteuertC

// 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->Daten = Daten;  stackNode->next = NULL;  return stackNode; } int isEmpty(struct StackNode* root) { return !root; } void push(struct StackNode** root, int data) { struct StackNode* stackNode = newNode(data);  stackNode->next = *root;  *root = stackNode;  printf('%d auf Stapel geschoben
', data); } int pop(struct StackNode** root) { if (isEmpty(*root)) return INT_MIN;  struct StackNode* temp = *root;  *root = (*root)->next;  int popped = temp->data;  frei(vorübergehend);  Rückkehr knallte; } int peek(struct StackNode* root) { if (isEmpty(root)) return INT_MIN;  return root->data; } int main() { struct StackNode* root = NULL;  push(&root, 10);  push(&root, 20);  push(&root, 30);  printf('%d vom Stapel gepoppt
', pop(&root));  printf('Oberstes Element ist %d
', peek(root));  0 zurückgeben; }>

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

>

Ausgabe

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>

Vorteile der Implementierung einer verknüpften Liste:

• Die verknüpfte Listenimplementierung eines Stapels kann je nach Bedarf zur Laufzeit wachsen und schrumpfen.
• Es wird in vielen virtuellen Maschinen wie JVM verwendet.

Nachteile der Implementierung einer verknüpften Liste:

• Benötigt aufgrund der Einbeziehung von Zeigern zusätzlichen Speicher.
• Im Stack ist kein wahlfreier Zugriff möglich.

Komplexitätsanalyse von Operationen an der Stapeldatenstruktur:

Vorteile von Stack Datenstruktur :

• Einfachheit: Stacks sind eine einfache und leicht verständliche Datenstruktur, wodurch sie für eine Vielzahl von Anwendungen geeignet sind.
• Effizienz: Push- und Pop-Operationen auf einem Stapel können in konstanter Zeit ausgeführt werden (O(1)) , was einen effizienten Zugriff auf Daten ermöglicht.
• Last-in, First-out (LIFO): Stapel folgen dem LIFO-Prinzip und stellen sicher, dass das letzte dem Stapel hinzugefügte Element das erste ist, das entfernt wird. Dieses Verhalten ist in vielen Szenarios nützlich, beispielsweise bei Funktionsaufrufen und der Ausdrucksauswertung.
• Begrenzte Speichernutzung: Stapel müssen nur die Elemente speichern, die auf sie übertragen wurden, was sie im Vergleich zu anderen Datenstrukturen speichereffizient macht.

Nachteile von Stack Datenstruktur :

• Beschränkter Zugang: Auf Elemente in einem Stapel kann nur von oben zugegriffen werden, was es schwierig macht, Elemente in der Mitte des Stapels abzurufen oder zu ändern.
• Überlaufgefahr: Wenn mehr Elemente auf einen Stapel verschoben werden, als er aufnehmen kann, tritt ein Überlauffehler auf, der zu Datenverlust führt.
• Nicht für Direktzugriff geeignet: Stapel s erlauben keinen wahlfreien Zugriff auf Elemente und eignen sich daher nicht für Anwendungen, bei denen auf Elemente in einer bestimmten Reihenfolge zugegriffen werden muss.
• Beschränkte Kapazität: Stapel haben eine feste Kapazität, was eine Einschränkung darstellen kann, wenn die Anzahl der zu speichernden Elemente unbekannt oder stark schwankend ist.

Anwendungen der Stapeldatenstruktur:

• Infix zu Postfix /Präfixkonvertierung
• Funktionen zum Wiederherstellen und Rückgängigmachen gibt es an vielen Stellen, z. B. in Editoren und Photoshop.
• Vorwärts- und Rückwärtsfunktionen in Webbrowsern
• Bei der Speicherverwaltung verwendet jeder moderne Computer einen Stapel als primäre Verwaltung für einen laufenden Zweck. Jedes Programm, das in einem Computersystem ausgeführt wird, verfügt über seine eigene Speicherzuordnung.
• Stack hilft auch bei der Implementierung von Funktionsaufrufen in Computern. Die zuletzt aufgerufene Funktion wird immer zuerst abgeschlossen.

In Verbindung stehende Artikel:

• Implementieren Sie einen Stapel mithilfe einer einfach verknüpften Liste
• Grundlegende Operationen in der Stapeldatenstruktur mit Implementierungen
• Die 50 häufigsten Probleme bei der Stack-Datenstruktur, die in SDE-Interviews gestellt wurden
• Anwendungen, Vor- und Nachteile von Stack
  
• Stack für wettbewerbsfähige Programmierung