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

2
00:00:05,204 --> 00:00:07,370
Дъг 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
Подобно на комин,
имаме две операции

31
00:01:36,190 --> 00:01:38,470
че можем да се извърши по опашки.

32
00:01:38,470 --> 00:01:43,910
Имената са Enqueue, която е да се добави
нов елемент към края на опашката,

33
00:01:43,910 --> 00:01:47,330
и dequeue, което е
за да се отстрани най-старите

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
Така че с Enqueue, това е като към
края, отстраняване от предната.

40
00:02:07,570 --> 00:02:10,639
Така че най-старото нещо там
Винаги е следващото нещо,

41
00:02:10,639 --> 00:02:13,620
да излезе, ако се опитаме
и dequeue нещо.

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
така че ние знаем кой елемент
ние искаме да dequeue,

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
И малко по-объркващо, аз реших
да наричаме тази опашка р, буквата

68
00:03:35,350 --> 00:03:38,090
р вместо тип данни р на.

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
Тя съдържа три членове или три
полета, масив от размера КАПАЦИТЕТ.

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
>> Така че първата операция можем
изпълнява е да Enqueue нещо,

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
Ами тази функция Enqueue нужди
да приеме указател към нашата опашка.

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
Това е елемент, което искаме да Enqueue,
искаме да добавим към края на опашката.

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
за това, което Enqueue може да изглежда така.

102
00:05:13,980 --> 00:05:14,910
И ето го.

103
00:05:14,910 --> 00:05:18,335
Нека Enqueue броя
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
защото искаме да знаем какво елемент
ние може да се наложи да dequeue късно.

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
е да добавите тези две числа
заедно, предни и размер,

122
00:06:12,310 --> 00:06:16,390
и че ще ви кажа, когато на следващия
елемент в опашката е да отиде.

123
00:06:16,390 --> 00:06:18,130
Така че сега нека Enqueue друг номер.

124
00:06:18,130 --> 00:06:20,250
Нека Enqueue 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-- когато ние в крайна сметка се получи
да dequeuing, премахване на елементи

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
>> Нека в Enqueue още един елемент, 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
Така че, ако бяхме да, и ние няма
до момента, Enqueue друг елемент,

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
Така че ние сме enqueued няколко елемента сега.

145
00:07:15,279 --> 00:07:16,570
Сега нека да започнем да ги премахнете.

146
00:07:16,570 --> 00:07:19,450
Нека да ги dequeue от опашката.

147
00:07:19,450 --> 00:07:23,340
>> Така че подобно на поп, който е нещо като
на аналог на тази за купчини,

148
00:07:23,340 --> 00:07:26,180
dequeue трябва да приеме
указател към 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
тя dequeuing, защото ни е грижа за него.

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
>> Така че сега нека dequeue нещо.

162
00:08:05,670 --> 00:08:09,310
Нека да премахнете елемент от опашката.

163
00:08:09,310 --> 00:08:15,970
Ако кажем, инт х равнява & Q, амперсанд q--
отново, че е указател към този р данни

164
00:08:15,970 --> 00:08:20,177
structure-- какво елемент
ще се dequeued?

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
Ще вид го игнорира, като движите
другите две области на нашия р данни

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
до два елемента, вместо три.

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
>> Така че ние сега сме dequeued ни
първи елемент от опашката.

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
И така, х ще стане 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
Сега нека Enqueue нещо, и аз
нещо като даде това далеч преди една секунда,

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
за да стигнем до края на
нашата масив във вътрешността на р,

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
но сега имаме два
елементи в опашката,

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
Ако искаме да Enqueue, искаме
да се добави нов елемент, добре

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
Това, което ние просто [? Малък?] или динамично
разпредели нашия нов възел за себе си.

249
00:12:35,262 --> 00:12:38,220
И тогава, точно както когато ние добавяме всеки
елемент за двойно свързан списък, ние,

250
00:12:38,220 --> 00:12:40,410
Просто трябва да се справи of--
тези последните три стъпки тук

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
И така, ако искаме да Enqueue 10 в
тази опашка, ние искаме да го кажем след 13.

261
00:13:17,030 --> 00:13:19,860
И така, ние ще динамично
разпредели пространство за нов възел

262
00:13:19,860 --> 00:13:23,280
и се проверява за нищожна да се уверите,
ние нямаме недостатъчност с памет.

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
И сега, в този момент, ние имаме
enqueued броя 10 в тази опашка.

275
00:14:08,220 --> 00:14:14,740
Всичко, което трябва да направим сега, е просто придвижете
опашката да сочи към 10 вместо до 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing е всъщност
много подобен на мак

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
>> И така, когато искаме
да dequeue елемент,

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
на този queue-- нещо като казва Trav
равнява Trav стрелката, например,

292
00:15:02,290 --> 00:15:07,170
ще се движат Trav там, за да сочи към
15, които, след като сме dequeue 12,

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
и вторият елемент
чрез TRAV показалка.

296
00:15:19,440 --> 00:15:25,170
Ние вече могат свободно главата, а след това можем да
казват нищо не идва преди 15 вече.

297
00:15:25,170 --> 00:15:29,990
Така че ние можем да променим 15 на предишния
указател да сочи към нула,

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
Сега имаме успешно
dequeued 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