LoginSignup
5
0

More than 1 year has passed since last update.

@tronicboy(井上 / Mayer オースティン / Austin)inちゅらデータ株式会社

TypeScript・JavaScriptでFIFOキューを作る方法

Last updated at Posted at 2022-08-05

はいさい！ちゅらデータぬオースティンやいびーん！

概要

TypeScriptでジェネリック型を用いて、FIFOキューを作る方法を紹介します。

最初は純粋なFIFOキューを作り、それから削除ができるキューも作ってみます。

目次

  1. 簡素なFIFOキューを実装
  2. 削除できるキューを作る
  3. キューに入っている実態の数を露呈する
  4. まとめ

背景

始める前に、キューについて説明します。

キューとは何か

キューは、配列を保って保持されているメモリー上の実体の集まりです。通常のアレイと似て非なるものです。
アレイと大きく異なるのは、キューは、後ろにしか追加できないこと、そして、前からしか取り出せないことです。
スクリーンショット 2022-08-05 9.18.24.png
画像の引用：Wikipedia, Queue (abstract data type)

FIFOとは

FIFOは、First-in, First-outの頭文字で、直訳すると、最初に入るものから出す。
キュー配列の後ろに実体が入ってくるのですが、出る時は、必ず配列の前から出していく、これがFIFOです。

Enqueue

キューに実体を追加することを英語でEnqueueと言います。

Dequeue

キューから実体を取り出すことをDequeueと言います。

簡素なFIFOキューを実装

最初に、教科書通りのFIFOキューを作ってみましょう。

まず、クラス構文で書きますが、TypeScriptにキューの実体の型を教えるために、クラス定義の頭にジェネリック型を使います。

class TaskQueue<T>{
  // ここで定義するTは、new TaskQueue<{ name: string }>というように、
  // クラス・インスタンスを作成する時に、TypeScriptインタプリターにキューの値の型を教えることができます。
}

キューのMapを定義します。

通常のアレイを使わないのは、今回の実装では、Mapの方が使い勝手がいいのと、パフォーマンスがぐんといいからです。

Mapは一つの実体に対して、キーと、その値を持ちます。通常のオブジェクトに似ています。

今回は、キーに数値の型を使い、値にジェネリック型を使います。

class TaskQueue<T> {
  #queue: Map<number, T>;
}

ここで#を使っているのは、デザインパターンとして、このクラスから作成されるPrototype = インスタンスでは、キューのMapを直接変更できるようにしたくないからです。

FrontとBackをクラス変数として定義します。

class TaskQueue<T> {
  #queue: Map<number, T>;
  #front: number = 1;
  #back: number = 0;
}

#frontは次から取り出される予定の実体の、Mapにおけるキーになっています。

#backは、新しい実際のキーを定義するように使います。新しい実体を追加する時に、この#backに1を足しますので、初期値として0にします。後でconstructorの中に入れておきましょう。

contructorで初期値を設定する

上記で定義していた値をconstructorの中でも定義できます。

個人的には、contructorで設定する方が好きですが、統一していればいいかと思います。

class TaskQueue<T> {
  #queue: Map<number, T>;
  #front: number;
  #back: number;

  constructor() {
    this.#front = 1;
    this.back = 0;
    this.#queue = new Map();
  }
}

キューに追加するメソッドを作成する

ここで、Map.setを実行する前に#backを+1します。また、不要ですが、#backの追加後の値、つまり、追加した実体のキーの値を返すようにしています。

class TaskQueue<T> {
  #queue: Map<number, T>;
  #front: number;
  #back: number;

  constructor() {
    this.#front = 1;
    this.back = 0;
    this.#queue = new Map();
  }

  enqueue(value: T): number {
    this.#back++;
    this.#queue.set(this.#back, value);
    return this.#back;
  }
}

キューから取り出すメソッドを作成する

ここで注目していただきたいのは、

  1. #frontが#backより大きければ、エラーを吐かせて処理を中断すること
  2. Map.getを実行してから、Map.deleteで#queueから削除します。
  3. 最後に、キューの最善の値のキーを表す#frontを+1します。
class TaskQueue<T> {
  #queue: Map<number, T>;
  #front: number;
  #back: number;

  constructor() {
    this.#front = 1;
    this.back = 0;
    this.#queue = new Map();
  }

  enqueue(value: T): number {
    this.#back++;
    this.#queue.set(this.#back, value);
    return this.#back;
  }

  dequeue(): T {
    if (this.#front > this.#back) throw Error("End of Queue.");
    const poppedItem = this.#queue.get(this.#front);
    this.#queue.delete(this.#front);
    this.#front++;
    return poppedItem;
  }
}

キューから取り出さずに、次の実体を「覗く」メソッドを作成する

キューには通常、キュー配列から取り出さずに、次に出てくる値があるかどうかを判断するためのメソッドがあります。
今回もそのメソッドpeekを追加しましょう。

class TaskQueue<T> {
  #queue: Map<number, T>;
  #front: number;
  #back: number;

