はじめに
今までのリストとは少し違うデータ構造がキューとスタックです。
リストに制限を加えることで高速に動作するように設計されています。
リストは静的配列から「便利にしたい」という思いで進化したデータ構造でしたが、
キューやスタックは「制限があってもいいから速く動いてほしい」という思いがあります。
また、これからもデータ構造シリーズは続いていきますので、
良かったら高評価の方もよろしくお願いします。
目次
- キューとは
- プログラムでのキュー
- キューのアイデア
- 想定される操作とその最悪時間計算量
- さいごに
1. キューとは
キューとスタックはリストに制限を加えたデータ構造です。
参照ができず、挿入や削除も特定の順番でしか行えません。
キューは最初に追加された要素から取り出すことができます。
イメージとしてはラーメン屋の待ち行列のようなものです。
| リストの操作 | 疑似コード表記 | 説明 |
|---|---|---|
| 参照 | l.get(i) |
リスト l の i 番目の要素を参照 |
| 挿入 | l.insert(e, i) |
リスト l の i 番目に新しい要素 e を挿入 |
| 削除 | l.delete(i) |
リスト l の i 番目の要素を削除 |
| キューの操作 | 疑似コード表記 | 説明 |
|---|---|---|
| エンキュー | q.enqueue(e) |
キュー q に要素 e を追加 |
| デキュー | q.dequeue() |
キュー q から先頭の要素を取り出し |
人 -> enqueue -> | 人, 人, ... | -> dequeue -> ラーメン屋
以上で紹介したのは典型的なキューの話です。
実際はもう少し便利にするためにサイズが分かったり、
取り出さないけど先頭の要素を参照する操作などがあったりします。
その時はこの動画で紹介する計算量ではないこともあります。
2. プログラムでのキュー
キューは動的配列ほど各言語ですぐに使えないこともあります。
言語によっては自分で実装する必要がありますので注意してください。
- キュー
- 厳密にはキューではない
- JavaScript での Array
使ったことがある場合はイメージが沸いたのではないかと思います。
もし使ったことがない場合でも問題ないので引き続きご覧ください。
3. キューのアイデア
4. 想定される操作とその最悪時間計算量
キューとリストはできる操作が違うという説明はしましたが、
それだけだったらリストを使えばいいという話になってしまいます。
キューやスタックのメリットは、特定の操作が高速にできることです。
5. さいごに
この記事ではキューについて紹介しました。
制限があっても特定の条件下で早く動いてほしいという
少し違うモチベーションで進化したデータ構造でした。
次の記事では同じようなデータ構造としてスタックを紹介しようと思います。
