1
00:00:00,000 --> 00:00:05,204

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD：あなたがきたのであれば
スタック上のビデオを見て、

3
00:00:07,370 --> 00:00:09,870
これはおそらく感じになるだろう
既視少しのように。

4
00:00:09,870 --> 00:00:13,850
それは非常によく似た概念に起こっています、
ちょうどその上にわずかにひねりを加えました。

5
00:00:13,850 --> 00:00:15,530
我々は、キューについて今話をするつもりです。

6
00:00:15,530 --> 00:00:19,350
だから、スタックに似キュー、
データ構造の他の一種であります

7
00:00:19,350 --> 00:00:22,412
我々は維持するために使用することができます
組織化された方法でデータ。

8
00:00:22,412 --> 00:00:24,120
スタックと同様に、
それを実現することができます

9
00:00:24,120 --> 00:00:27,000
配列やリンクリストなど。

10
00:00:27,000 --> 00:00:30,320
スタックとは異なり、ルール
我々が判断するために使用すること

11
00:00:30,320 --> 00:00:34,210
物事を加えてから削除されますとき
キューは少し異なっています。

12
00:00:34,210 --> 00:00:36,590
>> スタックとは異なり、これは
LIFO構造です、

13
00:00:36,590 --> 00:00:45,610
最後の、最初のうち、キューはFIFOで
構造、FIFO、先入れ先出し、インチ

14
00:00:45,610 --> 00:00:49,320
今、あなたはおそらく、キューに入れ
キューとの類似を持っています。

15
00:00:49,320 --> 00:00:52,820
あなたは今までに行にされてきた場合
遊園地や銀行で、

16
00:00:52,820 --> 00:00:56,430
公平性のようなものがあります
構造を実現します。

17
00:00:56,430 --> 00:00:59,160
行の最初の人で
銀行は最初の人であります

18
00:00:59,160 --> 00:01:00,760
誰が窓口係に話すようになります。

19
00:01:00,760 --> 00:01:03,522
>> これは、レースのようなものであろう
唯一の方法の場合下へ

20
00:01:03,522 --> 00:01:06,730
あなたは、出納係に話すようになりました
銀行は、行の最後の人であることでした。

21
00:01:06,730 --> 00:01:09,146
誰もが常にたい
行の最後の一人であるためには、

22
00:01:09,146 --> 00:01:12,580
そして最初のがあった人は、
誰が、しばらくの間待っています

23
00:01:12,580 --> 00:01:14,715
時間があるかもしれません、
そして、時間、時間

24
00:01:14,715 --> 00:01:17,590
彼らは実際にチャンスがある前に、
銀行でお金を引き出します。

25
00:01:17,590 --> 00:01:22,510
だからキューは一種のです
公平性は、以下の構造を実現します。

26
00:01:22,510 --> 00:01:25,780
しかし、それは必ずしも意味するものではありません
スタックはただ、悪いことであることを

27
00:01:25,780 --> 00:01:28,160
キューはそれを行うための別の方法であることを。

28
00:01:28,160 --> 00:01:32,420
だから、再びキューが最初に最初のものです
の最後のスタック対、アウト、

29
00:01:32,420 --> 00:01:34,440
最初に出て。

30
00:01:34,440 --> 00:01:36,190
スタックと同様に、
我々は2つ​​の操作を持っています

31
00:01:36,190 --> 00:01:38,470
我々はキューで実行できます。

32
00:01:38,470 --> 00:01:43,910
名前は、追加することである、エンキューされています
キューの最後に新しい要素、

33
00:01:43,910 --> 00:01:47,330
で、デキュー、
最も古いを削除するには

34
00:01:47,330 --> 00:01:49,670
キューの先頭から要素。

35
00:01:49,670 --> 00:01:53,600
だから我々は、要素を追加するつもりです
キューの最後に、

36
00:01:53,600 --> 00:01:57,220
我々は要素を削除しようとしています
キューの先頭から。

37
00:01:57,220 --> 00:02:00,790
ここでも、スタックで、私たちは追加しました。
スタックの先頭に要素

38
00:02:00,790 --> 00:02:03,380
そして要素を削除
スタックの先頭から。

39
00:02:03,380 --> 00:02:07,570
だからエンキューと、それはへの追加です
終わり、正面から取り外します。

