Grundlegendes zur Stack-Datenstruktur: Eine Schritt-für-Schritt-Anleitung zur Implementierung von Stack in JavaScript

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 ✨.

So funktioniert im Wesentlichen eine Stack-Datenstruktur. Ein Stack ist eine lineare Datenstruktur, die dem Last In First Out (LIFO)-Prinzip folgt. Genau wie bei unserem Tellerstapel wird der letzte Artikel, 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 Stapel
5. Stack-Implementierung in JavaScript
6. Fazit

---

---

Bist du 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. In der folgenden Tabelle sind die Vor- und Nachteile von Stack im Detail aufgeführt.

Pros	Cons
Simple and easy to implement	Limited access (only top element is directly accessible)
Efficient for Last-In-First-Out (LIFO) operations	Not suitable for random access of elements
Constant time O(1) for push and pop operations	Can lead to stack overflow if not managed properly
Useful for tracking state in algorithms (e.g., depth-first search)	Not ideal for searching or accessing arbitrary elements
Helps in memory management (e.g., call stack in programming languages)	Fixed size in some implementations (array-based stacks)
Useful for reversing data	May require resizing in dynamic implementations, which can be costly
Supports recursive algorithms naturally	Not efficient for large datasets that require frequent traversal
Helps in expression evaluation and syntax parsing	Potential for underflow if pop operation is called on an empty stack
Useful in undo mechanisms in software	Limited functionality compared to more complex data structures
Efficient for certain types of data organization (e.g., browser history)	Not suitable for problems requiring queue-like (FIFO) behavior

Opérations clés sur une pile

Les opérations fondamentales pouvant être effectuées sur une pile sont :

1. push() : ajoute un élément en haut de la pile.
2. pop() : supprime l'élément le plus haut de la pile.
3. peek() : renvoie l'élément supérieur de la pile sans le supprimer.
4. isEmpty() : Vérifie si la pile est vide.
5. size() : renvoie le nombre d'éléments dans la pile.

Applications réelles des piles

Les piles sont omniprésentes dans l'informatique et le développement de logiciels. Voici quelques applications courantes :

1. Fonctionnalité d'annulation : Dans les éditeurs de texte ou les logiciels de conception graphique, chaque action est poussée sur une pile. Lorsque vous appuyez sur « Annuler », l'action la plus récente est retirée de la pile et inversée.

2. Historique du navigateur : lorsque vous visitez une nouvelle page, elle est placée sur une pile. Le bouton "retour" fait sortir la page actuelle de la pile, révélant la précédente.

3. Pile d'appels de fonction : Dans les langages de programmation, les appels de fonction sont gérés à l'aide d'une pile. Lorsqu'une fonction est appelée, elle est placée sur la pile d'appels. Quand il revient, il s'enlève.

4. Évaluation des expressions : les piles sont utilisées pour évaluer les expressions arithmétiques, en particulier celles en notation postfixée.

5. Algorithmes de retour en arrière : dans des problèmes tels que la résolution de labyrinthes ou d'énigmes, les piles peuvent garder une trace du chemin emprunté, permettant un retour en arrière facile en cas de besoin.

Implémentation de la pile en JavaScript

Maintenant, implémentons une Stack en JavaScript. Il est important de savoir qu’il existe différentes manières d’implémenter une pile en JavaScript. L'une des façons courantes d'implémenter une pile consiste à utiliser un tableau, une autre méthode consiste à utiliser une liste chaînée. Dans cet article, nous allons implémenter une pile utilisant une liste chaînée (liste chaînée unique).

Implémenter la pile à l'aide d'une liste chaînée

J'espère que vous vous souvenez encore du fonctionnement des listes chaînées ? Vous devrez peut-être consulter l'implémentation de la liste chaînée dans l'un de nos articles précédents de cette même série.

Comment implémenter une liste à lien unique en JavaScript

La Grande Solution ? ・ 4 octobre

#javascript #débutants #programmation #dsa

