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