Ein Stapel ist eine einfache lineare Datenstruktur, die wie ein Plattenstapel funktioniert ?️. Es folgt dem Last In, First Out (LIFO)-Prinzip. Stellen Sie es sich wie einen Tellerstapel vor: Sie können Teller nur oben auf dem Stapel hinzufügen oder entfernen.

Um den Stapel besser zu verstehen, begeben wir uns auf eine kurze Reise der Fantasie.
Stellen Sie sich vor, Sie sind in einem schicken Restaurant ?️ und das Küchenpersonal bereitet sich auf einen geschäftigen Abend vor ?‍?. Im Geschirrbereich wartet ein hoher Tellerstapel darauf, benutzt zu werden. Sobald die Gäste eintreffen und die Bestellungen eingehen, nimmt das Personal die Teller vom Stapel. Wenn saubere Teller hinzugefügt werden, kommen diese ganz oben drauf. Dieses einfache System stellt sicher, dass die Teller unten im Stapel, die am längsten dort waren, zuletzt verwendet werden, während die frisch gereinigten Teller oben zuerst verwendet werden ✨.

Im Wesentlichen funktioniert eine Stack-Datenstruktur so. Ein Stack ist eine lineare Datenstruktur, die dem Last In First Out (LIFO)-Prinzip folgt. Genau wie bei unserem Tellerstapel wird der letzte Gegenstand, der einem Stapel hinzugefügt wird, als erster entfernt.

Inhaltsverzeichnis

In diesem umfassenden Tutorial zur Stack-Datenstruktur werden wir die folgenden Themen mit einem einfachen, anfängerfreundlichen Ansatz untersuchen:

1. Was ist ein Stack?
2. Vor- und Nachteile der Verwendung von Stack
3. Reale Anwendungen von Stacks
4. Schlüsseloperationen auf einem Stack
5. Stack-Implementierung in JavaScript
6. Abschluss

Sind Sie bereit? Lass uns eintauchen

Was ist ein Stapel?

Ein Stack ist eine lineare Datenstruktur, die dem Last In, First Out (LIFO)-Prinzip folgt. Dies bedeutet, dass das letzte dem Stapel hinzugefügte Element als erstes entfernt wird. Stellen Sie es sich wie einen Stapel Bücher vor: Sie können Bücher nur oben auf dem Stapel hinzufügen oder entfernen.

Vor- und Nachteile der Verwendung von Stack

Bevor wir mit dem Ablauf fortfahren und einige Codes schreiben, ist es gut zu verstehen, wo Stack verwendet werden sollte und wo nicht. Die folgende Tabelle enthält detaillierte Angaben zu den Vor- und Nachteilen von Stack.

Schlüsseloperationen auf einem Stapel

Die grundlegenden Operationen, die auf einem Stapel ausgeführt werden können, sind:

1. push(): Fügt ein Element oben im Stapel hinzu.
2. pop(): Entfernt das oberste Element vom Stapel.
3. peek(): Gibt das oberste Element des Stapels zurück, ohne es zu entfernen.
4. isEmpty(): Prüft, ob der Stapel leer ist.
5. size(): Gibt die Anzahl der Elemente im Stapel zurück.

Reale Anwendungen von Stacks

Stacks gibt es überall in der Informatik und Softwareentwicklung. Hier sind einige häufige Anwendungen:

1. Rückgängig-Funktionalität: In Texteditoren oder Grafikdesign-Software wird jede Aktion auf einen Stapel verschoben. Wenn Sie auf „Rückgängig“ klicken, wird die letzte Aktion vom Stapel entfernt und rückgängig gemacht.

2. Browserverlauf: Wenn Sie eine neue Seite besuchen, wird sie auf einen Stapel verschoben. Mit der Schaltfläche „Zurück“ wird die aktuelle Seite vom Stapel entfernt und die vorherige angezeigt.

3. Function Call Stack: In Programmiersprachen werden Funktionsaufrufe über einen Stack verwaltet. Wenn eine Funktion aufgerufen wird, wird sie auf den Aufrufstapel verschoben. Wenn es zurückkommt, ist es abgesprungen.

4. Ausdrucksauswertung: Stapel werden zur Auswertung arithmetischer Ausdrücke verwendet, insbesondere solcher in Postfix-Notation.

5. Backtracking-Algorithmen: Bei Problemen wie dem Lösen von Labyrinthen oder Rätseln können Stapel den eingeschlagenen Weg verfolgen und so bei Bedarf ein einfaches Backtracking ermöglichen.

Stack-Implementierung in JavaScript

Jetzt implementieren wir einen Stack in JavaScript. Es ist wichtig zu wissen, dass es verschiedene Möglichkeiten gibt, einen Stack in JavaScript zu implementieren. Eine der häufigsten Methoden zum Implementieren eines Stapels ist die Verwendung eines Arrays, eine andere Möglichkeit ist die Verwendung einer verknüpften Liste. In diesem Artikel implementieren wir einen Stapel mithilfe einer verknüpften Liste (einfach verknüpfte Liste).

Implementieren Sie den Stack mithilfe einer verknüpften Liste

Ich hoffe, Sie erinnern sich noch daran, wie eine verknüpfte Liste funktioniert? Möglicherweise müssen Sie sich die Implementierung der verknüpften Liste in einem unserer vorherigen Artikel derselben Serie ansehen.

