DOUG LLOYD：あなたがきたのであれば スタック上のビデオを見て、
これはおそらく感じになるだろう 既視少しのように。
それは非常によく似た概念に起こっています、 ちょうどその上にわずかにひねりを加えました。
我々は、キューについて今話をするつもりです。
だから、スタックに似キュー、 データ構造の他の一種であります
我々は維持するために使用することができます 組織化された方法でデータ。
スタックと同様に、 それを実現することができます
配列やリンクリストなど。
スタックとは異なり、ルール 我々が判断するために使用すること
物事を加えてから削除されますとき キューは少し異なっています。
>> スタックとは異なり、これは LIFO構造です、
最後の、最初のうち、キューはFIFOで 構造、FIFO、先入れ先出し、インチ
今、あなたはおそらく、キューに入れ キューとの類似を持っています。
あなたは今までに行にされてきた場合 遊園地や銀行で、
公平性のようなものがあります 構造を実現します。
行の最初の人で 銀行は最初の人であります
誰が窓口係に話すようになります。
>> これは、レースのようなものであろう 唯一の方法の場合下へ
あなたは、出納係に話すようになりました 銀行は、行の最後の人であることでした。
誰もが常にたい 行の最後の一人であるためには、
そして最初のがあった人は、 誰が、しばらくの間待っています
時間があるかもしれません、 そして、時間、時間
彼らは実際にチャンスがある前に、 銀行でお金を引き出します。
だからキューは一種のです 公平性は、以下の構造を実現します。
しかし、それは必ずしも意味するものではありません スタックはただ、悪いことであることを
キューはそれを行うための別の方法であることを。
だから、再びキューが最初に最初のものです の最後のスタック対、アウト、
最初に出て。
スタックと同様に、 我々は2つ​​の操作を持っています
我々はキューで実行できます。
名前は、追加することである、エンキューされています キューの最後に新しい要素、
で、デキュー、 最も古いを削除するには
キューの先頭から要素。
だから我々は、要素を追加するつもりです キューの最後に、
我々は要素を削除しようとしています キューの先頭から。
ここでも、スタックで、私たちは追加しました。 スタックの先頭に要素
そして要素を削除 スタックの先頭から。
だからエンキューと、それはへの追加です 終わり、正面から取り外します。
そこで最も古いものだから 常に次のものです
我々がしようと出てきます 何かをデキュー。
>> だからもう一度、キューで、我々はできます アレイベースの実装
そして、リンクリストの実装をベース。
私たちは再び始めます アレイベースの実装。
構成定義 かなり似ています。
私たちは、別の配列を持っています そこにデータ型の値の、
ので、任意のデータ型を保持することができます。
私たちは、再び使用するつもり この例では、整数です。
>> そして、ちょうど私たちと同じように アレイベースのスタック実装、
私たちが使用しているため、 配列、我々は必ずしも
その限界を持っているのC種 私達である、私たちに強制し
私たちの内の任意のダイナミズムを持っていません 成長し、配列を縮小する機能。
私たちは最初に決定する必要があります 物事の最大数は何ですか
我々はこれに入れることができること キュー、この場合、
容量はいくつかのポンドになります 我々のコードの定数定義しました。
そしてこの目的のために ビデオ、容量が10になるだろう。
>> 我々は、を追跡する必要があります 待ち行列の先頭
私たちはどの要素を知っています 我々はデキューします、
そして我々はまた、を追跡する必要があります 何かが要素の数をelse--
私たちは、キューに持っていること。
私たちはトラックを保っていない注意してください キューの最後の、ちょうど
キューのサイズ。
そして、その理由は、うまくいけば意志 瞬間に少し明確になります。
我々が完了したら このタイプの定義、
新たなデータ型を持ちます 、キューと呼ばれる我々ができるようになりました
そのデータ型の変数を宣言します。
そしてやや紛らわしい、私が決めました このキューQを呼び出すために、手紙
代わりに、データタイプQのQ。
>> だからここに私たちのキューです。
これは、構造体です。
これは3つのメンバーまたは3が含まれています フィールド、サイズの容量の配列。
この場合、容量は10です。
そして、この配列は、 整数を保持するために行きます。
グリーンで、私たちのキューの先頭です 次の要素を除去し、赤でします
キューのサイズになります、 現在、どのように多くの要素であり、
キューに存在します。
だから我々はq.front等号を言うなら 0、およびq.sizeサイズが等しいです0--
我々は、これらのフィールドに0を入れています。
そして、この時点で、我々はかなりいます 私たちのキューの使用を開始する準備ができています。
>> 私たちができるように、最初の操作 実行何かをエンキューすることで、
に新しい要素を追加します キューの最後。
さて、私たちはするには何が必要です 一般的なケースではいますか？
さて、この関数は、ニーズをエンキュー 私たちのキューへのポインタを受け入れます。
繰り返しますが、私たちは宣言していた場合 世界的に私たちのキュー、
我々はこれを行うには必要はありません 必ずしも、しかし一般的には、我々
ポインタを受け入れる必要があり データ構造への
このような、そうでないので、 私たちがしているvalue--渡しています
キューのコピーを渡し、 そのため、私たちは実際には変化していません
我々は変更するつもりキュー。
>> それを行うために必要な他の事を受け入れています 適切な型のデータ要素。
再び、この場合には、です 整数になるだろう、
しかし、あなたは任意の可能性 値のデータ型を宣言
より一般的にこれを使用します。
それは我々がエンキューする要素ですが、 我々は、キューの最後に追加します。
その後、我々は、実際にしたいです キューにそのデータを配置します。
この場合には、それを置くこと 私たちの配列の正しい場所、
し、我々は、サイズを変更したいです キューの、どのように多くの要素たち
現在持っています。
>> それでは始めましょう。
ここで、再び、ある一般的なこと フォームの関数宣言
エンキューは次のように見えるかもしれません何のために。
そしてここで私達は行きます。
番号をエンキューしてみましょう キューに28。
だから、私たちは何をするつもりですか？
さて、私たちのキューの先頭です 0、と私たちのキューのサイズで
0であり、私たちはおそらく入れたいです 配列の要素数の数28
0、右？
だから我々は今、そこにいることを配置しました。
だから今私たちは、変更する必要がありますか？
我々は変更する必要はありません キューの先頭、
私たちはどのような要素を知りたいので、 我々は、後でデキューする必要があるかもしれません。
私たちはフロントそこに持っているそうな理由 何の指標の一種であります
配列内の最も古いもの。
まあarray--で最も古いもので 実際、配列内の唯一のものは、右
now--である、28であり、 アレイ位置0で。
だから我々はしたくありません 、その緑の番号を変更します
なぜならそれは最古要素です。
むしろ、我々は、サイズを変更したいです。
したがって、この場合には、我々はよ 1のサイズを増加します。
>> 考え方の今一般的なソート 次の要素はキューに行くために起こっています
これらの2つの数値を追加することです 一緒に、フロントとサイズ、
それはどこにあなたの隣に教えてあげましょう キュー内の要素は、行くために起こっています。
だから今のは、別の番号をエンキューしましょう​​。
33をエンキューしてみましょう。
だから33は、に行くために起こっています アレイ位置0と1。
したがって、この場合には、それが起こっています アレイ位置1に移動するには、
そして今、私たちのキューのサイズは2です。
>> 繰り返しますが、私たちは変化していません 私たちの待ち行列の先頭、
28はまだあるので、 最古要素と、我々
我々は最終的に得るときto--たい 要素を削除、デキューへ
このキューから、我々が知りたいです ここで、最も古い要素です。
そして、私たちは常に維持する必要があります それがどこにあるのいくつかの指標。
だから、0がためにそこにあるものです。
それはフロントがためにそこにあるものです。
>> エンキュー中のもう一つの要素、19をしてみましょう。
私はあなたが推測することができると確信してい どこに19に行くために起こっています。
これは、に行くために起こっています アレイの位置番号2。
それは0プラス2です。
そして今、私たちのキューのサイズは3です。
私たちはその中に3つの要素を持っています。
だから我々はしていた、と私たちはつもりはない場合 今まで、別の要素をエンキュー、
それは配列の場所に行くだろう 数3、および当社のキューのサイズ
4になります。
だから我々は今、いくつかの要素を待ち行列に入れてきました。
今度は、それらを削除するために始めましょう。
キューからデキューしてみましょう。
>> ソートされており、ポップに非常に類似しました スタックのために、このアナログの、
デキューは受け入れる必要があります 再びqueue--へのポインタ、
しない限り、それがグローバルに宣言です。
今、私たちは場所を変更します キューの先頭の。
それは一種の出番です プレイには、その前の変数、
我々は削除すると理由 要素、私たちが望みます
次に古い要素に移動します。
>> その後、我々は減少します キューのサイズ、
し、我々は値を返すようにしたいです それをキューから除去しました。
繰り返しますが、私たちはそれを廃棄する必要はありません。
我々は、おそらく抽出されています それ私たちがしているqueue--から
我々はそれを気にするので、それをキューから取り出します。
だから我々は、この関数が返すようにしたいです タイプ値のデータ要素。
再び、この場合、値は整数です。
>> だから今のは何かをデキューしましょう​​。
キューから要素を削除してみましょう。
私たちが言う場合はint型xが等しい＆Q、アンパサンドq-- もう一度このQデータへのポインタです
structure--何要素 デキューされようとしていますか？
この場合には、最初であるため 、の最初のデータ構造、FIFOうち、
私たちはこの中に入れ、まず キューは28であったので、この場合には、
我々は外に28を取るつもりです 何であるキューではなく、19、
これがスタックした場合、我々は行っているだろう。
私たちは、キューから28を取るつもりです。
>> 私たちがやったことと同様に スタックは、我々は実際にはありませんよ
28を削除しようとして キュー自体から、
私達はちょうど種類になるだろう それがないふりをします。
だから、そこに滞在するつもりです メモリに、私たちはただです
種の移動によってそれを無視しようとして 我々のQデータの他の二つのフィールド
構造。
私たちは前を変更しようとしています。
Q.frontは今に起こっています それが今であるため、1であります
私たちは私たちの中に持っている最古要素 キュー、我々はすでに28を削除したので、
これはかつての最古要素でした。
>> そして今、我々は、変更したいです キューのサイズ
二つの要素の代わりに、3。
今覚え以前私が言ったとき、私たち キューに要素を追加したいです、
我々は、アレイの場所にそれを置きます これはフロントとサイズの合計です。
したがって、この場合には、我々はまだ入れています これは、キュー内の次の要素、
アレイ位置3、およびへ 我々は、第二​​のそれが表示されます。
>> だから我々は今、私たちをデキューしました キューから最初の要素。
それでは、再びそれをやってみましょう。
のは、別のものを削除してみましょう キューから要素。
場合は、現在最も古いです 要素は、アレイ位置1です。
それはq.frontを教えてくれるものです。
つまり、緑色のボックスには、ことを教えてくれる それは最古の要素です。
だから、xは33になります。
私達はちょうど種類の忘れてしまいます 33が配列に存在することを、
私たちは今、それを言いますよ キュー内の新しい最古要素
アレイ位置2、およびサイズ​​であります 要素のキューの数
我々は、キューに、1である必要があります。
今度は、何かをエンキューしましょう​​、と私 ソートの第二の前にこれを譲りました、
しかし、我々はに40を配置する場合 キュー、40は行くために起こっていることは？
さて、私たちはそれを入れてきました q.frontプラスキューサイズで、
ので、それは理にかなって 実際にここで40を配置します。
今でていることがわかり いくつかのポイントは、我々が行っています
の最後に取得します qの内側に私たちの配列、
それは28をフェードアウトと33-- 彼らは技術的には、実際にしています
オープンスペース、右？
だから、私たちはeventually--あり 追加のルール
これら二つのtogether--我々は最終的によいです 容量の大きさによって、MODに必要
私たちは周りにラップすることができます。
>> だから我々は、要素を取得する場合 数10、我々はしている場合
要素数10でそれを置き換える、私たちはいただきたいです 実際には配列の位置0に入れます。
そして、我々はするつもりだった場合 アレイは、恐れ入りますlocation--、
私たちは一緒にそれらを追加した場合、 私たちは数になりました
私たちが入れなければならないであろう場所11は次のようになります このarray--に存在しないこと、
それが範囲外に行くことになります。
私たちは10で国防省と入れることができます そのアレイ位置1インチ
だから、キューがどのように動作するかです。
彼らは常に左から行くつもりです おそらく右に折り返します。
そして、あなたは彼らがしていることを知っています フルサイズの場合、赤いボックスこと、
容量に等しくなります。
そして、我々は40を追加したので、後 キュー、よく私たちは何をする必要がありますか？
まあ、最古要素 キューに、まだ19であります
私たちは変更したくありません キューの先頭、
しかし今、私た​​ちは2を持っています キュー内の要素、
そして私たちは増やしたいです 1から2への我々のサイズ。
>> それはかなりそれでです アレイベースのキューでの作業、
スタックと同様に、 方法もあります
リンクリストとしてキューを実装します。
ここで、このデータ構造タイプがあれば あなたに見慣れ、それはあります。
それは、単独でリンクされたリストではありません それは二重にリンクされたリストです。
そして今、余談として、それは 実装が実際に可能
単独でリンクされたリストとしてキューが、 私は、可視化の観点から考えます
それが実際に表示するために役立つかもしれません 二重リンクリストとして、この。
しかし、それは間違いなくに可能です 単独でリンクリストとしてこれを行います。
>> それでは、見てみましょう 何これは、次のようになります。
我々はenquue--したい場合 今、再び私たちがしています
リンクリストへの切り替え こちらのモデルに基づきます。
私たちがエンキューしたい場合は、我々はしたいです よく、新しい要素を追加します
私たちは何をする必要がありますか？
すべての最初の、まあ、理由 我々は最後に追加しています
から削除 おそらく我々、始まります
両方へのポインタを維持したいです 頭とリンクリストのテール？
テールのための別の用語であること リンクリストの最後に、
リンクリストの最後の要素。
そして、これらはおそらく意志、 再び、私たちに有益です
彼らはグローバル変数である場合。
しかし、今、我々は新しいを追加する場合 要素我々が何をすべきかを持っているのですか？
私たちはただ[？ malak？]または動的 自分のために私たちの新しいノードを割り当てます。
私たちはいずれかを追加するときそして、同じように 二重リンクリストたちの要素、
ただof--ソートする必要があり ここでこれらの最後の3つの手順
ただ、すべての移動についてです 正しい方法でポインタ
要素がに追加されるように、 チェーンを壊すことなくチェーン
または間違いのいくつかの並べ替えを行います または事故のいくつかの並べ替えを持ちます
それによって私たちは偶然に起こります 私たちのキューのいくつかの要素を孤立。
ここでは、これがどのように見えるかです。
私たちは、要素を追加したいです このキューの最後に10。
ここだから最古要素 ヘッドによって表されます。
それは我々が最初に入れてのことです ここで、この仮想的なキューに。
そして尾​​、13は、最もあり 最近追加された要素。
そして、私たちはに10をエンキューする場合 このキューは、我々は13の後にそれを載せていきたいと思います。
そして、私たちは、動的にするつもりです 新しいノード用の領域​​を割り当てます
そして、確認するためにnullをチェックします 我々は、メモリ障害を持っていません。
その後、我々はするつもりです そのノードに10を配置し、
そして今、我々は注意する必要があります 我々はポインタを整理する方法について
私たちはチェーンに不具合が発生していません。
>> 私たちは10の前のフィールドを設定することができます 古い尾に戻って指すように、
そして'10以降となります ある時点で新しい尾
これらのすべての時間によって チェーンが接続され、
何も来るつもりないです 10後の今。
だから10の次のポインタ ヌルを指すようになります、
私たちがした後、その後、我々は、これを実行した後、 チェーンに後方10を接続し、
我々は古い頭、または、言い訳を取ることができます 私は、キューの古い尾。
キューの古い終わり、 13、それは10を指して作ります。
そして今、この時点で、私たちは持っています このキューに数10をエンキュー。
私たちが今やらなければならないことは、単に移動されます 10の代わりに13を指すようにテール。
>> デキューは実際にあります ポップと非常によく似て
あるスタックから リンクリストとして実装
あなたはスタックのビデオを見てきた場合。
私たちがやらなければならないことは、時開始です 始まり、二番目の要素を見つけ、
最初の要素を解放し、 して、ヘッドを移動
二番目の要素を指すように。
おそらくより良い、それを可視化するために ちょうどそれについて余分明確にすること。
だからここに私たちのキューが再びです。
12は最も古い要素であります 私たちの待ち行列で、頭。
10は、最新の要素であります 私たちのキューで、私たちの尾。
>> そして、私たちがしたいとき 要素をデキューするために、
私たちは最も古い要素を削除します。
だから我々は何をしますか？
さて、私たちはトラバーサルポインタを設定 それが頭から始まり、
それように、我々はそれを動かします 二番目の要素を指します
このTRAVを言って何かをqueue-- TRAVは、次の矢印等しく、例えば、
を指すようにそこTRAVを移動します 私たちは12をデキューした後、15、
私たちは12を削除した後や、意志 当時の最古要素となります。
>> 今、私たちは最初にホールドを持っています ポインタヘッドを介した要素
第2要素 ポインタTRAV経由。
私たちは今、自由に頭をすることができますし、我々はできます 何ももう15前に来ないと言います。
だから我々は15の以前の変更することができます ポインタがNULLを指すように、
そして、私たちは頭を上に移動。
そして、そこに私達は行きます。
今、我々が正常に持っています 12をデキューし、今、私たちは
4つの要素の別のキューを持っています。
それはほとんどすべてです キューにあり、
アレイベースとリンクされたリストの両方がベース。
私はダグロイドです。
これは、CS 50です。