スタックは、最後に入れたデータを最初に取り出すデータ構造です。 この性質を 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()