Day 3: スタックとキュー

今日学ぶこと

• スタック（LIFO）の仕組みと実装
• キュー（FIFO）の仕組みと実装
• 両端キュー（Deque）の概念
• スタックとキューの実践的な活用例

---

スタック（Stack）

スタックは**LIFO（Last In, First Out：後入れ先出し）**のデータ構造です。最後に追加した要素が最初に取り出されます。

flowchart TB
    subgraph Stack["スタック"]
        direction TB
        TOP["← Top"]
        E3["30"]
        E2["20"]
        E1["10"]
    end
    PUSH["push(30)"] --> TOP
    TOP --> POP["pop() → 30"]
    style Stack fill:#3b82f6,color:#fff
    style PUSH fill:#22c55e,color:#fff
    style POP fill:#ef4444,color:#fff

スタックの実装

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

  // Add to top: O(1)
  push(value) {
    this.items.push(value);
  }

  // Remove from top: O(1)
  pop() {
    if (this.isEmpty()) return undefined;
    return this.items.pop();
  }

  // View top without removing: O(1)
  peek() {
    if (this.isEmpty()) return undefined;
    return this.items[this.items.length - 1];
  }

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

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

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.pop());  // 30
console.log(stack.peek()); // 20

スタックの計算量

操作	計算量
push	O(1)
pop	O(1)
peek	O(1)
isEmpty	O(1)
search	O(n)

---

スタックの活用例

1. 括弧の対応チェック

function isValidParentheses(s) {
  const stack = [];
  const pairs = { ')': '(', ']': '[', '}': '{' };

  for (const char of s) {
    if ('([{'.includes(char)) {
      stack.push(char);
    } else if (')]}'.includes(char)) {
      if (stack.pop() !== pairs[char]) return false;
    }
  }
  return stack.length === 0;
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("({[)]}"));  // false

2. 逆ポーランド記法の計算

function evalRPN(tokens) {
  const stack = [];

  for (const token of tokens) {
    if (['+', '-', '*', '/'].includes(token)) {
      const b = stack.pop();
      const a = stack.pop();
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(Math.trunc(a / b)); break;
      }
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop();
}

// "3 + 4" in RPN: ["3", "4", "+"]
console.log(evalRPN(["3", "4", "+"])); // 7

// "(2 + 3) * 4" in RPN: ["2", "3", "+", "4", "*"]
console.log(evalRPN(["2", "3", "+", "4", "*"])); // 20

3. ブラウザの戻る/進む

class BrowserHistory {
  constructor(homepage) {
    this.backStack = [];
    this.forwardStack = [];
    this.current = homepage;
  }

  visit(url) {
    this.backStack.push(this.current);
    this.current = url;
    this.forwardStack = []; // Clear forward history
  }

  back() {
    if (this.backStack.length === 0) return this.current;
    this.forwardStack.push(this.current);
    this.current = this.backStack.pop();
    return this.current;
  }

  forward() {
    if (this.forwardStack.length === 0) return this.current;
    this.backStack.push(this.current);
    this.current = this.forwardStack.pop();
    return this.current;
  }
}

---

キュー（Queue）

キューは**FIFO（First In, First Out：先入れ先出し）**のデータ構造です。最初に追加した要素が最初に取り出されます。

flowchart LR
    ENQ["enqueue(30)"] --> BACK["Back"]
    subgraph Queue["キュー"]
        direction LR
        E1["10"]
        E2["20"]
        E3["30"]
    end
    FRONT["Front"] --> DEQ["dequeue() → 10"]
    style Queue fill:#8b5cf6,color:#fff
    style ENQ fill:#22c55e,color:#fff
    style DEQ fill:#ef4444,color:#fff

キューの実装（連結リスト版）

配列でshift()を使うとO(n)になるため、連結リストで実装するのが効率的です。

class QueueNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  // Add to back: O(1)
  enqueue(value) {
    const node = new QueueNode(value);
    if (this.tail) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
    this.length++;
  }

  // Remove from front: O(1)
  dequeue() {
    if (!this.head) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    if (!this.head) this.tail = null;
    this.length--;
    return value;
  }

  // View front without removing: O(1)
  peek() {
    return this.head ? this.head.value : undefined;
  }

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

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

const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.dequeue()); // 10
console.log(queue.peek());    // 20