40
00:02:07,570 --> 00:02:10,639
そこで最も古いものだから
常に次のものです

41
00:02:10,639 --> 00:02:13,620
我々がしようと出てきます
何かをデキュー。

42
00:02:13,620 --> 00:02:18,330
>> だからもう一度、キューで、我々はできます
アレイベースの実装

43
00:02:18,330 --> 00:02:20,110
そして、リンクリストの実装をベース。

44
00:02:20,110 --> 00:02:24,620
私たちは再び始めます
アレイベースの実装。

45
00:02:24,620 --> 00:02:27,070
構成定義
かなり似ています。

46
00:02:27,070 --> 00:02:30,720
私たちは、別の配列を持っています
そこにデータ型の値の、

47
00:02:30,720 --> 00:02:32,690
ので、任意のデータ型を保持することができます。

48
00:02:32,690 --> 00:02:35,570
私たちは、再び使用するつもり
この例では、整数です。

49
00:02:35,570 --> 00:02:39,830
>> そして、ちょうど私たちと同じように
アレイベースのスタック実装、

50
00:02:39,830 --> 00:02:42,340
私たちが使用しているため、
配列、我々は必ずしも

51
00:02:42,340 --> 00:02:46,850
その限界を持っているのC種
私達である、私たちに強制し

52
00:02:46,850 --> 00:02:51,670
私たちの内の任意のダイナミズムを持っていません
成長し、配列を縮小する機能。

53
00:02:51,670 --> 00:02:55,710
私たちは最初に決定する必要があります
物事の最大数は何ですか

54
00:02:55,710 --> 00:02:59,300
我々はこれに入れることができること
キュー、この場合、

55
00:02:59,300 --> 00:03:02,070
容量はいくつかのポンドになります
我々のコードの定数定義しました。

56
00:03:02,070 --> 00:03:05,430
そしてこの目的のために
ビデオ、容量が10になるだろう。

57
00:03:05,430 --> 00:03:07,690
>> 我々は、を追跡する必要があります
待ち行列の先頭

58
00:03:07,690 --> 00:03:11,160
私たちはどの要素を知っています
我々はデキューします、

59
00:03:11,160 --> 00:03:15,070
そして我々はまた、を追跡する必要があります
何かが要素の数をelse--

60
00:03:15,070 --> 00:03:16,690
私たちは、キューに持っていること。

61
00:03:16,690 --> 00:03:19,360
私たちはトラックを保っていない注意してください
キューの最後の、ちょうど

62
00:03:19,360 --> 00:03:21,150
キューのサイズ。

63
00:03:21,150 --> 00:03:24,310
そして、その理由は、うまくいけば意志
瞬間に少し明確になります。

64
00:03:24,310 --> 00:03:26,143
我々が完了したら
このタイプの定義、

65
00:03:26,143 --> 00:03:29,080
新たなデータ型を持ちます
、キューと呼ばれる我々ができるようになりました

66
00:03:29,080 --> 00:03:30,630
そのデータ型の変数を宣言します。

67
00:03:30,630 --> 00:03:35,350
そしてやや紛らわしい、私が決めました
このキューQを呼び出すために、手紙

68
00:03:35,350 --> 00:03:38,090
代わりに、データタイプQのQ。

69
00:03:38,090 --> 00:03:39,600
>> だからここに私たちのキューです。

70
00:03:39,600 --> 00:03:40,700
これは、構造体です。

71
00:03:40,700 --> 00:03:45,730
これは3つのメンバーまたは3が含まれています
フィールド、サイズの容量の配列。

72
00:03:45,730 --> 00:03:47,340
この場合、容量は10です。

73
00:03:47,340 --> 00:03:49,580
そして、この配列は、
整数を保持するために行きます。

74
00:03:49,580 --> 00:03:55,240
グリーンで、私たちのキューの先頭です
次の要素を除去し、赤でします

75
00:03:55,240 --> 00:03:58,610
キューのサイズになります、
現在、どのように多くの要素であり、

76
00:03:58,610 --> 00:04:01,190
キューに存在します。

77
00:04:01,190 --> 00:04:05,300
だから我々はq.front等号を言うなら
0、およびq.sizeサイズが等しいです0--

78
00:04:05,300 --> 00:04:07,120
我々は、これらのフィールドに0を入れています。

