LIFO か FIFO か?スタック/キューのガイド

Big O 記法を理解していることを前提としています。例は JavaScript で示されています。情報参照先「Cracking thecoding Interview」ゲイル・ラークマン・マクダウェル著

今日は、スタック と キュー という 2 つの重要なデータ構造について説明します。これらの概念、ユースケースを詳しく調べ、古典的なアプローチとプロトタイプベースのアプローチの両方を使用して JavaScript に実装します。

---

スタック: 後入れ先出し (LIFO)

パンケーキが積み重なっているところを想像してください。最後に一番上に乗せたものが最初に食べられます。これがまさにスタック データ構造の仕組みです。これは後入れ先出し (LIFO) 原則に従います。

キー操作

• Push(item): スタックの先頭に項目を追加します
• Pop(): スタックから先頭の項目を削除します
• Peak(): 先頭の項目を削除せずに返します
• isEmpty(): スタックが空かどうかを確認します

使用例

スタックは、次のようなシナリオで特に役立ちます。

• 再帰的アルゴリズム
• テキストエディターの元に戻すメカニズム

JavaScriptの実装

古典的なOOP

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

プロトタイプベース

function Stack() {
  this.items = [];
}

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

Stack.prototype.isEmpty = function() {
  return this.items.length === 0;
};

Stack.prototype.size = function() {
  return this.items.length;
};

Stack.prototype.clear = function() {
  this.items = [];
};

---

キュー: 先入れ先出し (FIFO)

ここで、キューに焦点を移しましょう。スタックとは異なり、キューは先入れ先出し (FIFO) 原則に従います。コンサート会場の列を思い浮かべてください。最初に到着した人が最初に入場します。

キー操作

• enqueue(item): キューの最後にアイテムを追加します
• dequeue(): キューから最初の項目を削除します
• Peak(): 最初の項目を削除せずに返します
• isEmpty(): キューが空かどうかを確認します

使用例

キューは一般的に次の場所で使用されます。

• 幅優先検索アルゴリズム
• タスクのスケジュール

JavaScriptの実装

古典的なOOP

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

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

プロトタイプベース

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

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

Queue.prototype.isEmpty = function() {
  return this.size === 0;
};

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

---

パフォーマンス分析

スタックとキューの両方が提供する $O(1)$O(1) 効率的に実装すると、コア操作 (スタックのプッシュ/ポップ、キューのエンキュー/デキュー) の時間の複雑さが軽減されます。これにより、特定のユースケースで高いパフォーマンスが得られます。

これらは両方とも、多くの一般的なプログラミングの問題に対する洗練された解決策を提供し、より複雑なデータ構造とアルゴリズムの基礎を形成します。これらの構造を JavaScript で理解して実装することで、リートコード/アルゴリズムの幅広い問題に取り組む準備が整います。

以上がLIFO か FIFO か?スタック/キューのガイドの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。