DOUG LLOYD：すべての権利、 ので、この点によって、あなたはしています おそらくかなりおなじみの 配列やリンクリストで 主要な2つはあります 私たちがしたデータ構造 のセットを維持するための話題 同様のデータ型のデータを整理。 今、私たちは話をするつもりです バリエーションのカップルについて 配列やリンクされたリストに。 このビデオでは、つもりです スタックについて話をします。 具体的に、我々は話をするつもりです データ構造は、スタックと呼ば​​れます。 前回の議論を思い出し ポインタとメモリについて、 スタックでもあること メモリのセグメントの名前 静的に宣言場所 そのあなたmemory--メモリ 名前は、名前の変数、ら これはまた、我々セテラと機能フレーム コー​​ルスタックフレームが存在します。 これは、スタックデータ構造であります メモリのないスタックセグメント。 OK。 

しかし、スタックは何ですか？ だから、それだけでかなりのです 構造の特別な種類 それは組織的な方法でデータを保持しています。 そして、二人は非常にあります 実装するための一般的な方法 二つのデータ構造を使用してスタック 我々はすでに精通していること、 配列やリンクリスト。 どのようなスタックが特別なものにすることです 我々は情報を掲載する方法 スタック、および方法我々に スタックから情報を削除します。 スタックと特に ルールは、ほとんどあり 最近追加された要素を除去することができます。 

それはスタックだかのようにそれについて考えます。 我々は情報を重ねています 自身の上に、 上部にあるだけのもの パイルを除去することができます。 私たちは下のものを削除することはできません 他のすべてがあろうから 崩壊と倒れます。 だから我々は本当にそのスタックを構築しています 我々はその後、ピース単位を削除する必要があります。 このため、私たちは一般的に参照してください。 LIFO構造としてスタックに、 最後の、最初のうち。 LIFOは、最初に出て、の最後の。 

だからためにこの制限の 情報を追加する方法 スタックから削除、本当にあります 2つだけのものは、我々は、スタックで行うことができます。 私たちはある、プッシュすることができます 我々は追加のために使用する用語 の先頭に新しい要素 スタック、またはスタックが存在しない場合 私たちは、最初からそれを作成しています 最初の場所でスタックを作成します 押すことになります。 そしてポップ、それはCSのようなものです 我々は、最近削除するために使用する用語 スタックの先頭から要素を追加しました。 

だから我々は両方を見ていきます 実装、両方の配列がベース そして、リンクされたリストベース。 そして、我々はするつもりです ベースの配列で始まります。 だからここの基本的な考え方だもの アレイベースのスタックデータ構造 以下のようになります。 ここでは、型指定された定義があります。 その内では、メンバーが2つ または構造体のフィールド。 我々は配列を持っています。 そして再び私が使用しています 任意のデータ型の値。 

これは任意のデータ・タイプとすることができます、 int型のcharまたは他のいくつかのデータ 以前に作成したタイプ。 だから我々は、サイズ容量の配列を持っています。 容量はポンドは、一定の定義されています おそらくどこか私たちのファイルインチ したがって、この特定にすでに気付か 我々は境界されている実装 自分自身一般的にあったように 配列の場合、 我々は、動的にサイズを変更することができません、 ここで特定の番号があります その最大の要素 私たちは、スタックに置くことができます。 この場合、容量素子です。 

我々はまた、追跡します スタックの最上位。 ほとんどは何の要素であります 最近スタックに追加されましたか？ そして、私たちはそのを追跡 トップと呼ばれる変数です。 そして、このすべてが一緒に包まれます スタックと呼ば​​れる新しいデータ型に。 そして、我々は作成していたら、 この新しいデータ型 我々は次のように扱うことができます 他のデータ型。 私たちは同じように、スタックSを宣言することができます 我々は、int型のx、またはchar yを行うことができます。 そして、我々は、スタックを言うとき Sは、よく何が​​起こります 我々は、のセットを取得されます メモリは、私たちのために取っておきます。 

この場合、容量に 私は明らかに決めました 私が持っているため、10 型スタックの単一の変数 これはリコール2つのフィールドが含まれています。 この場合の配列は、起こっています 整数の配列であることを 私の例のほとんどでそうであるように。 また、別の整数変数 トップを記憶することができます、 最も最近追加されました スタックの要素。 私たちのだから一つのスタック ちょうどこのようなルックスを定義しました。 それは入っている箱です 10何の配列 この場合の整数となり、 そこに緑の中の別の整数変数 スタックの先頭を示します。 