79
00:04:07,120 --> 00:04:11,070
そして、この時点で、我々はかなりいます
私たちのキューの使用を開始する準備ができています。

80
00:04:11,070 --> 00:04:14,140
>> 私たちができるように、最初の操作
実行何かをエンキューすることで、

81
00:04:14,140 --> 00:04:16,860
に新しい要素を追加します
キューの最後。

82
00:04:16,860 --> 00:04:19,089
さて、私たちはするには何が必要です
一般的なケースではいますか？

83
00:04:19,089 --> 00:04:23,690
さて、この関数は、ニーズをエンキュー
私たちのキューへのポインタを受け入れます。

84
00:04:23,690 --> 00:04:26,370
繰り返しますが、私たちは宣言していた場合
世界的に私たちのキュー、

85
00:04:26,370 --> 00:04:29,490
我々はこれを行うには必要はありません
必ずしも、しかし一般的には、我々

86
00:04:29,490 --> 00:04:32,330
ポインタを受け入れる必要があり
データ構造への

87
00:04:32,330 --> 00:04:35,040
このような、そうでないので、
私たちがしているvalue--渡しています

88
00:04:35,040 --> 00:04:38,140
キューのコピーを渡し、
そのため、私たちは実際には変化していません

89
00:04:38,140 --> 00:04:41,050
我々は変更するつもりキュー。

90
00:04:41,050 --> 00:04:44,860
>> それを行うために必要な他の事を受け入れています
適切な型のデータ要素。

91
00:04:44,860 --> 00:04:46,818
再び、この場合には、です
整数になるだろう、

92
00:04:46,818 --> 00:04:49,330
しかし、あなたは任意の可能性
値のデータ型を宣言

93
00:04:49,330 --> 00:04:51,160
より一般的にこれを使用します。

94
00:04:51,160 --> 00:04:56,030
それは我々がエンキューする要素ですが、
我々は、キューの最後に追加します。

95
00:04:56,030 --> 00:04:58,573
その後、我々は、実際にしたいです
キューにそのデータを配置します。

96
00:04:58,573 --> 00:05:01,490
この場合には、それを置くこと
私たちの配列の正しい場所、

97
00:05:01,490 --> 00:05:05,040
し、我々は、サイズを変更したいです
キューの、どのように多くの要素たち

98
00:05:05,040 --> 00:05:07,050
現在持っています。

99
00:05:07,050 --> 00:05:07,990
>> それでは始めましょう。

100
00:05:07,990 --> 00:05:10,890
ここで、再び、ある一般的なこと
フォームの関数宣言

101
00:05:10,890 --> 00:05:13,980
エンキューは次のように見えるかもしれません何のために。

102
00:05:13,980 --> 00:05:14,910
そしてここで私達は行きます。

103
00:05:14,910 --> 00:05:18,335
番号をエンキューしてみましょう
キューに28。

104
00:05:18,335 --> 00:05:19,460
だから、私たちは何をするつもりですか？

105
00:05:19,460 --> 00:05:23,390
さて、私たちのキューの先頭です
0、と私たちのキューのサイズで

106
00:05:23,390 --> 00:05:29,680
0であり、私たちはおそらく入れたいです
配列の要素数の数28

107
00:05:29,680 --> 00:05:31,124
0、右？

108
00:05:31,124 --> 00:05:32,540
だから我々は今、そこにいることを配置しました。

109
00:05:32,540 --> 00:05:34,820
だから今私たちは、変更する必要がありますか？

110
00:05:34,820 --> 00:05:37,090
我々は変更する必要はありません
キューの先頭、

111
00:05:37,090 --> 00:05:40,850
私たちはどのような要素を知りたいので、
我々は、後でデキューする必要があるかもしれません。

112
00:05:40,850 --> 00:05:44,020
私たちはフロントそこに持っているそうな理由
何の指標の一種であります

113
00:05:44,020 --> 00:05:46,439
配列内の最も古いもの。

114
00:05:46,439 --> 00:05:49,730
まあarray--で最も古いもので
実際、配列内の唯一のものは、右

115
00:05:49,730 --> 00:05:53,540
now--である、28であり、
アレイ位置0で。

116
00:05:53,540 --> 00:05:56,160
だから我々はしたくありません
、その緑の番号を変更します

117
00:05:56,160 --> 00:05:57,910
なぜならそれは最古要素です。