キューの計算量

操作	計算量
enqueue	O(1)
dequeue	O(1)
peek	O(1)
isEmpty	O(1)
search	O(n)

---

キューの活用例

1. タスクスケジューラ

class TaskScheduler {
  constructor() {
    this.queue = new Queue();
  }

  addTask(task) {
    this.queue.enqueue(task);
    console.log(`Task added: ${task.name}`);
  }

  processNext() {
    if (this.queue.isEmpty()) {
      console.log("No tasks to process");
      return;
    }
    const task = this.queue.dequeue();
    console.log(`Processing: ${task.name}`);
    task.execute();
  }

  processAll() {
    while (!this.queue.isEmpty()) {
      this.processNext();
    }
  }
}

2. 幅優先探索（BFS）

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start]; // Using array as simple queue
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'E'],
  D: ['B'],
  E: ['C'],
};

console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D', 'E']

---

両端キュー（Deque）

Deque（Double-Ended Queue）は、両端から要素の追加・削除ができるデータ構造です。

flowchart LR
    AFL["addFront()"] --> FRONT["Front"]
    subgraph Deque["Deque（両端キュー）"]
        direction LR
        E1["10"]
        E2["20"]
        E3["30"]
    end
    BACK["Back"] --> ABL["addBack()"]
    FRONT --> RFL["removeFront()"]
    BACK --> RBL["removeBack()"]
    style Deque fill:#f59e0b,color:#fff

class Deque {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }

  addFront(value) {
    this.frontIndex--;
    this.items[this.frontIndex] = value;
  }

  addBack(value) {
    this.items[this.backIndex] = value;
    this.backIndex++;
  }

  removeFront() {
    if (this.isEmpty()) return undefined;
    const value = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return value;
  }

  removeBack() {
    if (this.isEmpty()) return undefined;
    this.backIndex--;
    const value = this.items[this.backIndex];
    delete this.items[this.backIndex];
    return value;
  }

  peekFront() {
    return this.items[this.frontIndex];
  }

  peekBack() {
    return this.items[this.backIndex - 1];
  }

  isEmpty() {
    return this.backIndex - this.frontIndex === 0;
  }

  get size() {
    return this.backIndex - this.frontIndex;
  }
}

---

スタック vs キュー vs Deque

特徴	スタック	キュー	Deque
順序	LIFO	FIFO	両端
追加	top	back	front/back
削除	top	front	front/back
用途	関数呼び出し、Undo	タスク処理、BFS	スライディングウィンドウ

---

まとめ

概念	説明
スタック	LIFO構造、push/pop操作
キュー	FIFO構造、enqueue/dequeue操作
Deque	両端から操作可能な汎用構造
コールスタック	関数呼び出しの管理にスタックを使用

重要ポイント

1. スタックとキューはどちらも O(1) で主要操作を実行できる
2. JavaScriptの配列はスタックとしては効率的だが、キューとしては非効率（shift が O(n)）
3. キューを効率的に実装するには連結リストを使う
4. BFS にはキュー、DFS にはスタックを使う

---

練習問題

問題1: 基本

2つのスタックを使ってキューを実装してください。

class QueueUsingStacks {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }
  enqueue(value) { /* implement */ }
  dequeue() { /* implement */ }
}

問題2: 応用

min()メソッドが O(1) で動作するスタックを実装してください。

チャレンジ問題

スライディングウィンドウの最大値を求める関数を、Deque を使って O(n) で実装してください。

---

参考リンク

• MDN - Array.prototype.push
• Wikipedia - Stack
• Wikipedia - Queue

---

次回予告: Day 4では「ハッシュテーブル」について学びます。O(1)での検索を実現する仕組みを理解しましょう。