1 歩ずつ動かす
命令の列 (左から順に実行する)
- enqueue 3
- enqueue 7
- enqueue 5
- dequeue
- enqueue 9
- dequeue
- dequeue
- dequeue
先頭から出る最後に並ぶ
出た値
- いま入れた値
- 出た値
- 空いている枠
- エラー
- front は先頭、rear は最後の位置
1 歩目 / 全 9 歩実行した命令 0 個中の値 0 個
空のキューに、8 個の命令を順に実行します。入るのは 5 個までです。
いま動いている疑似コードの行
- 1enqueue(x)
- 2いっぱいなら エラー (あふれる)
- 3x を最後に置き、そこを rear にする
- 4dequeue()
- 5空なら エラー (出す値が無い)
- 6front の値を返し、次の値を front にする
見本を変える
予想してみる
いまは 1 歩目です。
次の dequeue で出るのは、どれでしょう。
今回わかること
- 最初に入れた値が、最初に出る流れ
- front と rear の 2 つの印が、それぞれいつ動くか
前提
- 配列と添字 (0 から数える番号)
- スタックの push と pop
どんな入れ物か
キューは、値を列の最後に並ばせ、取り出すときは列の先頭から取る入れ物です。先に入れた値が先に出るので、先入れ先出しと呼びます。
並ばせるのを enqueue、取り出すのを dequeue と呼びます。先頭の位置を front、最後の位置を rear と呼びます。
手順と具体例
- 1enqueue では、いっぱいでないかを確かめてから、rear の後ろに値を置く
- 2dequeue では、空でないかを確かめてから、front の値を返す
- 3返したあとは、次の値を front にする
- 4空のときの dequeue と、いっぱいのときの enqueue はエラーにする
| 命令 | 出た値 | 中身 (前から) |
|---|---|---|
| enqueue 3 | なし | [3] |
| enqueue 7 | なし | [3, 7] |
| enqueue 5 | なし | [3, 7, 5] |
| dequeue | 3 | [7, 5] |
| enqueue 9 | なし | [7, 5, 9] |
| dequeue | 7 | [5, 9] |
| dequeue | 5 | [9] |
| dequeue | 9 | [] |
手間と計算量
| 操作 | 手間 | 計算量 |
|---|---|---|
| enqueue (並ばせる) | 1 回 (最後に置くだけ) | O(1) |
| dequeue (先頭から出す) | 1 回 (front を 1 つ進める) | O(1) |
| 配列の先頭を消す書き方 | n 回 (残りを左へ詰める) | O(n) |
図では見やすいよう、出したあとに残りを左へ詰めています。実際のキューは詰めずに front の位置を 1 つ進めるので、dequeue の手間は 1 回で済みます。
使いどころ
向いているとき
- 届いた順に処理したいとき (印刷の待ち行列、注文の受付)
- 近い場所から順に調べるとき (幅優先探索)
向いていないとき
- 最後に来たものから処理したいとき (スタックを使う)
- Python のリストで pop(0) を繰り返すとき (毎回詰めるので遅い。deque を使う)
コード
疑似コード
- 1enqueue(x)
- 2いっぱいなら エラー (あふれる)
- 3x を最後に置き、そこを rear にする
- 4dequeue()
- 5空なら エラー (出す値が無い)
- 6front の値を返し、次の値を front にする
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- スタックとキューは、何が違いますか？
- 入れ方は同じで、出す端が違います。スタックは最後に入れた値から、キューは最初に入れた値から出します。
- Python で list.pop(0) を使うと、なぜ遅いのですか？
- 先頭を消したあと、残りを全部 1 つずつ左へ詰めるからです。collections.deque の popleft は詰めないので、何個あっても手間が変わりません。
