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
>> В отличие от стека, который
это структура ЛИФО,

13
00:00:36,590 --> 00:00:45,610
последний пришел, первый, очереди 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
Имена поставить в очередь, которая является добавление
новый элемент в конец очереди,

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
Так что с Enqueue, это добавление к
конец, удаляя с фронта.

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
есть это ограничение, что С рода
из навязывает нам, что мы

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
д вместо типа данных д.

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
мы вкладываем в 0s этих областях.

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

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
хочу, целью которых, когда мы в конечном итоге получить
чтобы извлечение из очереди, удаление элементов

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
Это плюс 2 0.

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 х равен & 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
собирается рода игнорируют его, перемещая
другие два поля нашего кв данных

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
>> Таким образом, мы в настоящее время из очереди нашей
Первый элемент из очереди.

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
Теперь давайте в очередь что-то, и я
вроде дал это далеко секунду назад,

199
00:10:05,110 --> 00:10:10,340
но если мы хотим, чтобы положить 40 Into The
Очередь, где это 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-- мы в конечном итоге может
нужно мод размером емкости

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
Если мы хотим, чтобы поставить в очередь, мы хотим
чтобы добавить новый элемент, а

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
И поэтому, если мы хотим, чтобы поставить в очередь 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
А теперь, в этот момент, у нас есть
в очередь число 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
это что-то queue-- говоря TRAV
Trav равна стрелку рядом, например,

292
00:15:02,290 --> 00:15:07,170
будет двигаться TRAV есть, чтобы указать на
15, которая, после того как мы из очереди 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
Теперь у нас есть успешно
из очереди 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