118
00:05:57,910 --> 00:06:00,510
むしろ、我々は、サイズを変更したいです。

119
00:06:00,510 --> 00:06:04,110
したがって、この場合には、我々はよ
1のサイズを増加します。

120
00:06:04,110 --> 00:06:08,430
>> 考え方の今一般的なソート
次の要素はキューに行くために起こっています

121
00:06:08,430 --> 00:06:12,310
これらの2つの数値を追加することです
一緒に、フロントとサイズ、

122
00:06:12,310 --> 00:06:16,390
それはどこにあなたの隣に教えてあげましょう
キュー内の要素は、行くために起こっています。

123
00:06:16,390 --> 00:06:18,130
だから今のは、別の番号をエンキューしましょう​​。

124
00:06:18,130 --> 00:06:20,250
33をエンキューしてみましょう。

125
00:06:20,250 --> 00:06:24,480
だから33は、に行くために起こっています
アレイ位置0と1。

126
00:06:24,480 --> 00:06:26,840
したがって、この場合には、それが起こっています
アレイ位置1に移動するには、

127
00:06:26,840 --> 00:06:29,500
そして今、私たちのキューのサイズは2です。

128
00:06:29,500 --> 00:06:31,840
>> 繰り返しますが、私たちは変化していません
私たちの待ち行列の先頭、

129
00:06:31,840 --> 00:06:34,730
28はまだあるので、
最古要素と、我々

130
00:06:34,730 --> 00:06:38,220
我々は最終的に得るときto--たい
要素を削除、デキューへ

131
00:06:38,220 --> 00:06:43,300
このキューから、我々が知りたいです
ここで、最も古い要素です。

132
00:06:43,300 --> 00:06:48,620
そして、私たちは常に維持する必要があります
それがどこにあるのいくつかの指標。

133
00:06:48,620 --> 00:06:50,410
だから、0がためにそこにあるものです。

134
00:06:50,410 --> 00:06:52,910
それはフロントがためにそこにあるものです。

135
00:06:52,910 --> 00:06:55,022
>> エンキュー中のもう一つの要素、19をしてみましょう。

136
00:06:55,022 --> 00:06:56,980
私はあなたが推測することができると確信してい
どこに19に行くために起こっています。

137
00:06:56,980 --> 00:06:59,860
これは、に行くために起こっています
アレイの位置番号2。

138
00:06:59,860 --> 00:07:01,570
それは0プラス2です。

139
00:07:01,570 --> 00:07:03,199
そして今、私たちのキューのサイズは3です。

140
00:07:03,199 --> 00:07:04,240
私たちはその中に3つの要素を持っています。

141
00:07:04,240 --> 00:07:08,490
だから我々はしていた、と私たちはつもりはない場合
今まで、別の要素をエンキュー、

142
00:07:08,490 --> 00:07:11,370
それは配列の場所に行くだろう
数3、および当社のキューのサイズ

143
00:07:11,370 --> 00:07:13,160
4になります。

144
00:07:13,160 --> 00:07:15,279
だから我々は今、いくつかの要素を待ち行列に入れてきました。

145
00:07:15,279 --> 00:07:16,570
今度は、それらを削除するために始めましょう。

146
00:07:16,570 --> 00:07:19,450
キューからデキューしてみましょう。

147
00:07:19,450 --> 00:07:23,340
>> ソートされており、ポップに非常に類似しました
スタックのために、このアナログの、

148
00:07:23,340 --> 00:07:26,180
デキューは受け入れる必要があります
再びqueue--へのポインタ、

149
00:07:26,180 --> 00:07:28,140
しない限り、それがグローバルに宣言です。

150
00:07:28,140 --> 00:07:31,610
今、私たちは場所を変更します
キューの先頭の。

151
00:07:31,610 --> 00:07:35,050
それは一種の出番です
プレイには、その前の変数、

152
00:07:35,050 --> 00:07:37,310
我々は削除すると理由
要素、私たちが望みます

153
00:07:37,310 --> 00:07:40,720
次に古い要素に移動します。

154
00:07:40,720 --> 00:07:44,180
>> その後、我々は減少します
キューのサイズ、

155
00:07:44,180 --> 00:07:47,130
し、我々は値を返すようにしたいです
それをキューから除去しました。

156
00:07:47,130 --> 00:07:48,921
繰り返しますが、私たちはそれを廃棄する必要はありません。

