スタックのデータ構造を理解する: 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 ?
}

押し込み操作

プッシュ操作により、スタックの先頭に新しい要素が追加されます。新しい 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++;
  }

ポップ操作

pop 操作は、スタックから最上位の要素を削除します。まずスタックが空かどうかを確認します。存在する場合は、エラー メッセージが返されます。それ以外の場合は、最上位要素を削除し、次のノードへの最上位ポインタを更新し、サイズをデクリメントします。最後に、削除された要素を返します。

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

ピーク操作

ピーク操作は、先頭の要素を削除せずに返します。まずスタックが空かどうかを確認します。存在する場合は、エラー メッセージが返されます。それ以外の場合は、最上位要素のデータを返します。

  // 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 オペレーション

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 (Twitter)

コーディングを楽しみにしていてください?‍??

以上がスタックのデータ構造を理解する: JavaScript でスタックを実装するためのステップバイステップ ガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。