[Powered by Google Translate] [キュー]
[クリスガーバー、ハーバード大学]
これは、CS50、CS50.TVです]
要素の順序付けられたコレクションを格納するための1つの有用なデータ構造はキューです。
要素を削除する必要があるとき、それは使用されてい
それらが追加されたときと同じ順序インチ
この概念は、ファースト·イン、ファースト·アウトのための頭字語である、FIFOと呼ばれています。
これを視覚化するために、それは絵に有用かもしれない
店でチェックアウトライン。
人が到着すると、彼らはラインの後ろで待つ。
レジ係はその後、フロントでお客様にサービスを提供するターンを取る
その後、一度に1行を終了した人。
コンピュータサイエンスでは、我々は、責任者としてキューの先頭を参照してください。
と尾などのバック。
我々は、アプリケーションでこれを使用する場合の例
クラスの入学のための空席待ちです。
座席はクラスで利用できるようになると、
順番待ちリストの先頭にある人は、クラスに参加する機会を提供する。
>> キューは、任意のコレクションを使用して構築できます
そのような配列やリンクリストとして、順番にデータを格納します。
キューにアイテムを格納するためのコレクションと一緒に、
我々はまた、キューの末尾に項目を追加する方法を必要とする
エンキューと呼ばれている、
と別のキューの先頭から項目を削除するには、
これらはデキューと呼ばれています。
これは、キューの現在の長さを返すために別の方法を含めることがしばしば有用である
同様に、キューが空であるかどうかを確認する方法として。
我々はC言語で整数のキューを実装する方法を見てみましょう、
要素のコレクションのために配列を使用しています。
まず、我々は我々の変数を保持するキューと呼ばれる構造体を作成します。
我々は、整数の固定サイズ0のインデックス配列を使用します
要素を格納する。
我々はまた、頭と呼ばれる変数が含まれています
それはキューの先頭にある現在の要素のインデックスを格納します。
長さと呼ばれる第三の変数は、使用されます
配列内の要素の数を追跡する。
別の方法として、変数と呼ばれる尾の使用を検討でき
配列の最後のフィールド要素を指すように設定します。
我々はそれ以上のコードを記述する前に、
私たちのデザインを試してみましょう。
長さが0の空の配列を見てみましょう、
頭を0に設定します。
6、2、3、1 - 今のエンキューの4つの値を聞かせて。
長さは、今、4になります
と頭が0にとどまります。
>> 我々は価値をデキューする場合はどうなりますか？
我々は、3までの長さを削減します
1に頭を設定する
と値6を返します。
そのコードは次のようになります。
ここでは、デキューする機能を持っている
と、要素へのポインタ - Q - キューへのポインタをとる
これはint型です。
まず、それが0以上であることを確認するためのキューの長さをチェック
デキューされる要素があることを確認します。
その後、我々は、位置ヘッドで、要素の配列の中を見る
とその位置の値になるように要素の値を設定します。
その後、我々は次の指標である頭部を変更
％容量を実現します。
私たちは、それから、1キューの長さを減らすことができます。
最後に、我々は、デキューが成功したことを示すためにtrueを返す。
我々は再びデキューする場合、長さは、2になります
ヘッドはまた、2になります
と戻り値は2になります。
>> 我々は7など、別の値をエンキューするとどうなりますか？
我々は、キューの最後にあったように、
我々は、ラップアラウンドし、配列の要素0に値を格納する必要があります。
数学的には、これは、長さを追加することで表現することができる
頭のインデックスへ
とキューの容量を使用して弾性を行う。
ここでは4％4 2 2、つまり、
これは、0です。
我々はこの機能を持っているコードにこのアイデアを翻訳します。
ここでは、エンキュー関数の説明を参照してください
Q - これはキューへのポインタを指定します -
と整数である、エンキューする要素を取ります。
我々は、次のキューの容量か確認してください
まだキューの現在の長さより大きい。
次に、要素の配列内の要素を格納する
ヘッド+長さ％キューの容量によって決定されたインデックス位置にある。
次に、私たちは1でキューの長さを増やす
その後エンキュー関数が成功したことを示すためにtrueを返します。
>> 我々が言及した2つの機能に加えて、
2つの追加機能があります。
最初は、IsEmpty関数である
キューへのポインタをとる
と長さが0であることを検証します。
第二は、length関数である
また、キューへのポインタをとる
とstructから現在の長さを返します。
この短い概要は、キューの1つの可能な実装を実証してきました。
この実装の限界の一つ
キューは、固定された最大サイズを持っているということです。
我々は、キューが保持できるより多くの要素を追加しようとすると、
我々は、要求を無視し、要素を削除する必要があります
あるいは、我々は、エラーのいくつかの型を返すのを好むかもしれません。
リンクされたリストではなく、配列を使用して、
動的にサイズのキューに、それが容易になる。
しかし、我々は、リンクされたリストの要素への直接のアクセスを持っていないので、
我々は尾を追跡しない場合、
我々は最後まで各時間を取得するために、全体のリンクリストをスキャンする必要があります。
我々はまた、別のデータ型の配列を使用して検討することもでき
構造体のような、より複雑な要素のキューを作成する。
、クラスの空席待ちの私達の例に戻って考える
これらの構造は、個々の生徒を表すことができます。
>> 私の名前はクリス·ガーバーであり、これはCS50です。
[CS50.TV]
と返す - >>もう一回。
キューが成功した - とことを示すためにtrueを返す。
- ％キューの容量 -
それは編集に楽しいものになるだろう。 [笑い]