157
00:07:48,921 --> 00:07:51,170
我々は、おそらく抽出されています
それ私たちがしているqueue--から

158
00:07:51,170 --> 00:07:54,170
我々はそれを気にするので、それをキューから取り出します。

159
00:07:54,170 --> 00:08:01,080
だから我々は、この関数が返すようにしたいです
タイプ値のデータ要素。

160
00:08:01,080 --> 00:08:04,360
再び、この場合、値は整数です。

161
00:08:04,360 --> 00:08:05,670
>> だから今のは何かをデキューしましょう​​。

162
00:08:05,670 --> 00:08:09,310
キューから要素を削除してみましょう。

163
00:08:09,310 --> 00:08:15,970
私たちが言う場合はint型xが等しい＆Q、アンパサンドq--
もう一度このQデータへのポインタです

164
00:08:15,970 --> 00:08:20,177
structure--何要素
デキューされようとしていますか？

165
00:08:20,177 --> 00:08:23,840

166
00:08:23,840 --> 00:08:29,480
この場合には、最初であるため
、の最初のデータ構造、FIFOうち、

167
00:08:29,480 --> 00:08:33,690
私たちはこの中に入れ、まず
キューは28であったので、この場合には、

168
00:08:33,690 --> 00:08:37,245
我々は外に28を取るつもりです
何であるキューではなく、19、

169
00:08:37,245 --> 00:08:38,870
これがスタックした場合、我々は行っているだろう。

170
00:08:38,870 --> 00:08:42,220
私たちは、キューから28を取るつもりです。

171
00:08:42,220 --> 00:08:44,960
>> 私たちがやったことと同様に
スタックは、我々は実際にはありませんよ

172
00:08:44,960 --> 00:08:47,345
28を削除しようとして
キュー自体から、

173
00:08:47,345 --> 00:08:49,470
私達はちょうど種類になるだろう
それがないふりをします。

174
00:08:49,470 --> 00:08:51,678
だから、そこに滞在するつもりです
メモリに、私たちはただです

175
00:08:51,678 --> 00:08:57,820
種の移動によってそれを無視しようとして
我々のQデータの他の二つのフィールド

176
00:08:57,820 --> 00:08:58,830
構造。

177
00:08:58,830 --> 00:09:00,230
私たちは前を変更しようとしています。

178
00:09:00,230 --> 00:09:04,290
Q.frontは今に起こっています
それが今であるため、1であります

179
00:09:04,290 --> 00:09:07,740
私たちは私たちの中に持っている最古要素
キュー、我々はすでに28を削除したので、

180
00:09:07,740 --> 00:09:10,460
これはかつての最古要素でした。

181
00:09:10,460 --> 00:09:13,540
>> そして今、我々は、変更したいです
キューのサイズ

182
00:09:13,540 --> 00:09:15,780
二つの要素の代わりに、3。

183
00:09:15,780 --> 00:09:20,450
今覚え以前私が言ったとき、私たち
キューに要素を追加したいです、

184
00:09:20,450 --> 00:09:26,000
我々は、アレイの場所にそれを置きます
これはフロントとサイズの合計です。

185
00:09:26,000 --> 00:09:29,050
したがって、この場合には、我々はまだ入れています
これは、キュー内の次の要素、

186
00:09:29,050 --> 00:09:33,360
アレイ位置3、およびへ
我々は、第二​​のそれが表示されます。

187
00:09:33,360 --> 00:09:35,730
>> だから我々は今、私たちをデキューしました
キューから最初の要素。

188
00:09:35,730 --> 00:09:36,480
それでは、再びそれをやってみましょう。

189
00:09:36,480 --> 00:09:38,696
のは、別のものを削除してみましょう
キューから要素。

190
00:09:38,696 --> 00:09:42,400
場合は、現在最も古いです
要素は、アレイ位置1です。

191
00:09:42,400 --> 00:09:44,220
それはq.frontを教えてくれるものです。

192
00:09:44,220 --> 00:09:46,980
つまり、緑色のボックスには、ことを教えてくれる
それは最古の要素です。

193
00:09:46,980 --> 00:09:49,310
だから、xは33になります。

194
00:09:49,310 --> 00:09:52,130
私達はちょうど種類の忘れてしまいます
33が配列に存在することを、

