1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [キュー]

2
00:00:02,000 --> 00:00:05,000
[クリスガーバー、ハーバード大学]

3
00:00:05,000 --> 00:00:07,000
これは、CS50、CS50.TVです]

4
00:00:07,000 --> 00:00:11,000
要素の順序付けられたコレクションを格納するための1つの有用なデータ構造はキューです。

5
00:00:11,000 --> 00:00:14,000
要素を削除する必要があるとき、それは使用されてい

6
00:00:14,000 --> 00:00:16,000
それらが追加されたときと同じ順序インチ

7
00:00:16,000 --> 00:00:20,000
この概念は、ファースト·イン、ファースト·アウトのための頭字語である、FIFOと呼ばれています。

8
00:00:20,000 --> 00:00:23,000
これを視覚化するために、それは絵に有用かもしれない

9
00:00:23,000 --> 00:00:25,000
店でチェックアウトライン。

10
00:00:25,000 --> 00:00:28,000
人が到着すると、彼らはラインの後ろで待つ。

11
00:00:28,000 --> 00:00:31,000
レジ係はその後、フロントでお客様にサービスを提供するターンを取る

12
00:00:31,000 --> 00:00:34,000
その後、一度に1行を終了した人。

13
00:00:34,000 --> 00:00:37,000
コンピュータサイエンスでは、我々は、責任者としてキューの先頭を参照してください。

14
00:00:37,000 --> 00:00:39,000
と尾などのバック。

15
00:00:39,000 --> 00:00:41,000
我々は、アプリケーションでこれを使用する場合の例

16
00:00:41,000 --> 00:00:44,000
クラスの入学のための空席待ちです。

17
00:00:44,000 --> 00:00:46,000
座席はクラスで利用できるようになると、

18
00:00:46,000 --> 00:00:50,000
順番待ちリストの先頭にある人は、クラスに参加する機会を提供する。

19
00:00:50,000 --> 00:00:53,000
>> キューは、任意のコレクションを使用して構築できます

20
00:00:53,000 --> 00:00:57,000
そのような配列やリンクリストとして、順番にデータを格納します。

21
00:00:57,000 --> 00:01:00,000
キューにアイテムを格納するためのコレクションと一緒に、

22
00:01:00,000 --> 00:01:02,000
我々はまた、キューの末尾に項目を追加する方法を必要とする

23
00:01:02,000 --> 00:01:04,000
エンキューと呼ばれている、

24
00:01:04,000 --> 00:01:07,000
と別のキューの先頭から項目を削除するには、

25
00:01:07,000 --> 00:01:09,000
これらはデキューと呼ばれています。

26
00:01:09,000 --> 00:01:14,000
これは、キューの現在の長さを返すために別の方法を含めることがしばしば有用である

27
00:01:14,000 --> 00:01:17,000
同様に、キューが空であるかどうかを確認する方法として。

28
00:01:17,000 --> 00:01:20,000
我々はC言語で整数のキューを実装する方法を見てみましょう、

29
00:01:20,000 --> 00:01:23,000
要素のコレクションのために配列を使用しています。

30
00:01:23,000 --> 00:01:27,000
まず、我々は我々の変数を保持するキューと呼ばれる構造体を作成します。

31
00:01:27,000 --> 00:01:30,000
我々は、整数の固定サイズ0のインデックス配列を使用します

32
00:01:30,000 --> 00:01:33,000
要素を格納する。

33
00:01:33,000 --> 00:01:35,000
我々はまた、頭と呼ばれる変数が含まれています

34
00:01:35,000 --> 00:01:39,000
それはキューの先頭にある現在の要素のインデックスを格納します。

35
00:01:39,000 --> 00:01:42,000
長さと呼ばれる第三の変数は、使用されます

36
00:01:42,000 --> 00:01:45,000
配列内の要素の数を追跡する。

37
00:01:45,000 --> 00:01:48,000
別の方法として、変数と呼ばれる尾の使用を検討でき

38
00:01:48,000 --> 00:01:51,000
配列の最後のフィールド要素を指すように設定します。

39
00:01:51,000 --> 00:01:53,000
我々はそれ以上のコードを記述する前に、

40
00:01:53,000 --> 00:01:55,000
私たちのデザインを試してみましょう。

41
00:01:55,000 --> 00:01:58,000
長さが0の空の配列を見てみましょう、

42
00:01:58,000 --> 00:02:02,000
頭を0に設定します。

43
00:02:02,000 --> 00:02:11,000
6、2、3、1  - 今のエンキューの4つの値を聞かせて。

44
00:02:11,000 --> 00:02:14,000
長さは、今、4になります

45
00:02:14,000 --> 00:02:17,000
と頭が0にとどまります。

46
00:02:17,000 --> 00:02:20,000
>> 我々は価値をデキューする場合はどうなりますか？

47
00:02:20,000 --> 00:02:24,000
我々は、3までの長さを削減します

48
00:02:24,000 --> 00:02:28,000
1に頭を設定する

49
00:02:28,000 --> 00:02:33,000
と値6を返します。

50
00:02:33,000 --> 00:02:36,000
そのコードは次のようになります。

51
00:02:36,000 --> 00:02:38,000
ここでは、デキューする機能を持っている

52
00:02:38,000 --> 00:02:41,000
と、要素へのポインタ -  Q  - キューへのポインタをとる

53
00:02:41,000 --> 00:02:44,000
これはint型です。

54
00:02:44,000 --> 00:02:47,000
まず、それが0以上であることを確認するためのキューの長さをチェック

55
00:02:47,000 --> 00:02:50,000
デキューされる要素があることを確認します。