のトップを設定するには スタック私たちはs.topを言います。 それは我々がアクセスする方法を説明します 構造リコールのフィールド。 s.topを効果0に等しいです 私たちのスタックにこれを行います。 だからもう一度、私たちは2つの操作を持っています 私たちが今実行できます。 私たちは、プッシュすることができますし、我々は開くことができます。 プッシュを始めましょう。 ここでも、新しいを追加して押し スタックの先頭に要素。 

それでは、私たちが何をする必要があります この配列ベースの実装？ まあ、一般的に プッシュ機能が起こっています 受け入れることを必要とします スタックへのポインタ。 今二を取り、それについて考えます。 なぜ我々は受け入れるしたいです スタックへのポインタ？ 上の以前のビデオからリコール 変数のスコープとポインタ、 我々だけで送信した場合にどうなりますか スタック、パラメータとしてではなくね？ 実際にそこには何が渡されるでしょうか？ 我々はコピーを作成している覚えています 我々は関数に渡す場合 私たちは、ポインタを使用しない限り。 ので、この機能は、ニーズをプッシュ スタックへのポインタを受け入れます 私たちは、実際に変更しているように、 我々は変更するつもりスタック。 

他の事プッシュは、おそらくに望んでいます 受け入れタイプ値のデータ要素です。 この場合には、再び、その整数 我々は、スタックの先頭に追加するつもりです。 だから我々は我々の2つのパラメータを持っています。 私たちがしようとしています 今プッシュの内側にいますか？ まあ、単に、私たちは追加するつもりです スタックの先頭にその要素 して、どこの上部変更 スタックは、それがトップの値をドットだ、です。 だから、これはどのような機能があります プッシュの宣言 でのようになります。 アレイベースの実装です。 

これもまた、厳格なルールではありません あなたはこれを変更し、持つことができること それはさまざまな方法で変化します。 おそらくsがグローバルに宣言されています。 だからあなたもする必要はありません それは、パラメータとして渡すためです。 これはもう一度だけです プッシュのための一般的なケース。 異なるがあります それを実装する方法。 しかし、この場合には、当社の プッシュが取るために起こっています 二つの引数、スタックへのポインタと タイプ値のデータ要素、整数 この場合。 

だから我々は、我々は、Sを宣言しました s.topが0に等しいと述べました。 今度はプッシュしてみましょう スタックに数28。 まあそれは何を意味するのでしょうか？ さて現在 スタックの先頭は0です。 だから基本的には何 起こるだろうことです 我々は数を固執するつもりです アレイ位置0に28。 その、右、非常に簡単 トップだったと今、私たちは行ってもいいです。 そして、我々は何を変更する必要があります スタックの最上位になります。 次回だから 我々は内の要素をプッシュし、 我々はそれを保存しようとしています アレイ位置、おそらくない0。 私たちは、上書きしたくありません 私たちはただそこに置きます。 だから私達はちょうど1にトップを移動します。 それはおそらく意味があります。 

今、私たちは別の要素を入れたい場合は スタックに、我々は33をプッシュしたいと、 よく、今私達はちょうど33を取るつもりです アレイの位置番号でそれを置きます 1、およびその後の上部を変更私たち 配列の位置番号2であることを積み重ねます。 だから、次回あれば、私たちがしたいです スタック上に要素をプッシュし、 それは、アレイ位置2に置かれます。 そしてのは、そのもう一回やらせます。 私たちは、スタックのオフに19を押します。 私たちは、アレイ位置2で19を出してあげます 私たちのスタックの先頭を変更 アレイ位置3で そう、次の時間、私たちの場合 私たちが行ってもいいですプッシュを行う必要があります。 

[OK]を、ので、それは一言で言えば押し込みます。 何ポップは？ だから、ポッピングはの一種であります 押しに対応。 私たちは、スタックからデータを削除する方法です。 そして、一般的なポップ・ニーズの 次の操作を行います。 それはへのポインタを受け入れる必要があります 一般的なケースでは、再び、スタック。 あなたがかもしれないいくつかの他の場合には グローバルスタックを宣言しています、 その場合、あなたはそれを渡す必要はありません それは既にそれへのアクセス権を持っているためで グローバル変数として。 しかし、他に何私たちは何をする必要がありますか？ さて、私たちはインクリメントされました プッシュでスタックの先頭、 私たちは、おそらくするつもりです スタックの先頭をデクリメントします ポップで、右か？ そしてもちろん 我々はまた、するつもりです 我々は削除値を返します。 我々は要素を追加している場合は、私たちが欲しいです 後で要素を取得するには、 おそらく、実際に我々 私たちがそれらを保存します ちょうどからそれらを削除しないでください スタックし、それらを何もしません。 一般的に私たちがしている場合 プッシュとポップこちら 我々はこれを保存したいです 意味のある方法で情報 そしてそれはありません 意味はそれを廃棄します。 したがって、この関数はすべき おそらく私たちに値を返します。 