So implementieren Sie einfach verknüpfte Listen in JavaScript

Die großartige Lösung? ・ 4. Okt.

#javascript #Anfänger #Programmierung #dsa

Jetzt beginnen wir mit der Implementierung unseres Stacks mithilfe einer einfach verknüpften Liste. Sollen wir?

Zuerst erstellen wir eine Node-Klasse, um unser einzelnes Stapelelement darzustellen.

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

Dann erstellen wir eine Stack-Klasse, um unseren Stack darzustellen.

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }

  // Stack Operations will be implemented here ?
}

Push-Bedienung

Der Push-Vorgang fügt oben im Stapel ein neues Element hinzu. Es erstellt einen neuen StackNode, setzt seinen nächsten Zeiger auf den aktuellen Top und aktualisiert dann Top, um auf diesen neuen Knoten zu zeigen. Schließlich wird die Größe erhöht.

  // Push element to the top of the stack
  push(element) {
    const newNode = new Node(element);
    newNode.next = this.top;
    this.top = newNode;
    this.size  ;
  }

Pop-Operation

Die Pop-Operation entfernt das oberste Element aus dem Stapel. Es prüft zunächst, ob der Stapel leer ist. Wenn dies der Fall ist, wird eine Fehlermeldung zurückgegeben. Andernfalls wird das oberste Element entfernt, der oberste Zeiger auf den nächsten Knoten aktualisiert und die Größe verringert. Schließlich wird das entfernte Element zurückgegeben.

  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    const poppedElement = this.top.data;
    this.top = this.top.next;
    this.size--;
    return poppedElement;
  }

Peek-Operation

Die Peek-Operation gibt das oberste Element zurück, ohne es zu entfernen. Es prüft zunächst, ob der Stapel leer ist. Wenn dies der Fall ist, wird eine Fehlermeldung zurückgegeben. Andernfalls werden die Daten des obersten Elements zurückgegeben.

  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.top.data;
  }

isEmpty-Vorgang

Die isEmpty-Operation prüft, ob der Stapel leer ist. Es gibt true zurück, wenn der Stapel leer ist, andernfalls false.

  // Check if the stack is empty
  isEmpty() {
    return this.size === 0;
  }

getSize-Vorgang

Die getSize-Operation gibt die Größe des Stapels zurück. Es gibt die Anzahl der Elemente im Stapel zurück.

  // Return the size of the stack
  getSize() {
    return this.size;
  }

Druckvorgang

Der Druckvorgang druckt den Stapel. Es gibt die Daten des obersten Elements zurück.

  // Print the stack
  print() {
    let current = this.top;
    let result = "";
    while (current) {
      result  = current.data   " ";
      current = current.next;
    }
    console.log(result.trim());
  }

Anwendungsbeispiel

// Usage example
const customStack = new CustomStack();
customStack.push(10);
customStack.push(20);
customStack.push(30);
console.log(customStack.pop()); // 30
console.log(customStack.peek()); // 20
console.log(customStack.getSize()); // 2
console.log(customStack.isEmpty()); // false
customStack.print(); // 20 10

In dieser Implementierung haben wir eine verknüpfte Listenstruktur (einfach verknüpfte Liste) verwendet, um unseren Stapel darzustellen. Jedes Element ist ein Knoten mit einem Datenwert und einer Referenz auf den nächsten Knoten. Ganz oben auf dem Stapel steht immer der zuletzt hinzugefügte Knoten.

Abschluss

Stacks sind eine grundlegende Datenstruktur in der Informatik, die dem Last In, First Out (LIFO)-Prinzip folgt. Sie werden in verschiedenen Anwendungen verwendet, einschließlich der Verwaltung von Funktionsaufrufen, der Implementierung der Rückgängig-Funktionalität und der Auswertung arithmetischer Ausdrücke.

In diesem Tutorial haben wir die Grundlagen von Stacks, die Vor- und Nachteile ihrer Verwendung und ihre Implementierung in JavaScript (mithilfe einer verknüpften Liste) behandelt. Beim Verständnis von Stacks geht es nicht nur darum, zu wissen, wie man sie implementiert, sondern auch darum, zu erkennen, wann sie das richtige Werkzeug zur Lösung eines Problems sind.

Während Sie Ihre Reise in der Softwareentwicklung fortsetzen, werden Sie feststellen, dass Stacks ein unverzichtbares Werkzeug in Ihrem Toolkit zur Problemlösung sind. Sie sind einfach, aber leistungsstark, und wenn Sie sie beherrschen, werden Sie Ihre Fähigkeit, effiziente Algorithmen und Datenstrukturen zu entwerfen, erheblich verbessern.

Bleiben Sie auf dem Laufenden und verbunden

Um sicherzustellen, dass Sie keinen Teil dieser Reihe verpassen und um mit mir in Kontakt zu treten, um ausführlichere Diskussionen über Softwareentwicklung (Web, Server, Mobile oder Scraping/Automatisierung), Datenstrukturen und Algorithmen sowie andere spannende Technologien zu führen Themen, folge mir auf:

• GitHub
• Linkedin
• X (Twitter)

Bleiben Sie dran und viel Spaß beim Codieren ?‍??