56
00:02:50,000 --> 00:02:54,000
その後、我々は、位置ヘッドで、要素の配列の中を見る

57
00:02:54,000 --> 00:02:58,000
とその位置の値になるように要素の値を設定します。

58
00:02:58,000 --> 00:03:01,000
その後、我々は次の指標である頭部を変更

59
00:03:01,000 --> 00:03:04,000
％容量を実現します。

60
00:03:04,000 --> 00:03:07,000
私たちは、それから、1キューの長さを減らすことができます。

61
00:03:07,000 --> 00:03:12,000
最後に、我々は、デキューが成功したことを示すためにtrueを返す。

62
00:03:12,000 --> 00:03:19,000
我々は再びデキューする場合、長さは、2になります

63
00:03:19,000 --> 00:03:24,000
ヘッドはまた、2になります

64
00:03:24,000 --> 00:03:32,000
と戻り値は2になります。

65
00:03:32,000 --> 00:03:35,000
>> 我々は7など、別の値をエンキューするとどうなりますか？

66
00:03:35,000 --> 00:03:37,000
我々は、キューの最後にあったように、

67
00:03:37,000 --> 00:03:47,000
我々は、ラップアラウンドし、配列の要素0に値を格納する必要があります。

68
00:03:47,000 --> 00:03:50,000
数学的には、これは、長さを追加することで表現することができる

69
00:03:50,000 --> 00:03:52,000
頭のインデックスへ

70
00:03:52,000 --> 00:03:55,000
とキューの容量を使用して弾性を行う。

71
00:03:55,000 --> 00:04:00,000
ここでは4％4 2 2、つまり、

72
00:04:00,000 --> 00:04:02,000
これは、0です。

73
00:04:02,000 --> 00:04:05,000
我々はこの機能を持っているコードにこのアイデアを翻訳します。

74
00:04:05,000 --> 00:04:08,000
ここでは、エンキュー関数の説明を参照してください

75
00:04:08,000 --> 00:04:10,000
Q  - これはキューへのポインタを指定します - 

76
00:04:10,000 --> 00:04:14,000
と整数である、エンキューする要素を取ります。

77
00:04:14,000 --> 00:04:18,000
我々は、次のキューの容量か確認してください

78
00:04:18,000 --> 00:04:21,000
まだキューの現在の長さより大きい。

79
00:04:21,000 --> 00:04:24,000
次に、要素の配列内の要素を格納する

80
00:04:24,000 --> 00:04:30,000
ヘッド+長さ％キューの容量によって決定されたインデックス位置にある。

81
00:04:30,000 --> 00:04:33,000
次に、私たちは1でキューの長さを増やす

82
00:04:33,000 --> 00:04:39,000
その後エンキュー関数が成功したことを示すためにtrueを返します。

83
00:04:39,000 --> 00:04:42,000
>> 我々が言及した2つの機能に加えて、

84
00:04:42,000 --> 00:04:44,000
2つの追加機能があります。

85
00:04:44,000 --> 00:04:46,000
最初は、IsEmpty関数である

86
00:04:46,000 --> 00:04:48,000
キューへのポインタをとる

87
00:04:48,000 --> 00:04:51,000
と長さが0であることを検証します。

88
00:04:51,000 --> 00:04:53,000
第二は、length関数である

89
00:04:53,000 --> 00:04:55,000
また、キューへのポインタをとる

90
00:04:55,000 --> 00:04:58,000
とstructから現在の長さを返します。

91
00:04:58,000 --> 00:05:03,000
この短い概要は、キューの1つの可能な実装を実証してきました。

92
00:05:03,000 --> 00:05:06,000
この実装の限界の一つ

93
00:05:06,000 --> 00:05:08,000
キューは、固定された最大サイズを持っているということです。

94
00:05:08,000 --> 00:05:11,000
我々は、キューが保持できるより多くの要素を追加しようとすると、

95
00:05:11,000 --> 00:05:14,000
我々は、要求を無視し、要素を削除する必要があります

96
00:05:14,000 --> 00:05:17,000
あるいは、我々は、エラーのいくつかの型を返すのを好むかもしれません。

97
00:05:17,000 --> 00:05:20,000
リンクされたリストではなく、配列を使用して、

98
00:05:20,000 --> 00:05:22,000
動的にサイズのキューに、それが容易になる。

99
00:05:22,000 --> 00:05:26,000
しかし、我々は、リンクされたリストの要素への直接のアクセスを持っていないので、

100
00:05:26,000 --> 00:05:28,000
我々は尾を追跡しない場合、

101
00:05:28,000 --> 00:05:32,000
我々は最後まで各時間を取得するために、全体のリンクリストをスキャンする必要があります。

102
00:05:32,000 --> 00:05:35,000
我々はまた、別のデータ型の配列を使用して検討することもでき

103
00:05:35,000 --> 00:05:39,000
構造体のような、より複雑な要素のキューを作成する。

104
00:05:39,000 --> 00:05:42,000
、クラスの空席待ちの私達の例に戻って考える

105
00:05:42,000 --> 00:05:45,000
これらの構造は、個々の生徒を表すことができます。

106
00:05:45,000 --> 00:05:48,000
>> 私の名前はクリス·ガーバーであり、これはCS50です。

107
00:05:48,000 --> 00:05:51,000
[CS50.TV]

108
00:05:51,000 --> 00:05:55,000
と返す -  >>もう一回。

109
00:05:55,000 --> 00:06:00,000
キューが成功した - とことを示すためにtrueを返す。

110
00:06:00,000 --> 00:06:03,000
 - ％キューの容量 - 

111
00:06:03,000 --> 00:06:06,000
それは編集に楽しいものになるだろう。 [笑い]