だから、これはPOPの何宣言です 左上の存在のようになります。 この関数が戻ります タイプ値のデータ。 再び、我々は使用してきました 整数全体に。 そしてそれは、スタックとしてのポインタを受け入れます その唯一の引数または唯一のパラメータです。 だから何ポップは何をするつもりですか？ それでは、私たちが今したいとしましょう 秒から要素をポップ。 だから私は、スタックが最後であることを言った覚えています 最初に出て、で、LIFOデータ構造。 どの要素は、しようとしています スタックから削除されますか？ あなたは19を推測しましたか？ あなたは正しいだろうから。 19は、我々が追加された最後の要素でした 我々は上の要素を押したときに、スタック ので、それは最初に起こっています 削除される要素。 私たちは28を言っているかのようだし、 その後、我々はそれの上に33を入れ、 私たちはその上に19を置きます。 私たちは離陸できる唯一の​​要素は19です。 

今ここで図中の私が何をやりましたか ソートの配列から19を削除されます。 それは実際にはありません 私たちがやろうとしています。 私達はちょうど種類になるだろう それがないふりをします。 それはでありまだあります その記憶場所、 しかし、我々はそれを無視するつもりです 私たちのスタックの先頭を変更することにより、 3であることから2へ。 だから我々は今プッシュした場合 スタックに別の要素、 それは以上の19を記述します。 

しかし、ここでは、トラブルを通過しないようにしましょう スタックから19を削除します。 私達はちょうどそれがないふりをすることができます。 スタックの目的のためには、次の場合に逝ってしまいました 我々は2ではなく3でトップに変更します。 すべての権利、それはそれはかなりだったので。 それは我々が行う必要があるすべてです 要素をオフにポップします。 それでは、再びそれをやってみましょう。 だから私はここに赤でそれを強調してきました 私たちは別のコールを作っている示しています。 私たちは、同じことをやろうとしています。 

だから何が起こるだろうか？ さて、私たちは店に行っています xの33、我々はつもりです 1にスタックの先頭を変更します。 我々がプッシュするようになりました場合にそう 私たちがしているスタックに要素 今やろうとして、 何が起こるだろう 我々は上書きつもりさ アレイの位置番号1。 左のようなものであるように、33 その後ろに私達はちょうどふり もはや存在しない、私達はちょうどつもりです それを上書きして、代わりにそこに40を配置します。 そしてその後、もちろん、 私たちはプッシュをしたので、 私たちは、インクリメントするつもりです 1から2へのスタックの先頭 そのように私たちが今追加した場合 別の要素、それはよ 配列の位置番号2に入ります。 

今リンクリストは、別のあります スタックを実装する方法。 そして、上のこの定義の場合 画面はここで、あなたに見慣れ それはほとんど見えるので、それはです 全く同じ、実際には、 それはかなり正確です 単独でリンクされたリストと同じ、 あなたは私たちの議論から思い出した場合 単独で別のビデオにリンクリスト。 ここでの唯一の制限 プログラマとして私たちのためのものです、 我々はに許可されていません 挿入またはランダム削除 単独でリンクされたリストから これは、我々が以前に行うことができます。 我々は今だけ挿入してから削除することができます フロントまたはリンクのトップ リスト。 それは本当にだけです しかし違い。 これは、そうでない場合は単独でリンクされたリストです。 これは、唯一の制限です 自分自身に置き換えます プログラマと スタックにそれを変更します。 