195
00:09:52,130 --> 00:09:55,100
私たちは今、それを言いますよ
キュー内の新しい最古要素

196
00:09:55,100 --> 00:09:58,900
アレイ位置2、およびサイズ​​であります
要素のキューの数

197
00:09:58,900 --> 00:10:02,152
我々は、キューに、1である必要があります。

198
00:10:02,152 --> 00:10:05,110
今度は、何かをエンキューしましょう​​、と私
ソートの第二の前にこれを譲りました、

199
00:10:05,110 --> 00:10:10,340
しかし、我々はに40を配置する場合
キュー、40は行くために起こっていることは？

200
00:10:10,340 --> 00:10:12,880

201
00:10:12,880 --> 00:10:17,730
さて、私たちはそれを入れてきました
q.frontプラスキューサイズで、

202
00:10:17,730 --> 00:10:20,850
ので、それは理にかなって
実際にここで40を配置します。

203
00:10:20,850 --> 00:10:22,840
今でていることがわかり
いくつかのポイントは、我々が行っています

204
00:10:22,840 --> 00:10:27,980
の最後に取得します
qの内側に私たちの配列、

205
00:10:27,980 --> 00:10:32,010
それは28をフェードアウトと33--
彼らは技術的には、実際にしています

206
00:10:32,010 --> 00:10:33,300
オープンスペース、右？

207
00:10:33,300 --> 00:10:36,040
だから、私たちはeventually--あり
追加のルール

208
00:10:36,040 --> 00:10:40,390
これら二つのtogether--我々は最終的によいです
容量の大きさによって、MODに必要

209
00:10:40,390 --> 00:10:41,410
私たちは周りにラップすることができます。

210
00:10:41,410 --> 00:10:43,620
>> だから我々は、要素を取得する場合
数10、我々はしている場合

211
00:10:43,620 --> 00:10:48,790
要素数10でそれを置き換える、私たちはいただきたいです
実際には配列の位置0に入れます。

212
00:10:48,790 --> 00:10:50,997
そして、我々はするつもりだった場合
アレイは、恐れ入りますlocation--、

213
00:10:50,997 --> 00:10:53,080
私たちは一緒にそれらを追加した場合、
私たちは数になりました

214
00:10:53,080 --> 00:10:56,330
私たちが入れなければならないであろう場所11は次のようになります
このarray--に存在しないこと、

215
00:10:56,330 --> 00:10:58,200
それが範囲外に行くことになります。

216
00:10:58,200 --> 00:11:03,367
私たちは10で国防省と入れることができます
そのアレイ位置1インチ

217
00:11:03,367 --> 00:11:04,450
だから、キューがどのように動作するかです。

218
00:11:04,450 --> 00:11:08,540
彼らは常に左から行くつもりです
おそらく右に折り返します。

219
00:11:08,540 --> 00:11:11,280
そして、あなたは彼らがしていることを知っています
フルサイズの場合、赤いボックスこと、

220
00:11:11,280 --> 00:11:13,710
容量に等しくなります。

221
00:11:13,710 --> 00:11:16,720
そして、我々は40を追加したので、後
キュー、よく私たちは何をする必要がありますか？

222
00:11:16,720 --> 00:11:19,890
まあ、最古要素
キューに、まだ19であります

223
00:11:19,890 --> 00:11:21,990
私たちは変更したくありません
キューの先頭、

224
00:11:21,990 --> 00:11:23,820
しかし今、私た​​ちは2を持っています
キュー内の要素、

225
00:11:23,820 --> 00:11:28,710
そして私たちは増やしたいです
1から2への我々のサイズ。

226
00:11:28,710 --> 00:11:31,820
>> それはかなりそれでです
アレイベースのキューでの作業、

227
00:11:31,820 --> 00:11:33,630
スタックと同様に、
方法もあります

228
00:11:33,630 --> 00:11:36,450
リンクリストとしてキューを実装します。

229
00:11:36,450 --> 00:11:40,150
ここで、このデータ構造タイプがあれば
あなたに見慣れ、それはあります。

230
00:11:40,150 --> 00:11:43,780
それは、単独でリンクされたリストではありません
それは二重にリンクされたリストです。

231
00:11:43,780 --> 00:11:46,790
そして今、余談として、それは
実装が実際に可能

232
00:11:46,790 --> 00:11:50,160
単独でリンクされたリストとしてキューが、
私は、可視化の観点から考えます

