5.5   練習問題¶

5.5.1   知識の確認¶

1.   スタックとキューで最初に取り出される要素¶

空のスタック S と空のキュー Q を用意し、それぞれに同じ操作列を実行します。

手順 1：A を追加します。 手順 2：B を追加します。 手順 3：要素を一つ取り出して記録します。 手順 4：C を追加します。 手順 5：空になるまで要素を取り出して記録します。

S と Q から要素が取り出される順序をそれぞれ書き、「先入れ後出し」または「先入れ先出し」を使って違いを説明してください。

2.   キューの末尾が配列の末端を越えたら¶

長さ 5 の循環配列でキューを実装します。配列のインデックスは 0～4 です。 現在は front = 3、size = 2 で、キューの A、B はそれぞれインデックス 3、4 にあります。

1. 「C をエンキューする」とき、C はどのインデックスに置きますか。その後の size はいくつですか。
2. 続いて一回デキューすると、どの要素が取り出されますか。新しい front と size はそれぞれいくつですか。
3. この時点で、先頭から末尾への論理的な順序はどうなっていますか。デキュー時に配列内のほかの要素を移動する必要はありますか。理由も説明してください。

3.   両端キューの両側からの操作¶

ここでは、push_first は先頭への追加、push_last は末尾への追加、 pop_first は先頭からの取り出し、pop_last は末尾からの取り出しを表します。

空の両端キュー deq に、次の操作を順に実行します。

1. push_last(A)
2. push_last(B)
3. push_first(C)
4. pop_last()
5. push_last(D)
6. pop_first()

1. 二回の取り出しで得られる要素はそれぞれ何ですか。
2. すべての操作が終わると、先頭から末尾へどの要素が残っていますか。
3. 六つの操作を確認してください。末尾への追加と先頭からの削除だけを許すキューで、すべて実行できますか。できない場合は、実行できない操作を挙げてください。さらに、両端キューでは実行できるかどうかと、その理由を説明してください。

5.5.2   プログラミング演習¶

1.   括弧列の検証¶

三種類の括弧 ()、[]、{} だけからなる文字列 s が与えられます。スタックを使い、正しい括弧列かどうかを判定してください。

正しい列では、各閉じ括弧の種類が、直近のまだ対応付けられていない開き括弧の種類と一致し、 かつ走査の終了後に対応付けられていない開き括弧が残っていない必要があります。判定結果を真偽値で返してください。

LeetCode

コメント欄で、考えや質問、ご提案をお寄せください。