LoginSignup
1

More than 1 year has passed since last update.

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

Last updated at Posted at 2021-06-13

はじめに

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;
  }
}

参考資料

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1