リスト・スタック・キューの問題の解き方

スタックは後から入れたものが先に出る

スタックは、積み重ねた皿のように最後に入れたものから取り出す入れ物です（LIFO）。 入れる操作を push、取り出す操作を pop と書くことが多いです。

1操作ごとに、中身を左から右へ（右端が一番上）書いていきます。

操作       スタックの中身   取り出した値
push 1     1
push 2     1 2
pop        1                2
push 3     1 3
pop        1                3
pop        （空）           1

取り出した順は 2, 3, 1 です。

キューは先に入れたものが先に出る

キューは、レジの行列のように先に入れたものから取り出す入れ物です（FIFO）。 同じ操作の並びをキューで行うと、こうなります（左端が先頭）。

操作       キューの中身     取り出した値
追加 1     1
追加 2     1 2
取出し     2                1
追加 3     2 3
取出し     3                2
取出し     （空）           3

取り出した順は 1, 2, 3 です。同じ操作でも、スタックとは順番が変わります。問題文で「どちらの端から入れて、どちらの端から出すか」を最初に確かめてください。スタックやキューを配列で作る問題では、先頭と末尾を指す変数が何を指しているか（今の要素か、次に入れる場所か）も、 ここで決まります。

連結リストは、箱と矢印で描く

連結リストは、値と「次の要素への参照」を持つ要素（ノード）をつないだものです。 科目B では node.value、node.next のように、. でノードの中身を指します。

紙には、ノードを箱、next を矢印で描きます。最後のノードの next は「未定義」で、どこも指しません。

head
 ↓
[ 10 | ●]→[ 20 | ●]→[ 30 | 未定義 ]

変数（head や p）は、箱の外から箱を指す矢印として描きます。p ← p.next は、p の矢印を1つ右の箱へ動かす、という意味です。箱そのものは動きません。

付け替えは、順番を間違えると後ろが消える

p が指すノードの次に、新しいノード q を入れる手続を考えます。正しい順番はこうです。

q.next ← p.next   // ① q から、p の次のノードを指す
p.next ← q        // ② p から q を指す

p が 10 の箱、q が 15 の箱のとき、矢印はこう変わります。

はじめ :  [10]→[20]→[30]    [15]→未定義
①のあと:  [10]→[20]→[30]    [15]→[20]  （10 も 15 も 20 を指す）
②のあと:  [10]→[15]→[20]→[30]

①と②を逆にすると、②で p.next が q に変わった時点で、20 の箱を指している矢印が1本も無くなります。そのあと①で q.next ← p.next を実行しても、p.next はもう q なので、q が自分自身を指すだけです。 20 と 30 には二度とたどり着けません。

付け替えの穴埋めでは、「この行を実行した瞬間に、どの箱を指す矢印が無くなるか」を1行ずつ確かめます。 矢印が無くなる箱があるなら、その前に別の変数で指しておく必要があります。

取り除くときは、1つ飛ばして指す

p の次のノードを取り除くときは、p の矢印を「次の次」へ向け直すだけです。

p.next ← p.next.next

p が 10 の箱なら、10 の矢印は 30 を指すようになり、20 はリストからたどれなくなります。 このとき、p.next が未定義でないかを先に確かめる必要があります。 p が最後のノードなら p.next.next は読めません。 条件式に p.next ≠ 未定義 が入っている理由は、たいていこれです。

ループは「未定義」に着いたら止まる

リストを先頭から最後までたどるときは、次の形がほとんどです。

p ← head
while (p ≠ 未定義)
  p.value を出力する
  p ← p.next
endwhile

条件が p ≠ 未定義 か p.next ≠ 未定義 かで、最後のノードを処理するかどうかが変わります。 後者だと、最後のノードに着いた時点でループを抜けるので、最後のノードの値は出力されません。 最後のノードの1つ手前で止まりたいとき（末尾に追加するときなど）に使う形です。

ほかの分野の解き方

• 木構造の問題の解き方
• オブジェクト指向の問題の解き方
• 擬似言語のトレースのやり方