ここでのルールは常に維持することです リンクリストの先頭へのポインタ。 これは、一般的には勿論です 最初の重要なルール。 単独でリンクされたリストについては、とにかく 唯一の先頭へのポインタを必要とします それを持っているために、 チェーンが参照できます 他のすべての要素に リンクされたリストです。 しかし、それは特にです スタックとの重要な。 だから、一般的にあなたがいます 実際にするつもり このポインタはグローバル変数であることを。 それはおそらくに起こっています そのようにしても容易になります。 だから、プッシュとポップのアナログは何ですか？ 右。 だから、もう一度押す追加され スタックに新しい要素。 そのリンクリストで 我々が必要があるとしていることを意味 私たちがしている新しいノードを作成します リンクリストに追加しようとして、 して、慎重に手順に従ってください 我々は前に概説してきたこと に追加するには、単一リンクリストの チェーンを壊すことなくチェーン そして失ったり、任意の孤立 リンクされたリストの要素。 そして、それは基本的にどのようなことです テキストの小さなブロブがまとめたものです。 そしてのは、見てみましょう 図として、それは、。 

だからここに私達のリンクリストです。 それは、同時に4つの要素が含まれています。 そして、もっと完璧にここに私たちです 四つの要素を含むスタック。 そして、我々が今したいとしましょう このスタックに新しい項目を押してください。 そして、我々は新しいをプッシュします そのデータ値が12であるアイテム。 さて私たちは何をするつもりですか？ まあ最初の我々はするつもりです 動的にmallocスペース、 新しいノード用の領域​​を割り当てます。 そしてもちろんの直後 我々は常に我々のをmallocの呼び出しを行います nullを確認してください、 私たちが戻ってnullを得た場合のため 問題のいくつかの並べ替えがありました。 我々は、ヌル参照解除したくありません ポインタまたはあなたはワンセグ障害を被るだろう。 それはよくないのです。 だから我々は、ノードのmallocさました。 我々はここで成功を収めてきたと仮定します。 我々はに12を置くつもりです そのノードのデータ・フィールド。 今、あなたは私たちのポインタのどちらを思い出すん 移動は、次のように、私たちはチェーンに不具合が発生していませんか？ ここではオプションのカップルを持っていますが、 安全であることが起こっているだけ 次のポインタへのニュースを設定することです リストの古い頭をポイント またはすぐにどうなりますか リストの古い頭。 そして今のすべてが私たちの 要素が互いに連鎖しています、 私達はちょうどポイントにリストを移動することができます 新しいがする同じ場所に。 そして、我々は今、効果的にプッシュしています スタックの前に新しい要素。 

ポップするために私達はちょうどしたいです その最初の要素を削除します。 だから基本的にはどのような 私たちはここで行う必要があり、 よく私達は二番目の要素を見つける必要があります。 最終的にそれが新しいとなります 我々は最初のものを削除した後にヘッド。 だから我々はちょうどから開始する必要があります 初めは、1前方に移動します。 我々は1の保留を持ってたら、 どこ現在の前方 私たちが安全に最初のものを削除することができています し、我々はただ頭を移動することができます だったものを指すように 今、第2項及び その後の最初であります ノードが削除されました。 

だからもう一度、見てみます これで図のように、私たち 今ポップにしたいです このスタックのオフ要素。 だから我々は何をしますか？ さて、私たちは最初に作成しようとしています 起こっている新しいポインタ ヘッドと同じ場所を指すように。 我々はそれを一つの位置を移動しようとしています 前方TRAVの等号を言って たとえば、次のTRAVします TRAVポインタ1を進めう 前方位置。 今、私たちは持っていること 最初の要素に開催 ポインタと呼ばれるリスト、貫通 呼ばれるポインタを介して第2の要素 TRAV、我々は安全にそれを削除することができます スタックから最初の要素 残りの部分を失うことなく、 チェーンの私たちのため 参照する方法を持っています 二番目の要素に を介して転送します TRAVと呼ばれるポインタ。 

だから今、私たちは、そのノードを解放することができます。 私たちは、リストを解放することができます。 そして、我々が今行う必要があるのです 同じ場所を指すようにリストを移動 そのTRAVはない、と我々は戻って、ソートのです 私たちは12をプッシュする前に、我々はスタート地点 最初の場所での、右。 これは、我々があった場所を正確にあります。 我々は、この4要素のスタックを持っていました。 我々は、第五を追加しました。 我々は、第五のプッシュ 要素にしてから、我々 その直近ポップ バックオフ要素を追加しました。 

それは本当にかなりのです すべてのスタックすることがあります。 あなたは配列としてそれらを実装することができます。 あなたは、リンクリストとしてそれらを実装することができます。 その他は、もちろん、存在します 同様にそれらを実装する方法。 我々が使用する基本的な理由 スタックのような方法でデータを維持することです 最も最近追加されたこと 要素は、私たちがしている最初のものです 取り戻すためにするつもり。 私はダグロイドだけど、これはCS50です。