このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
キューはFIFOである
- キュー は First In, First Out (FIFO) です。
- 最初に追加したアイテムが最初に退去します。
- 行列を想像してください:先頭にいる人が最初にサービスを受けます。
リストを用いたenqueueとdequeue
- Pythonのリストを使ってキューを構築できます。
- enqueue =
queue.append(x)— 後ろに追加します。 - dequeue =
queue.pop(0)— 先頭を削除して返します。
English
queue = []
queue.append("first")
queue.append("second")
print(queue.pop(0))
print(queue)
frontとempty
- 削除せずに先頭を確認する:
queue[0]。 len(queue) == 0のとき、キューは空です。- dequeueする前に空でないことを確認します。
English
queue = [10, 20, 30]
print(queue[0]) # the front
print(len(queue) == 0) # is it empty?
速度に関する注記
pop(0)は他のすべてのアイテムを1つずらす必要があります。- 大きなキューではこれが遅くなるため、より多くの時間がかかります。
- 実際のシステムでは、frontとrearポインタを持つ循環バッファを使用します。
Cambridge擬似コードにおける表現
- 試験では、配列と
frontとrearポインタを使ってキューを構築します。
DECLARE queue : ARRAY[1:10] OF INTEGER
DECLARE front, rear : INTEGER
front ← 1
rear ← 0 // empty
// enqueue value
rear ← rear + 1
queue[rear] ← value
// dequeue into value
value ← queue[front]
front ← front + 1
よくあるミス
- キューは先加入・先除去です:後ろにjoinし、先頭からleaveします。
- dequeueする前に空でないことを確認します。
あなたも試してみよう
- リストをキューとして使用します(
appendでenqueue、pop(0)でdequeue)。 - 回答を確認 を押してコードを試してください。
探索
キューはFIFOである
キューは後端に追加し、前端から削除する——最初に入れたものが最初に出る(先入れ先出し)。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
空のキューで始めます。Enqueue で "a" を追加し、次に "b" 、次に "c" を追加します。その後 dequeue を一度実行し、削除された値を first に格納します。(first は "a" であり、キューは ["b", "c"] であるべきです。)
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
キューに ⟨1⟩, ⟨2⟩, ⟨3⟩ を追加し、すべてを result へ dequeue します。スタックとは異なり、キューは順序を 維持 します。(result は [1, 2, 3] であるべきです。)
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
serve(queue) を記述し、前面のアイテムを dequeue する:リストから取り除いて リターン する。呼び出し元のリストは短くなる。
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
front(queue) を記述し、前面のアイテムを取り除かず リターン する(キューは変化しない)。キューが空の場合は None を返回する。
実行ボタンをクリックして出力を確認してください。