4 練習問題

スタックとキューについて，以下の操作を定義する．

PUSH($n$ )	:スタックにデータ$n$ をプッシュする．戻り値は無し．
POP()	:スタックからデータをポップする．戻り値は，取り出した値．
ENQ($n$ )	:キューにデータ$n$ を追加する．戻り値はなし．
DEQ()	:キューからデータを取り出す．戻り値は取り出した値．

空のスタックやキューに対して，以下の操作を行ったとき，データ構造の様子を図で示せ．

[問1]

PUSH(3) $\rightarrow$ PUSH(5) $\rightarrow$ POP() $\rightarrow$ PUSH(2) $\rightarrow$ PUSH(1) $\rightarrow$ POP() $\rightarrow$ POP() $\rightarrow$ PUSH(1) $\rightarrow$ POP() $\rightarrow$ PUSH(7)

[問2]

PUSH(1) $\rightarrow$ POP() $\rightarrow$ PUSH(9) $\rightarrow$ PUSH(5) $\rightarrow$ POP() $\rightarrow$ PUSH(2) $\rightarrow$ POP() $\rightarrow$ PUSH(4) $\rightarrow$ PUSH(8) $\rightarrow$ POP()

[問3]

ENQ(6) $\rightarrow$ ENQ(2) $\rightarrow$ DEQ() $\rightarrow$ ENQ(7) $\rightarrow$ DEQ() $\rightarrow$ ENQ(3) $\rightarrow$ ENQ(1) $\rightarrow$ ENQ(2) $\rightarrow$ DEQ() $\rightarrow$ DEQ()

[問4]

ENQ(1) $\rightarrow$ DEQ() $\rightarrow$ ENQ(2) $\rightarrow$ DEQ() $\rightarrow$ ENQ(3) $\rightarrow$ DEQ() $\rightarrow$ ENQ(4) $\rightarrow$ ENQ(5) $\rightarrow$ DEQ()

[問5]

PUSH(3) $\rightarrow$ ENQ(POP()) $\rightarrow$ PUSH(8) $\rightarrow$ PUSH(5) $\rightarrow$ ENQ(POP()) $\rightarrow$ PUSH(DEQ()) $\rightarrow$ ENQ(2)

4.1 レポート提出要領

提出方法は、次の通りとする。

期限	12月19日(月) AM 10:40
用紙	A4
提出場所	山本研究室の入口のポスト
表紙	表紙を1枚つけて、以下の項目を分かりやすく記述すること。
	授業科目名「情報工学」
	課題名「課題　スタックとキュー」
	2E    学籍番号    氏名
	提出日
内容	2ページ以降に問いに対する答えを分かりやすく記述すること．

ホームページ: Yamamoto's laboratory
著者: 山本昌志