BFE.devでのAI解答例 - JavaScript コーディング問題
108. QueueでStack を実装する

以下はJavaScriptの class 構文を使った回答例です。

class Stack {
  constructor() {
    this.queue = new Queue();
  }
  
  push(element) {
    this.queue.enqueue(element);
  }
  
  pop() {
    const size = this.size();
    
    for (let i = 0; i < size - 1; i++) {
      // size - 1 回だけキューの先頭要素をキューの末尾に移動
      this.queue.enqueue(this.queue.dequeue());
    }
    
    // キューの末尾の要素がトップ要素になる
    return this.queue.dequeue();
  }
  
  peek() {
    const size = this.size();
    
    for (let i = 0; i < size - 1; i++) {
      // size - 1 回だけキューの先頭要素をキューの末尾に移動
      this.queue.enqueue(this.queue.dequeue());
    }
    
    // キューの末尾の要素がトップ要素になる
    const topEl = this.queue.peek();
    
    // トップ要素を取得したあとにキューに追加することで元の形に戻す
    this.queue.enqueue(this.queue.dequeue());
    
    return topEl;
  }
  
  size() {
    return this.queue.size();
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
  
  enqueue(element) {
    const newNode = new Node(element);
    
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    
    this.count++;
  }
  
  dequeue() {
    if (!this.head) {
      return null;
    }
    
    const dequeuedEl = this.head.value;
    this.head = this.head.next;
    this.count--;
    
    return dequeuedEl;
  }
  
  peek() {
    if (!this.head) {
      return null;
    }
    
    return this.head.value;
  }
  
  size() {
    return this.count;
  }
}

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

Stack クラスでは、Queue を使って要素の追加と取り出しを行います。 pop(), peek() メソッドでは、キューの先頭の要素を末尾にまで移動させて、トップ要素を取り出しています。 この操作によって、キューの先頭が常にトップ要素になるようにしています。

Queue クラスでは、単方向リストを使って実装しています。