[javascript] スタックとキューの使い所と実装方法まとめ

今回はjavascriptでスタックとキューについての簡単な知識と、実際の使い所と実装方法についてまとめます。

スタックとは

スタックとは最後に入れたものを最初に取り出すデータ構造を指し、「LIFO（Last In, First Out : 後入れ先だし）」とも言われています。

スタックにデータを追加する動作を「push」と言い、データを取り出す動作を「pop」と言います。

上記図のように、データ1、データ2、データ3とpushした場合、pop動作としてはデータ3が先に取り出されます。

キューとは

キューとは、最初に入れたものを最初に取り出すデータ構造を指し、「FIFO（First In, First Out : 先入れ先だし）とも言われています。

キューにデータを追加する動作を「Enqueue（エンキュー）」と言い、データを取り出す動作を「Dequeue（デキュー）」と言います。

上記図のように、データ1、データ2、データ3とEnqueueした場合、Dequeue動作としてはデータ1が先に取り出されます。

Javascriptを利用してスタックを実装する

基本的な知識を理解したところで、javascriptを利用したスタック処理を実装していきます。

javascriptには既に配列に対してpushとpopメソッドが用意されています。これを使えば普通に実装できてしまいます。

let stack = [];
console.log('Initialize', stack);

console.log('-- push operation');
stack.push(1);
console.log('First Push Data', stack);
stack.push(2);
console.log('Second Push Data', stack);
stack.push(3);
console.log('Third Push Data', stack);

console.log('-- pop operation');
stack.pop();
console.log('Data after the first pop', stack);
stack.pop();
console.log('Data after the second pop', stack);
stack.pop();
console.log('Data after the third pop', stack);

-- push operation
First Push Data [ 1 ]
Second Push Data [ 1, 2 ]
Third Push Data [ 1, 2, 3 ]
-- pop operation
Data after the first pop [ 1, 2 ]
Data after the second pop [ 1 ]
Data after the third pop []

上記結果から、最初に1、2、3とデータをpushし、その後のpop処理では「3」「2」「1」と配列の中身が減っていきました。

Javascriptを利用してキューを実装する

スタック処理と同じようにキューも実装していきます。

javascriptの配列操作では「shift」メソッドが用意されています。これが「Dequeue」と同じ処理となります。

let queue = [];
console.log('Initialize', queue);

console.log('-- enqueue operation');
queue.push(1);
console.log('First enqueue Data', queue);
queue.push(2);
console.log('Second enqueue Data', queue);
queue.push(3);
console.log('Third enqueue Data', queue);

console.log('-- dequeue operation');
queue.shift();
console.log('Data after the first dequeue', queue);
queue.shift();
console.log('Data after the second dequeue', queue);
queue.shift();
console.log('Data after the third dequeue', queue);

Initialize []
-- enqueue operation
First enqueue Data [ 1 ]
Second enqueue Data [ 1, 2 ]
Third enqueue Data [ 1, 2, 3 ]
-- dequeue operation
Data after the first dequeue [ 2, 3 ]
Data after the second dequeue [ 3 ]
Data after the third dequeue []

上記結果から、最初に1、2、3とデータをenqueueし、その後のdequeue処理では「1」「2」「3」と配列の中身が減っていきました。

ただ、上記だとpushとshiftというメソッドを利用しているので、Queueクラスを作ってenqueueとdequeueという処理をわかりやすく実装してみたいと思います。

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

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    return this.items.shift();
  }

  peek() {
    return this.items[0];
  }
}

constructorでは初期設定として、空の配列を用意します。
enqueueメソッドでは、push操作を行い、dequeueメソッドではshift操作を行います。

peekでは、現在の最初にある値を返します。

実際に実行してみると下記のようになります。

et customQueue = new Queue();
customQueue.enqueue(1);
customQueue.enqueue(2);
customQueue.enqueue(3);
console.log('-- first data');
console.log(customQueue.peek());

customQueue.dequeue();
console.log('-- first data');
console.log(customQueue.peek());
customQueue.dequeue();
console.log('-- first data');
console.log(customQueue.peek());
customQueue.dequeue();

-- first data
1
-- first data
2
-- first data
3

スタックおよびキューの使い所

今回スタックとキューについての知識と実装方法についてまとめましたが、どういうところで使うのかというところが気になります。

スタックの用途

スタックは先入れ先だし（LIFO）という概念です。この仕組みは、下記のような用途で利用します。

例：Webブラウザの履歴

たとえば、あるページを閲覧していて次のページに遷移し、またページを戻るという操作を行うことがあるかと思います。

こういった操作はスタックの仕組みを利用しています。

例：アプリで処理を戻す処理

Excelなどで前回記入したものに戻すことがあります。こういった処理もスタックの仕組みを利用します。

キューの用途

キューは先入れ後出し（FIFO）という概念です。この仕組みは下記のような用途で利用します。

例：予約キャンセル待ち

飛行機やレストランの予約をしたことがあると思います。そのキャンセル待ちなどはこのキューの仕組みを利用しています。

例：印刷のジョブスケジュール

複数の人がプリンターやスキャナに対してリクエストを行うと、先に送信した人から順番に処理されます。
これもキューの仕組みの一つですね。

最後に

スタックとキューの考え方はとても重要な考え方の一つです。身の回りのシステムでも気づいていないだけで使われていますので、意識して開発すると、より効率的なコードを書くことができるかと思います。