スタックは、最後に入れたデータを最初に取り出すデータ構造です。 この性質を LIFO（Last In, First Out） といいます。
| 操作 | 意味 | 変化 |
|---|---|---|
push(x) | x をスタックに入れる | top が1つ上がる |
pop() | 一番上の値を取り出す | top が1つ下がる |
peek() | 一番上の値を見る | 取り出さないので状態は変わらない |
ここでは、top を「現在一番上にある要素番号」とします。
空のときは top = 0 です。
整数型の配列: stack
整数型: top ← 0
○ push(整数型: x)
top ← top + 1
stack[top] ← x
○整数型: pop()
整数型: x
x ← stack[top]
top ← top - 1
return x
pop しようとする状態をアンダーフロー、
容量いっぱいのスタックに push しようとする状態をオーバーフローといいます。
push(10)、push(20)、push(30)、pop()、push(40) の順に操作します。
| 操作 | 取り出した値 | スタックの状態（下から上） | top |
|---|---|---|---|
| 初期状態 | - | {} | 0 |
| push(10) | - | {10} | 1 |
| push(20) | - | {10, 20} | 2 |
| push(30) | - | {10, 20, 30} | 3 |
| pop() | 30 | {10, 20} | 2 |
| push(40) | - | {10, 20, 40} | 3 |
キューは、先に入れたデータを先に取り出すデータ構造です。 この性質を FIFO（First In, First Out） といいます。
| 操作 | 意味 | 変化 |
|---|---|---|
enqueue(x) | x をキューの後ろに入れる | rear 側に追加する |
dequeue() | キューの前から値を取り出す | front 側から削除する |
peek() | 先頭の値を見る | 取り出さないので状態は変わらない |
ここでは front を「次に取り出す位置」、
rear を「次に入れる位置」とします。
空のときは front = 1、rear = 1 とします。
整数型の配列: queue
整数型: front ← 1
整数型: rear ← 1
○ enqueue(整数型: x)
queue[rear] ← x
rear ← rear + 1
○整数型: dequeue()
整数型: x
x ← queue[front]
front ← front + 1
return x
front が右へ進みます。
実用上は、配列の末尾まで使ったら先頭に戻る循環キューを使うことがあります。
この資料では、まず基本の取り出し順を優先して扱います。
enqueue(10)、enqueue(20)、enqueue(30)、dequeue()、enqueue(40) の順に操作します。
| 操作 | 取り出した値 | キューの状態（前から後ろ） | front | rear |
|---|---|---|---|---|
| 初期状態 | - | {} | 1 | 1 |
| enqueue(10) | - | {10} | 1 | 2 |
| enqueue(20) | - | {10, 20} | 1 | 3 |
| enqueue(30) | - | {10, 20, 30} | 1 | 4 |
| dequeue() | 10 | {20, 30} | 2 | 4 |
| enqueue(40) | - | {20, 30, 40} | 2 | 5 |
| 項目 | スタック | キュー |
|---|---|---|
| 取り出し順 | 最後に入れたものが先 | 先に入れたものが先 |
| 性質 | LIFO | FIFO |
| 入れる操作 | push | enqueue |
| 取り出す操作 | pop | dequeue |
| 例 | 戻る操作、関数呼び出し、逆順処理 | 待ち行列、印刷待ち、幅優先探索 |
スタックの性質として正しいものはどれか。
キューの性質として正しいものはどれか。
空のスタックに push(3)、push(5)、push(8) を行った後、pop() で取り出される値はどれか。
空のキューに enqueue(3)、enqueue(5)、enqueue(8) を行った後、dequeue() で取り出される値はどれか。
次のスタックの push 処理で、空欄 ［ A ］ に入るものとして適切なものはどれか。
○ push(整数型: x)
top ← top + 1
［ A ］
top を1つ進めた後、その位置に新しい値 x を格納します。
次のキューの dequeue 処理で、値を取り出した後に行う更新として適切なものはどれか。
○整数型: dequeue()
整数型: x
x ← queue[front]
［ B ］
return x
front は次に取り出す位置です。
先頭の値を取り出した後は、次の要素を指すように front を1つ進めます。
空のスタックに次の操作を行う。最後の pop() で取り出される値はどれか。
push(1) push(2) pop() push(3) pop()
空のキューに次の操作を行う。最後の dequeue() で取り出される値はどれか。
enqueue(1) enqueue(2) dequeue() enqueue(3) dequeue()
空のスタックに対して次の操作を順に実行する。
すべての操作を終えた後、スタックを上（top）から順に取り出すと、どの順で値が出てくるか。
push(5) push(3) push(8) pop() push(1) push(4) pop()
次のような関数があります。process({3, 7, 2, 5, 9}) として呼び出したとき、
出力される順はどれか。
○ process(整数型の配列: a)
スタック型: s ← 空のスタック
整数型: i
for ( i を 1 から a の要素数 まで 1 ずつ増やす )
s.push(a[i])
endfor
while ( s が空でない )
s.pop() を出力
endwhile
「ブラウザの『戻る』ボタン」「電卓のアンドゥ機能」「関数呼び出し」「印刷ジョブの順番待ち」のうち、 キュー（FIFO）を使うのが最も自然なのはどれか。