コース内容#
キュー#
- FIFO（First In First Out）、LILO。列に並ぶようなもので、先に来たものが先に出る
- 連続したストレージスペースが必要な順序構造（ただし、リンクリストでも実装可能）
構造定義#
- 連続したストレージスペースが必要
- 容量
- キューの先頭、キューの末尾
- + 要素数：キューが満杯かどうかを判断するために使用し、循環キューの擬似オーバーフロー問題を解決するのに便利
- データ型
構造操作#
- 出キュー
- head - 1
- count - 1
- 入キュー
- tail + 1
- count + 1
- ❗擬似オーバーフロー
- 要素を格納できなくなる
- 実際にはまだ満杯ではない：出キュー操作によりキューの先頭に空きができる
- 解決策：循環キュー
- tail が先頭に戻る
- 位置を決定するために剰余演算を使用：(tail + 1) % length
- 拡張：真のオーバーフローに遭遇した場合、コードデモを参照
スタック#
- FILO（First In Last Out）、LIFO。書籍を詰めた箱に例えられ、一方は塞がっている
- 連続したストレージスペースが必要な順序構造
構造定義#
- 連続したストレージスペースが必要（サイズ制限あり）
- 容量
- スタックトップポインタ【top】：空のスタックの場合、top = -1、0 では不適切
- データ型
構造操作#
- 出スタック：top - 1 // 空判定が必要
- 入スタック：top + 1、値を格納 // 満判定が必要
応用#
-
-
DFS と BFS の詳細は『面接筆記アルゴリズム上』 - 6 検索特集を参照
-
単調スタック、単調キューは自主学習
授業中の練習#
LC-20： 有効な括弧#
- 重要なのは思考：大きな問題を小さな問題に変える
- 問題を一種類の括弧だけに簡略化した場合、どうする？スタックを使わずに解決できるか？
- 思考：左括弧の数と右括弧の数を記録するだけでよい
- 任意の位置で、左の数 >= 右の数
- 最後の位置で、左の数 == 右の数
-
- 実際には一つの数 top で記録でき、左括弧に出会ったら + 1、右括弧に出会ったら - 1
- 任意の位置で、top >= 0
- 最後の位置で、top == 0
- この + 1、-1 操作はスタックの入スタック、出スタックに関連付けられるか？
- 一度の括弧のマッチングはスタックの入スタックと出スタックに相当する
- 括弧内の括弧は完全包含関係に相当する
- 分割統治の考え方もある
- スタック：完全包含関係の問題を処理できる
- コード
- 『面接筆記アルゴリズム上』- 5 STL「コンテナ」の使用と練習 - HZOJ-378 の解説を参照
- C 言語では、まずデータ構造 - スタックを実装し、その後スタックを使って問題を解決する
コードデモ#
キュー#
部分結果
-
-
tail の定義には二つの方法がある
- ①最後の要素のアドレスを指す
- ②最後の要素の次のアドレスを指す（本コードの選択）
-
循環キューを使用することで、擬似オーバーフローの現象は存在しなくなる
-
しかし、真のオーバーフローにはどうするか？👇
+ 拡張#
循環キューの拡張に関して
-
3 種類の動的メモリ割り当て方法【malloc、calloc、realloc】、どれを使用するか？
-
🆒malloc、calloc のどちらでも可能だが、
-
❗ 以前使用した realloc はうまくいかなくなった
- 循環キューの尾は先頭の後ろにない可能性があり、尾と先頭が重なっている
- 例：キューが満杯のとき、head、tail（ここで tail は尾部要素の次の位置と定義される）が以下の位置にあるとき、倍に拡張すると、拡張後のキューの push と pop はどうなるか？
-
- この時、head→tail の間に多くの空値が挿入されている。なぜなら realloc は値を元の順序で移動させるため、拡張部分にはまだ値がないから
- したがって、head から tail まで出キュー [間に多くの空値が挟まれている]、または tail に入キュー [tail 位置に未出キューの要素が存在する] のどちらにも問題がある！
-
しかし、malloc でスペースを割り当てた後、元のキューを head から tail まで順番に移動し、手動で head をインデックス 0 に調整する。以下に、頭尾ポインタの調整が重要である！
-
-
コード
-
- ポインタを正常な順序に調整することが重要
-
スタック#
-
-
-
-
第 72 行、pop 操作は top - 1 だけで済む
-
第 109 行、printf に未実行の命令がある場合、順序に注意が必要
- その呼び出し順序は、システムスタックの設計に関連している
- 参考printf 関数の引数は右から左にプッシュされる-CSDN；printf プッシュとポップ-CSDN
- この右から左の方法はコンパイラやマシンによって異なることはない
- 低レベルに関わるため、深く掘り下げない
- 【結論】 printf の引数に未実行の命令がある場合は、できるだけ分けて書く
-
第 106 行、出スタック前に空判定が必要で、そうでないと top = -1 が問題を引き起こす
- 初回の出スタック結果は安全である
-
-
❓ empty と top を呼び出す前にスタックが存在するか確認すべきであり、関数内で NULL 判定を行うべきではない
- 他の操作は基本的に NULL 判定があり、主にプログラムの分割の便利さに関連しているため、深く掘り下げる必要はない
- すべて NULL 判定を行うことも可能
追加知識#
- システムスタック
- スタックでもあり、サイズ：8MB
- 再帰時に使用されるのがシステムスタック