Sekarang, mari kita mula melaksanakan tindanan kami menggunakan senarai pautan tunggal. Boleh?

Pertama, kami akan mencipta kelas Nod untuk mewakili item individu tindanan kami.

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

Kemudian, kami akan mencipta kelas Tindanan untuk mewakili tindanan kami.

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

  // Stack Operations will be implemented here ?
}

Operasi Tolak

Operasi tolak menambah elemen baharu pada bahagian atas tindanan. Ia mencipta StackNode baharu, menetapkan penuding seterusnya ke bahagian atas semasa, dan kemudian mengemas kini bahagian atas untuk menghala ke nod baharu ini. Akhirnya, saiznya bertambah.

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

Operasi Pop

Operasi pop mengalih keluar elemen paling atas daripada tindanan. Ia mula-mula menyemak sama ada timbunan kosong. Jika ya, ia mengembalikan mesej ralat. Jika tidak, ia mengalih keluar elemen atas, mengemas kini penunjuk atas ke nod seterusnya dan mengurangkan saiz. Akhirnya, ia mengembalikan elemen yang dialih keluar.

  // 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;
  }

Operasi Intai

Operasi mengintip mengembalikan elemen teratas tanpa mengalih keluarnya. Ia mula-mula menyemak sama ada timbunan kosong. Jika ya, ia mengembalikan mesej ralat. Jika tidak, ia mengembalikan data elemen teratas.

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

adalah Operasi Kosong

Operasi isEmpty menyemak sama ada tindanan kosong. Ia kembali benar jika tindanan kosong, dan palsu sebaliknya.

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

Operasi getSize

Operasi getSize mengembalikan saiz tindanan. Ia mengembalikan bilangan elemen dalam tindanan.

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

Operasi Cetak

Operasi cetakan mencetak tindanan. Ia mengembalikan data elemen teratas.

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

Contoh Penggunaan

// 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

Dalam pelaksanaan ini, kami menggunakan struktur (senarai pautan tunggal) senarai terpaut untuk mewakili tindanan kami. Setiap elemen ialah Nod dengan nilai data dan rujukan kepada Nod seterusnya. Bahagian atas tindanan sentiasa Nod yang paling baru ditambah.

Kesimpulan

Tindanan ialah struktur data asas dalam sains komputer yang mengikut prinsip Masuk Terakhir, Keluar Dahulu (LIFO). Ia digunakan dalam pelbagai aplikasi, termasuk mengurus panggilan fungsi, melaksanakan kefungsian buat asal dan menilai ungkapan aritmetik.

Dalam tutorial ini, kami telah membincangkan asas tindanan, kebaikan dan keburukan penggunaannya serta pelaksanaannya dalam JavaScript (menggunakan senarai terpaut). Memahami tindanan bukan sekadar mengetahui cara melaksanakannya, tetapi juga mengenali apabila ia adalah alat yang tepat untuk menyelesaikan masalah.

Sambil anda meneruskan perjalanan anda dalam pembangunan perisian, anda akan mendapati tindanan adalah alat yang sangat diperlukan dalam kit alat penyelesaian masalah anda. Ia mudah tetapi berkuasa dan menguasainya dengan ketara akan meningkatkan keupayaan anda untuk mereka bentuk algoritma dan struktur data yang cekap.

---

---

Kekal Kemas Kini dan Terhubung

Untuk memastikan anda tidak terlepas mana-mana bahagian dalam siri ini dan untuk berhubung dengan saya untuk perbincangan yang lebih mendalam tentang Pembangunan Perisian (Web, Pelayan, Mudah Alih atau Mengikis / Automasi), struktur data dan algoritma serta teknologi menarik yang lain topik, ikuti saya di:

• GitHub
• Linkedin
• X (Twitter)

Nantikan dan selamat mengekod ?‍??

Das obige ist der detaillierte Inhalt vonGrundlegendes zur Stack-Datenstruktur: Eine Schritt-für-Schritt-Anleitung zur Implementierung von Stack in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!