Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript

スタックは、プレートのスタックのように機能する単純な線形データ構造です。これは後入れ先出し (LIFO) の原則に従います。これをプレートの山と考えてください。プレートを追加または削除できるのは、山の最上部のみです。

スタックをより深く理解するために、短い想像の旅に出かけましょう?
あなたが高級レストランにいて、キッチンのスタッフが忙しい夜の準備をしているところを想像してみてください ?‍?。食器エリアには、使用されるのを待っている背の高い皿の山があります。客が到着して注文が殺到すると、スタッフが山の上から皿を取り出します。きれいなプレートを追加すると、すぐにその上に置かれます。このシンプルなシステムにより、スタックの一番下にある最も長く存在したプレートが最後に使用され、一番上の新しく洗浄されたプレートが最初に使用されます。

これは本質的に、スタック データ構造がどのように機能するかです。スタックは、後入れ先出し (LIFO) 原則に従う線形データ構造です。プレートのスタックと同様に、スタックに追加された最後のアイテムが最初に削除されます。

目次

スタック データ構造に関するこの包括的なチュートリアルでは、シンプルで初心者向けのアプローチで次のトピックを検討します。

1. スタックとは何ですか?
2. スタックを使用するメリットとデメリット
3. スタックの実際のアプリケーション
4. スタック上のキー操作
5. JavaScript でのスタック実装
6. 結論

---

---

準備はできていますか?飛び込んでみましょう

スタックとは何ですか?

スタックは、後入れ先出し (LIFO) 原則に従う線形データ構造です。これは、スタックに追加された最後の要素が最初に削除されることを意味します。これは本の積み重ねのようなものだと考えてください。本の追加または削除は、積み重ねの一番上からのみ行うことができます。

スタックを使用することの長所と短所

フローを続行してコードを記述する前に、Stack を使用する場所と使用しない場所を理解しておくとよいでしょう。以下の表は、スタックの明確な長所と短所を詳細に示しています。

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

Key Operations on a Stack

The fundamental operations that can be performed on a stack are:

1. push(): Adds an element to the top of the stack.
2. pop(): Removes the topmost element from the stack.
3. peek(): Returns the top element of the stack without removing it.
4. isEmpty(): Checks if the stack is empty.
5. size(): Returns the number of elements in the stack.

Real-World Applications of Stacks

Stacks are every where in computer science and software development. Here are some common applications:

1. Undo Functionality: In text editors or graphic design software, each action is pushed onto a stack. When you hit "undo," the most recent action is popped off the stack and reversed.

2. Browser History: When you visit a new page, it's pushed onto a stack. The "back" button pops the current page off the stack, revealing the previous one.

3. Function Call Stack: In programming languages, function calls are managed using a stack. When a function is called, it's pushed onto the call stack. When it returns, it's popped off.

4. Expression Evaluation: Stacks are used to evaluate arithmetic expressions, especially those in postfix notation.

5. Backtracking Algorithms: In problems like maze-solving or puzzle-solving, stacks can keep track of the path taken, allowing easy backtracking when needed.

Stack Implementation in JavaScript

Now, let's implement a Stack in JavaScript. It is important to know that there are different ways to implement a stack in JavaScript. One of the common ways to implement a stack is using array, another way is to use linked list. In this article, we'll implement a stack using linked list (singly linked list).

Implement Stack using Linked List

I hope you still remember how linked list works? You might need to check out the linked list implementation in one of our previous articles in this same series.

How to Implement Singly Linked List in JavaScript

The Great SoluTion ? ・ Oct 4

#javascript #beginners #programming #dsa

現在，讓我們開始使用單鍊錶實作我們的堆疊。我們可以嗎？

首先，我們將建立一個 Node 類別來表示我們的堆疊單一專案。

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

然後，我們將建立一個 Stack 類別來表示我們的堆疊。

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

  // Stack Operations will be implemented here ?
}

推播操作

push操作將一個新元素加入到堆疊頂部。它會建立一個新的 StackNode，將其下一個指標設為目前頂部，然後更新頂部以指向這個新節點。最後，它增加了大小。

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

流行操作

彈出操作從堆疊中刪除最頂層的元素。它首先檢查堆疊是否為空。如果是，則傳回錯誤訊息。否則，它刪除頂部元素，更新頂部指標到下一個節點，並減少大小。最後，它會傳回被刪除的元素。

  // 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 操作會傳回頂部元素而不刪除它。它首先檢查堆疊是否為空。如果是，則傳回錯誤訊息。否則，返回頂部元素的資料。

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

isEmpty操作

isEmpty 操作檢查堆疊是否為空。如果堆疊為空則傳回 true，否則傳回 false。

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

取得大小操作

getSize 操作傳回堆疊的大小。它會傳回堆疊中元素的數量。

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

列印操作

列印操作列印堆疊。它會傳回頂部元素的資料。

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

使用範例

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

在此實作中，我們使用鍊錶（單鍊錶）結構來表示我們的堆疊。每個元素都是一個節點，具有資料值和對下一個節點的引用。堆疊頂部始終是最近新增的節點。

結論

堆疊是電腦科學中的基本資料結構，遵循後進先出（LIFO）原則。它們用於各種應用程序，包括管理函數呼叫、實現撤消功能以及計算算術表達式。

在本教程中，我們介紹了堆疊的基礎知識、使用它們的優缺點以及它們在 JavaScript 中的實作（使用鍊錶）。了解堆疊不僅僅是了解如何實現它們，還要認識到它們何時是解決問題的正確工具。

當您繼續軟體開發之旅時，您會發現堆疊是您解決問題的工具箱中不可或缺的工具。它們簡單而強大，掌握它們將顯著增強您設計高效演算法和資料結構的能力。

---

---

保持更新和聯繫

確保您不會錯過本系列的任何部分，並與我聯繫以更深入地討論軟體開發（Web、伺服器、移動或抓取/自動化）、資料結構和演算法以及其他令人興奮的技術主題，請追蹤我：

• GitHub
• 領英
• X（推特）

敬請期待並祝您編碼愉快??‍??

The above is the detailed content of Understanding Stack Data Structure: A Step-by-Step Guide to Implementing Stack in JavaScript. For more information, please follow other related articles on the PHP Chinese website!