  constructor() {
    this.#front = 1;
    this.back = 0;
    this.#queue = new Map();
  }

  enqueue(value: T): number {
    this.#back++;
    this.#queue.set(this.#back, value);
    return this.#back;
  }

  dequeue(): T {
    if (this.#front > this.#back) throw Error("End of Queue.");
    const poppedItem = this.#queue.get(this.#front);
    this.#queue.delete(this.#front);
    this.#front++;
    return poppedItem;
  }

  peek(): T | undefined {
    return this.#queue.get(this.#front);
  }
}

ここまで来れば、単純だけど、立派なキューが作れます！
試しにtscでビルドして、ブラウザのコンソールで実行してみましょう。

ビルドしてブラウザで試してみる

上記のTypeScriptクラスをtscでビルドして、ブラウザのコンソールで実行して、インスタンスを作成して試してみましょう。
スクリーンショット 2022-08-05 10.04.33.png
上等！

削除できるキューを作る

次に、キューに追加した実体を削除することができるキューの実装をします。

削除するメソッドを作成

まずは、指定された数値のキーに実体があるかどうかをチェックします。

あれば、削除します。

  remove(key: number): void {
    const hasItem = this.#queue.get(key);
    if (!hasItem) throw TypeError("Item not in queue.");
    this.#queue.delete(key);
  }

dequeueのメソッドを修正する

読者はお気づきでしょうか？この実装のキューだと、上記のremoveを実行した後に、必ず変な問題が起きます。

そうです、削除したキーのところをdequeueしようとした時に、エラーが起きます。

仮に、三つの実体をキューに追加したとしましょう。

キー 1 2 3
値 "a" "b" "c"

そして、2を削除します。

キー 1 3
値 "a" "c"

すると、以下のコードを実行すると

queue.dequeue() // "a"
queue.dequeue() // エラーが起きます。

エラーが起きることが想像できますね。

これを防ぐために、dequeueのロジックを少し調整します。

  dequeue(): T {
    let poppedItem: T | null = null;
    while (!poppedItem) {
      if (this.#front > this.#back) throw Error("End of Queue.");
      const hasItem = this.#queue.get(this.#front);
      if (hasItem) {
        poppedItem = hasItem;
        break;
      }
      this.#front++;
    }
    this.#queue.delete(this.#front);
    this.#front++;
    return poppedItem;
  }

このロジックでは、存在するキーに当たるか、#frontが#backより大きくなるかのどちらかまで、順番を進んで処理します。

同じことをpeekに対して実装してもいいです。

  peek(): T | undefined {
    let peekedItem: T | undefined = undefined;
    while (!peekedItem) {
      if (this.#front > this.#back) break;
      const hasItem = this.#queue.get(this.#front);
      if (hasItem) {
        peekedItem = hasItem;
        break;
      }
      this.#front++;
    }
    return peekedItem;
  }

キューに入っている実態の数を露呈する

最後に、キューのMapは外からアクセスできないようになっているので、キューの長さを知る方法がありません。

もし必要であれば、getterでTaskQueue.prototype.sizeの値を露呈することができます。

class TaskQueue<T> {
  #queue: Map<number, T>;
  #front: number;
  #back: number;

  constructor() {
    this.#front = 1;
    this.back = 0;
    this.#queue = new Map();
  }

  get size(): number {
    return this.#queue.size;
  }

  enqueue(value: T): number {
    if (this.size > this.#maxSize) throw Error("Queue is full.");
    this.#back++;
    this.#queue.set(this.#back, value);
    return this.#back;
  }

  remove(key: number): void {
    const hasItem = this.#queue.get(key);
    if (!hasItem) throw TypeError("Item not in queue.");
    this.#queue.delete(key);
  }

  dequeue(): T {
    let poppedItem: T | null = null;
    while (!poppedItem) {
      if (this.#front > this.#back) throw Error("End of Queue.");
      const hasItem = this.#queue.get(this.#front);
      if (hasItem) {
        poppedItem = hasItem;
        break;
      }
      this.#front++;
    }
    this.#queue.delete(this.#front);
    this.#front++;
    return poppedItem;
  }

  peek(): T | undefined {
    let peekedItem: T | undefined = undefined;
    while (!peekedItem) {
      if (this.#front > this.#back) break;
      const hasItem = this.#queue.get(this.#front);
      if (hasItem) {
        peekedItem = hasItem;
        break;
      }
      this.#front++;
    }
    return peekedItem;
  }
}

まとめ

ここまで、TypeScript、もしくはJavaScriptでキューを実装する方法を説明してきましたが、いかがでしょうか？

TypeScriptだと、型チェックができて便利ですが、JavaScriptで使っていると、現状の実装では、キューに追加する実態の型が統一されていなくてもエラーが出ないようになっているのでご注意ください。

JavaScriptでも動く型チェック（TypeGuard）を実装することができるので、おすすめです。

5
0
2

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
Sign upLogin
5
0