スタック・キューについて学んだ

2021-07-03

アルゴリズム学んだシリーズ。今回はスタックとキューについて学びました。というか既に概念自体は知っていたのでおさらいになります。

ソースコード

以下にあります。

スタックとは

日常でもスタックするとか言いますが、そのまんまの意味です。縦にどんどん山積みにしてあるデータ構造で、最後に追加した要素を取り出す仕組みのことです。

例えば

丸亀製麺でうどんを食べるときに、最初にトレーとお皿を上から取っていく（一番下から取ることない）
積ん読してある本の一番上のものから読む
洗濯かごに入ってある洗濯物を洗濯するときに、上から洗濯機に入れる（下からわざわざ入れない）

のようなものはすべてスタックです。後入れ先出しなので***LIFO（Last In Farst Out）***なんて呼ばれます。

追加する：プッシュ
取り出す：ポップ

キュー

キューもそのまんまの意味です。英語で順番待ちなどの意味なので

区役所で整理券を、もらって書いてある受付番号の順番に呼ばれる
レジに並ぶ
飛行機に搭乗するとき

のようなものはすべてキューです。先入れ先出しなので***FIFO（Farst In Farst Out）***と呼びます。

追加する：エンキュー
取り出す：デキュー

プログラミングでの用途を考える

普段配列を使っていれば、すぐにスタックとキューを実装できそうなことが分かります。スタックであればpush()とpop()を使えばOKです。

const array = [];
array.push(0);
array.push(1);
array.push(2);
array.push(3);
array.pop() // 3が削除される

キューは最初の要素を取り除くのでshift()を使います。

const array = [];
array.push(0);
array.push(1);
array.push(2);
array.push(3);
array.shift() // 0が削除される

※ shift()は破壊的な変更なので、配列を一度別変数で展開して使いましょう！

他にも再帰関数の呼び出しはスタック、非同期通信はキューになるかなと思います。

実装

以前に連結リストを学んだでLinkedListクラスを実装していました。実はこの機能をほとんど使えそうです。スタックの方は、ゼロから作りましたがキューの方は、LinkedListのクラスをimportして実装しました。

スタックはpush()とpop()があればいいので作るのは簡単です。push関数内で生成しているインスタンスは扱うNodeの初期値になります。（連結リストで実装したものと同じ）

/**
   * 追加
   *
   * @param {T} value
   * @return {*} 
   * @memberof Stack
   */
  push(value: T) {
    const newNode = new StackNode(value)
    newNode.nextNode = this.head
    this.head = newNode
    this.length + - 1

    return newNode
  }

  /**
   *
   * 削除
   * @return {*} 
   * @memberof Stack
   */
  pop() {
    const deletedNode = this.head
    if (this.head) {
      this.head = this.head.nextNode
      this.length -= 1
    }
    return deletedNode
  }

キューの方は、ソースコードを見て頂ければと思いますが、LinkedListをimportしています。スタックとの違いであるshiftについては、deleteHead()という関数で最初のheadを削除しています。

リングバッファ

キューで「エンキュー」「デキュー」を繰り返すと、要素が右側に移動してしまいデータのサイズがどんどん膨れ上がっていきます。このようなことにならないような仕組みとしてリングバッファというものがあります。

これはデータのメモリが輪っか状になっているように見えるもので実態は、最後の要素に移動すると最初に戻る、最初の要素の前に移動すると最後の要素に移動するという意味になります。データの一時的な保管場所ですね。

やってみて

正直、普段からよく使う言葉ではあるのでそこまで難しく考える必要はないかもしれませんが、何かソースコードを読んでいるときに「これはスタックしてそう」とか「ここでキューが溜まりそう」などを意識することって大事なことだなと改めて思いました。

次回

次は、ハッシュテーブルをやってみます。