【TypeScriptで学ぶデータ構造】キュー

キュー

最初に入れたデータを最初に取り出すデータ構造の一種。

具体的な例としてはプリンターのジョブ管理

プリンターは、印刷の工程をキューで管理しています。複数のユーザーからの印刷要求があった場合、先に送られたものが最初に印刷されます。新しい印刷の要求はキューの中の末尾に追加され、プリンターはキューの先頭にある要求から処理していきます。

また実生活であれば、お店の行列もキューに相当します。（キューのことを待ち行列と言ったりもするそうです。）

キューを再現したQueueクラス

enqueueメソッドで配列itemsに要素を追加します。
追加した要素を取り出す際はdequeueメソッドを使い、最初に入れたものから取り出せるようにしています。

Queue.ts

class Queue<T> {
	private items: T[] = [];
	private front: number = 0; //キューの先頭を管理
	private rear: number = 0; //キューの末尾を管理

	//要素をキューに追加するメソッド
	enqueue(item: T): void {
		this.items[this.rear] = item;
		this.rear += 1;
	}

	//キューの先頭の要素を削除して返すメソッド
	dequeue(): T | undefined {
		if (this.isEmpty()) {
			return undefined;
		}
		const dequeuedItem = this.items[this.front];
		this.front += 1;
		return dequeuedItem;
	}

	//キューが空かどうかを確認するメソッド
	isEmpty(): boolean {
		return this.front === this.rear;
	}

	//キューの内容を表示
	printQueue(): void {
		console.log(this.items.slice(this.front, this.rear).join(" "));
	}
}

//使用例です
const queue = new Queue<number>();
//キューに1000を追加
queue.enqueue(1000);
queue.enqueue(5000);
queue.enqueue(10000);

//この時点では1000 5000 10000
queue.printQueue();

//取り出す処理。下記の場合、1000が取り出される
queue.dequeue();
//次に5000が取り出される
queue.dequeue();
//残ったのは10000！
queue.printQueue();