スタック・キューの擬似言語実装

科目B頻出のデータ構造、スタックとキューの擬似言語実装を理解しましょう。

日野 こむぎ

スタックって、配列で実装できるんだよね?

藤森 さやか 先生

そう。
配列とインデックス変数で簡単に実装できるの。
push と pop を擬似言語で書いてみましょう。

/* スタックは配列 stack[] と先頭位置 top で表現 */
○ 手続: push(整数型: x)
  top ← top + 1
  stack[top] ← x

○ 手続: pop()
  整数型: result
  result ← stack[top]
  top ← top - 1
  return result

青木 澪

push は top を1つ進めて値を保存。
pop は top の値を取り出して top を1つ戻す。
LIFO (後入れ先出し) が実現されるわ。

桃井 すみれ

キューはどうですかぁ?

青木 澪

キューは先頭 (head) と末尾 (tail) の2つのインデックスで管理。
enqueue は tail に追加、dequeue は head から取り出す。

○ 手続: enqueue(整数型: x)
  tail ← tail + 1
  queue[tail] ← x

○ 手続: dequeue()
  整数型: result
  result ← queue[head]
  head ← head + 1
  return result

日野 こむぎ

おぉ、シンプルじゃん!
これならあたしでも分かるかも!

藤森 さやか 先生

実用上はバッファのサイズ制限や、配列の周回 (リングバッファ) が必要になるけど、試験では基本動作だけ理解できればOKよ。

青木 澪

出題例としては、「以下の操作後、スタックから取り出される値の順序は?」のような問題ね。
push(1), push(2), push(3), pop, push(4), pop, pop の結果は 3, 4, 2 になるわ。