233
00:11:50,160 --> 00:11:53,350
それが実際に表示するために役立つかもしれません
二重リンクリストとして、この。

234
00:11:53,350 --> 00:11:56,850
しかし、それは間違いなくに可能です
単独でリンクリストとしてこれを行います。

235
00:11:56,850 --> 00:12:00,110
>> それでは、見てみましょう
何これは、次のようになります。

236
00:12:00,110 --> 00:12:02,750
我々はenquue--したい場合
今、再び私たちがしています

237
00:12:02,750 --> 00:12:05,360
リンクリストへの切り替え
こちらのモデルに基づきます。

238
00:12:05,360 --> 00:12:08,420
私たちがエンキューしたい場合は、我々はしたいです
よく、新しい要素を追加します

239
00:12:08,420 --> 00:12:09,730
私たちは何をする必要がありますか？

240
00:12:09,730 --> 00:12:12,770
すべての最初の、まあ、理由
我々は最後に追加しています

241
00:12:12,770 --> 00:12:15,520
から削除
おそらく我々、始まります

242
00:12:15,520 --> 00:12:20,050
両方へのポインタを維持したいです
頭とリンクリストのテール？

243
00:12:20,050 --> 00:12:22,660
テールのための別の用語であること
リンクリストの最後に、

244
00:12:22,660 --> 00:12:24,496
リンクリストの最後の要素。

245
00:12:24,496 --> 00:12:26,620
そして、これらはおそらく意志、
再び、私たちに有益です

246
00:12:26,620 --> 00:12:28,477
彼らはグローバル変数である場合。

247
00:12:28,477 --> 00:12:31,060
しかし、今、我々は新しいを追加する場合
要素我々が何をすべきかを持っているのですか？

248
00:12:31,060 --> 00:12:35,262
私たちはただ[？ malak？]または動的
自分のために私たちの新しいノードを割り当てます。

249
00:12:35,262 --> 00:12:38,220
私たちはいずれかを追加するときそして、同じように
二重リンクリストたちの要素、

250
00:12:38,220 --> 00:12:40,410
ただof--ソートする必要があり
ここでこれらの最後の3つの手順

251
00:12:40,410 --> 00:12:43,330
ただ、すべての移動についてです
正しい方法でポインタ

252
00:12:43,330 --> 00:12:46,710
要素がに追加されるように、
チェーンを壊すことなくチェーン

253
00:12:46,710 --> 00:12:49,580
または間違いのいくつかの並べ替えを行います
または事故のいくつかの並べ替えを持ちます

254
00:12:49,580 --> 00:12:54,505
それによって私たちは偶然に起こります
私たちのキューのいくつかの要素を孤立。

255
00:12:54,505 --> 00:12:55,880
ここでは、これがどのように見えるかです。

256
00:12:55,880 --> 00:13:00,980
私たちは、要素を追加したいです
このキューの最後に10。

257
00:13:00,980 --> 00:13:03,380
ここだから最古要素
ヘッドによって表されます。

258
00:13:03,380 --> 00:13:06,800
それは我々が最初に入れてのことです
ここで、この仮想的なキューに。

259
00:13:06,800 --> 00:13:10,430
そして尾​​、13は、最もあり
最近追加された要素。

260
00:13:10,430 --> 00:13:17,030
そして、私たちはに10をエンキューする場合
このキューは、我々は13の後にそれを載せていきたいと思います。

261
00:13:17,030 --> 00:13:19,860
そして、私たちは、動的にするつもりです
新しいノード用の領域​​を割り当てます

262
00:13:19,860 --> 00:13:23,280
そして、確認するためにnullをチェックします
我々は、メモリ障害を持っていません。

263
00:13:23,280 --> 00:13:27,040
その後、我々はするつもりです
そのノードに10を配置し、

264
00:13:27,040 --> 00:13:30,030
そして今、我々は注意する必要があります
我々はポインタを整理する方法について

265
00:13:30,030 --> 00:13:32,180
私たちはチェーンに不具合が発生していません。

266
00:13:32,180 --> 00:13:38,910
>> 私たちは10の前のフィールドを設定することができます
古い尾に戻って指すように、

267
00:13:38,910 --> 00:13:41,620
そして'10以降となります
ある時点で新しい尾

