【アルゴリズム】JavaScriptでキュー/スタック問題を解く

#はじめに
Qiitaの競技プログラミング研究月間ということで、アルゴリズムの記事を書いています。
今回はキュー問題とスタック問題をまとめました。

JavaScriptでアルゴリズムの勉強をされている方の参考になれば幸いです。
記事を順次まとめていきますので、その他の記事についてはマイページからご覧ください。

#キュー
キューのデータ構造をもつクラスを作成してください。
データ追加、削除、削除データの参照のために、add(), remove(), peek()メソッドを作成してください。

##解答
キューとはFIFO(First-In-First-Out)の特徴をもつデータ構造の一つです。
最初に並んだ人から食べられるといった、ラーメン屋の行列でよく例えられるやつです。

JSでキューを実現するには、配列の最初に要素を追加するunshift()や、配列から最後の要素を取り除くpop()といったメソッドを使います。
const q = new Queueで空のキューのインスタンスを作成し、キューにデータを追加する際にはq.add(~)、データを削除する際にはq.remove()のようにします。

index.js

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}

#複数キューの織り交ぜ(Weave)
2つのキューを引数に与えて、各データを織り交ぜた新しいキューを作成してください。
キューの配列データにアクセスせず、add(), remove(), peek()メソッドのみを使用してください。

    const queueOne = new Queue();
    queueOne.add(1);
    queueOne.add(2);
    const queueTwo = new Queue();
    queueTwo.add('Hi');
    queueTwo.add('There');
    const q = weave(queueOne, queueTwo);
    q.remove() // 1
    q.remove() // 'Hi'
    q.remove() // 2
    q.remove() // 'There'

##解答
まず、前項で作成したクラスQueueを関数作成前に読み込んでおきます。

空のキューのインスタンスconst q = new Queue()を用意し、ここに2つのキューから取り出したデータを交互に入れていきます。
while (sourceOne.peek() || sourceTwo.peek())で各キューのデータがなくなるまでループをまわし、データがあればq.add(sourceOne.remove())のように取り出したデータをqに入れるようにします。

index.js

const Queue = require('./queue');

function weave(sourceOne, sourceTwo) {
  const q = new Queue();

  while (sourceOne.peek() || sourceTwo.peek()) {
    if (sourceOne.peek()) {
      q.add(sourceOne.remove());
    }
    if (sourceTwo.peek()) {
      q.add(sourceTwo.remove());
    }
  }
  return q;
}

#スタック
スタックのデータ構造をもつクラスを作成してください。
データ追加、削除、削除データの参照のために、push(), pop(), peek()メソッドを作成してください。

##解答
スタックとはLIFO(Last-In-First-Out)の特徴をもつデータ構造の一つです。
積み上がった本の山に例えられるやつですね。

JSでスタックを実現する際、pop()とpeek()メソッドはキューと同様ですが、要素追加にはpush()メソッドを使用します。

index.js

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

  push(record) {
    this.data.push(record);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }
}

#スタックからキューの作成
2つのスタックを使用してキューを作成してください。

##解答
2つのスタック(LIFO)を使うとキュー(FIFO)を実現することができます。

例えば、remove()の中では、1つ目のスタックthis.firstから取り出したデータを2つ目のスタックthis.secondに入れていき、this.secondの最後のデータをconst record = this.second.pop()で取り除いています。

index.js

const Stack = require('./stack');

class Queue {
  constructor() {
    this.first = new Stack();
    this.second = new Stack();
  }

  add(record) {
    this.first.push(record);
  }

  remove() {
    while (this.first.peek()) {
      this.second.push(this.first.pop());
    }

    const record = this.second.pop();

    return record;
  }

  peek() {
    while (this.first.peek()) {
      this.second.push(this.first.pop());
    }

    const record = this.second.peek();

    return record;
  }
}

#参考資料
https://www.udemy.com/share/101WNkCEEZd11VRno=/