コースの内容#
キュー#
- FIFO（First In First Out）、LILO。並び順を区別する
- 順序構造であり、連続したストレージスペースが必要（ただし、リンクリストでも実装可能）
構造の定義#
- 連続したストレージスペースが必要
- 容量
- キューヘッド、キューテール
- + 要素数：キューが満杯かどうかを判断し、循環キューで偽のオーバーフロー問題を解決するために使用
- データ型
構造の操作#
- キューから取り出す
- ヘッド - 1
- 要素数 - 1
- キューに追加する
- テール + 1
- 要素数 + 1
- ❗偽のオーバーフロー
- 要素を保存できなくなる
- 実際にはまだ満杯ではないかもしれない：キューヘッドに空きがあるため
- 解決策：循環キュー
- テールが最後まで行ったら、キューの先頭に戻る
- 位置を決定するために剰余演算子を使用：(テール + 1) % 長さ
- 容量の拡張：真のオーバーフローが発生した場合、コードのデモを参照してください
スタック#
- FILO（First In Last Out）、LIFO。本の箱に似ているが、片方は封鎖されている
- 順序構造でもある
構造の定義#
- 連続したストレージスペースが必要（サイズ制限あり）
- 容量
- スタックトップポインタ【top】：空のスタックの場合、top = -1、0 は適切ではない
- データ型
構造の操作#
- スタックから取り出す：top - 1 // 空の場合は判定が必要
- スタックに追加する：top + 1、値を保存する // 満杯の場合は判定が必要
応用#
-
-
DFS と BFS の詳細は「面接と筆記試験のアルゴリズム上」- 6 検索トピックを参照
-
モノトニックスタック、モノトニックキューは自己学習してください
授業の練習#
LC-20： 有効な括弧#
- キーポイントは考え方です：大きな問題を小さな問題に変換する方法
- 一種類の括弧だけの場合、どのように対処しますか？スタックを使用せずに完了できますか？
- アイデア：左括弧の数と右括弧の数だけを記録すれば良い
- 任意の位置で、左数 >= 右数
- 最後の位置で、左数 == 右数
-
- 実際には、左括弧に遭遇すると + 1、右括弧に遭遇すると - 1 の操作を行うだけで十分です
- 任意の位置で、top >= 0
- 最後の位置で、top == 0
- この + 1、-1 の操作は、スタックの push と pop に関連付けることができますか？
- 一回の括弧のマッチングは、スタックの push と pop を一回行うことと同等です
- 括弧内の括弧は完全に含まれる関係です
- 分割統治の考え方もあります
- スタック：完全に含まれる関係を持つ問題を処理できます
- コード
- 「面接と筆記試験のアルゴリズム上」- 5 STL「コンテナ」の使用と練習 - HZOJ-378 の解説を参照してください
- C 言語では、まずデータ構造であるスタックを実装し、その後スタックを使用して問題を解決します
コードデモ#
キュー#
一部の結果
-
-
テールの定義には 2 つの方法があります
- ①最後の要素のアドレスを指す
- ②最後の要素の次のアドレスを指す（このコードの選択）
-
循環キューを使用すると、偽のオーバーフローの現象はもはや存在しません
-
ただし、真のオーバーフローの場合はどうすればよいですか？👇
+ 容量の拡張#
循環キューに対する容量の拡張
-
3 つの動的メモリ割り当て方法【malloc、calloc、realloc】のうち、どれを使用しますか？
-
🆒malloc、calloc のどちらでも使用できますが、
-
❗以前使用していた realloc はうまく動作しません
- 循環キューのテールは、ヘッドの後ろではなく、テールとヘッドが重なっている可能性があります
- 例：キューがいっぱいの場合、ヘッド、テール（ここではテールは最後の要素の後）が次の位置にあるとします。この場合、容量を倍に拡張した後、キューの push と pop はどうなりますか？
-
- この場合、ヘッド→テールの間に多くの空の値が挿入されます。なぜなら、realloc は値を元の順序で移動するため、拡張部分にはまだ値がありません
- では、ヘッドからテールまでの出列 [間には多くの空の値が含まれています]、またはテールからの入列 [テールの位置にはまだ出列していない要素があります] は、どのような問題がありますか？
-
一方、malloc で空間を割り当て、元のキューをヘッドからテールまで順番に移動するだけで十分です。つまり、ヘッドをインデックス 0 に手動で調整するだけです。次のように、ヘッドとテールポインタの調整が重要です！
-
-
コード
-
- ポインタを正しい順序に調整することが重要です
-
スタック#
72 行目、pop 操作は top - 1 だけで十分です
109 行目、printf 内に実行待ちのコマンドがある場合、順序に注意が必要です
* 呼び出しの順序は、システムスタックの設計に関連しています
* 参考：printf 函数参数从右至左压栈-CSDN；printf 压栈出栈-CSDN
* この右から左への方法は、コンパイラやマシンによって異なるものではありません
* ローレベルのことであり、深くは追求しません
* 【結論】 printf の引数に実行待ちのコマンドがある場合は、できるだけ分けて書くべきです
106 行目、出栈前に空の場合に注意する必要があります。そうしないと、top = -1 で問題が発生します
* 初回の出力結果は安全です
* 
- ❓スタックが存在するかどうかを確認するために、empty と top を呼び出す前に、関数内で NULL の判定を行うべきです
- ただし、他の操作は基本的に NULL の判定がありますが、プログラムの分割を容易にするためのものであり、細かく考える必要はありません
- すべての操作に NULL の判定を含めることもできます
追加の知識#
- システムスタック
- スタックでもあり、サイズは 8MB です
- 再帰時に使用されるのはシステムスタックです