268
00:13:41,620 --> 00:13:44,459
これらのすべての時間によって
チェーンが接続され、

269
00:13:44,459 --> 00:13:46,250
何も来るつもりないです
10後の今。

270
00:13:46,250 --> 00:13:49,880
だから10の次のポインタ
ヌルを指すようになります、

271
00:13:49,880 --> 00:13:53,580
私たちがした後、その後、我々は、これを実行した後、
チェーンに後方10を接続し、

272
00:13:53,580 --> 00:13:57,780
我々は古い頭、または、言い訳を取ることができます
私は、キューの古い尾。

273
00:13:57,780 --> 00:14:02,980
キューの古い終わり、
13、それは10を指して作ります。

274
00:14:02,980 --> 00:14:08,220
そして今、この時点で、私たちは持っています
このキューに数10をエンキュー。

275
00:14:08,220 --> 00:14:14,740
私たちが今やらなければならないことは、単に移動されます
10の代わりに13を指すようにテール。

276
00:14:14,740 --> 00:14:17,630
>> デキューは実際にあります
ポップと非常によく似て

277
00:14:17,630 --> 00:14:21,710
あるスタックから
リンクリストとして実装

278
00:14:21,710 --> 00:14:24,040
あなたはスタックのビデオを見てきた場合。

279
00:14:24,040 --> 00:14:27,280
私たちがやらなければならないことは、時開始です
始まり、二番目の要素を見つけ、

280
00:14:27,280 --> 00:14:30,480
最初の要素を解放し、
して、ヘッドを移動

281
00:14:30,480 --> 00:14:32,930
二番目の要素を指すように。

282
00:14:32,930 --> 00:14:37,920
おそらくより良い、それを可視化するために
ちょうどそれについて余分明確にすること。

283
00:14:37,920 --> 00:14:39,230
だからここに私たちのキューが再びです。

284
00:14:39,230 --> 00:14:42,600
12は最も古い要素であります
私たちの待ち行列で、頭。

285
00:14:42,600 --> 00:14:46,210
10は、最新の要素であります
私たちのキューで、私たちの尾。

286
00:14:46,210 --> 00:14:49,310
>> そして、私たちがしたいとき
要素をデキューするために、

287
00:14:49,310 --> 00:14:52,202
私たちは最も古い要素を削除します。

288
00:14:52,202 --> 00:14:52,910
だから我々は何をしますか？

289
00:14:52,910 --> 00:14:55,243
さて、私たちはトラバーサルポインタを設定
それが頭から始まり、

290
00:14:55,243 --> 00:14:57,840
それように、我々はそれを動かします
二番目の要素を指します

291
00:14:57,840 --> 00:15:02,290
このTRAVを言って何かをqueue--
TRAVは、次の矢印等しく、例えば、

292
00:15:02,290 --> 00:15:07,170
を指すようにそこTRAVを移動します
私たちは12をデキューした後、15、

293
00:15:07,170 --> 00:15:13,030
私たちは12を削除した後や、意志
当時の最古要素となります。

294
00:15:13,030 --> 00:15:16,360
>> 今、私たちは最初にホールドを持っています
ポインタヘッドを介した要素

295
00:15:16,360 --> 00:15:19,440
第2要素
ポインタTRAV経由。

296
00:15:19,440 --> 00:15:25,170
私たちは今、自由に頭をすることができますし、我々はできます
何ももう15前に来ないと言います。

297
00:15:25,170 --> 00:15:29,990
だから我々は15の以前の変更することができます
ポインタがNULLを指すように、

298
00:15:29,990 --> 00:15:31,874
そして、私たちは頭を上に移動。

299
00:15:31,874 --> 00:15:32,540
そして、そこに私達は行きます。

300
00:15:32,540 --> 00:15:35,840
今、我々が正常に持っています
12をデキューし、今、私たちは

301
00:15:35,840 --> 00:15:39,180
4つの要素の別のキューを持っています。

302
00:15:39,180 --> 00:15:41,700
それはほとんどすべてです
キューにあり、

303
00:15:41,700 --> 00:15:45,810
アレイベースとリンクされたリストの両方がベース。

304
00:15:45,810 --> 00:15:46,860
私はダグロイドです。

305
00:15:46,860 --> 00:15:49,100
これは、CS 50です。

306
00:15:49,100 --> 00:15:50,763