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

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

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

https://qiita.com/suzuki0430

https://qiita.com/official-events/5a0502a2d94ed6a00c30

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

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

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

```js: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`に入れるようにします。

```js: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()`メソッドを使用します。

```js: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()`で取り除いています。

```js: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=/

https://qiita.com/drken/items/6a95b57d2e374a3d3292