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です。