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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Więc jeśli masz
oglądałem film na stosie,

3
00:00:07,370 --> 00:00:09,870
jest to prawdopodobnie będzie czuć się
jak trochę deja vu.

4
00:00:09,870 --> 00:00:13,850
To będzie bardzo podobnej koncepcji,
tylko z lekkim akcentem na jej temat.

5
00:00:13,850 --> 00:00:15,530
Mamy zamiar rozmawiać teraz o kolejkach.

6
00:00:15,530 --> 00:00:19,350
Tak kolejka podobny do stosu
jest inny rodzaj struktury danych

7
00:00:19,350 --> 00:00:22,412
że możemy użyć, aby utrzymać
dane w sposób zorganizowany.

8
00:00:22,412 --> 00:00:24,120
Podobnie jak w przypadku stosu
może to być realizowane

9
00:00:24,120 --> 00:00:27,000
jako tablica lub połączonej listy.

10
00:00:27,000 --> 00:00:30,320
W przeciwieństwie do stosu, zasady
używamy, aby określić

11
00:00:30,320 --> 00:00:34,210
Kiedy robi się dodawane i usuwane z
kolejki są nieco inne.

12
00:00:34,210 --> 00:00:36,590
>> W przeciwieństwie do stosu, który
jest strukturą LIFO,

13
00:00:36,590 --> 00:00:45,610
trwać, pierwsze wyszło, kolejka jest FIFO
Struktura, FIFO, pierwsze weszło, pierwsze wyszło.

14
00:00:45,610 --> 00:00:49,320
Teraz kolejek, prawdopodobnie
mają analogię do kolejek.

15
00:00:49,320 --> 00:00:52,820
Jeśli kiedykolwiek byłeś w kolejce
park rozrywki lub w banku,

16
00:00:52,820 --> 00:00:56,430
jest swego rodzaju uczciwości
wdrożenie struktury.

17
00:00:56,430 --> 00:00:59,160
Pierwsza osoba w kolejce
bank jest pierwszą osobą,

18
00:00:59,160 --> 00:01:00,760
kto może mówić do kasjera.

19
00:01:00,760 --> 00:01:03,522
>> Byłoby to coś w rodzaju wyścigu
części dolnej, jeśli jedynym sposobem

20
00:01:03,522 --> 00:01:06,730
masz mówić do kasjera
Bank miał być ostatnią osobą w kolejce.

21
00:01:06,730 --> 00:01:09,146
Wszyscy zawsze chcą
być ostatnią osobą w kolejce,

22
00:01:09,146 --> 00:01:12,580
a osoba, która była tam pierwszy
którzy czekali na chwilę,

23
00:01:12,580 --> 00:01:14,715
może być tam przez kilka godzin,
i godziny, a godzina

24
00:01:14,715 --> 00:01:17,590
przed mają szansę rzeczywiście
wycofania pieniędzy w banku.

25
00:01:17,590 --> 00:01:22,510
A więc kolejki są sortowania
rzetelność realizacji struktury.

26
00:01:22,510 --> 00:01:25,780
Ale to nie musi oznaczać,
że stosy są złe, po prostu

27
00:01:25,780 --> 00:01:28,160
że kolejki są kolejnym sposobem, aby to zrobić.

28
00:01:28,160 --> 00:01:32,420
Więc znowu kolejka jest pierwsze weszło, pierwsze
się, w stosunku do stosu, który trwał w,

29
00:01:32,420 --> 00:01:34,440
pierwsze wyszło.

30
00:01:34,440 --> 00:01:36,190
Podobnie jak w przypadku stosu
mamy dwie operacje

31
00:01:36,190 --> 00:01:38,470
które możemy wykonać na kolejkach.

32
00:01:38,470 --> 00:01:43,910
Nazwy są enqueue, która jest dodanie
Nowym elementem na końcu w kolejce,

33
00:01:43,910 --> 00:01:47,330
oraz z kolejki, która jest
usunąć najstarszy

34
00:01:47,330 --> 00:01:49,670
Element z przodu kolejki.

35
00:01:49,670 --> 00:01:53,600
Tak więc mamy zamiar dodać elementy
na koniec kolejki

36
00:01:53,600 --> 00:01:57,220
i jedziemy do usunięcia elementów
od przodu kolejki.

37
00:01:57,220 --> 00:02:00,790
Ponownie, ze stosem, byliśmy dodanie
Elementy do szczytu stosu

38
00:02:00,790 --> 00:02:03,380
i usuwanie elementów
ze szczytu stosu.

39
00:02:03,380 --> 00:02:07,570
Więc z Kolejkuj, to dodanie do
końcem, usuwając z przodu.

40
00:02:07,570 --> 00:02:10,639
Więc coś w najstarszej tam
zawsze jest następna rzecz

41
00:02:10,639 --> 00:02:13,620
wyjdzie, jeśli spróbujemy
i dequeue coś.

42
00:02:13,620 --> 00:02:18,330
>> Więc jeszcze raz, z kolejkami, możemy
implementacje oparte na tablicy

43
00:02:18,330 --> 00:02:20,110
i połączone listę opartą implementacje.

44
00:02:20,110 --> 00:02:24,620
Zaczniemy ponownie
implementacje oparte na tablicy.

45
00:02:24,620 --> 00:02:27,070
Definicja struktury
wygląda dość podobnie.

46
00:02:27,070 --> 00:02:30,720
Mamy kolejną tablicę
nie wartości typu danych,

47
00:02:30,720 --> 00:02:32,690
więc może posiadać dowolne typy danych.

48
00:02:32,690 --> 00:02:35,570
Jesteśmy znowu będziemy używać
całkowitymi w tym przykładzie.

49
00:02:35,570 --> 00:02:39,830
>> I tak jak z naszym
Realizacja Stos układów opartych na

50
00:02:39,830 --> 00:02:42,340
dlatego, że używasz
tablica, z konieczności

51
00:02:42,340 --> 00:02:46,850
mają to ograniczenie, że C rodzaju
od wymusza na nas, co my

52
00:02:46,850 --> 00:02:51,670
nie mają żadnego dynamizmu w naszym
zdolność do wzrostu i kurczyć tablicę.

53
00:02:51,670 --> 00:02:55,710
Musimy zdecydować, na początku
co jest maksymalną liczbą rzeczy

54
00:02:55,710 --> 00:02:59,300
że możemy umieścić w tym
Kolejka, w tym przypadku,

55
00:02:59,300 --> 00:03:02,070
Pojemność byłoby niektóre funta
zdefiniowane stałe w naszym kodzie.

56
00:03:02,070 --> 00:03:05,430
I dla celów tego
wideo, pojemność będzie 10.

57
00:03:05,430 --> 00:03:07,690
>> Musimy śledzić
przód kolejki

58
00:03:07,690 --> 00:03:11,160
więc wiemy, jaki element
chcemy z kolejki,

59
00:03:11,160 --> 00:03:15,070
i musimy również śledzić
coś else-- liczbę elementów

60
00:03:15,070 --> 00:03:16,690
że mamy w naszej kolejki.

61
00:03:16,690 --> 00:03:19,360
Zauważ, że nie jesteśmy śledzenie
Na koniec w kolejce, tak

62
00:03:19,360 --> 00:03:21,150
wielkość kolejki.

63
00:03:21,150 --> 00:03:24,310
A powodem, który, miejmy nadzieję,
stać się nieco jaśniejsze w jednej chwili.

64
00:03:24,310 --> 00:03:26,143
Kiedy zakończyliśmy
to definicja typu,

65
00:03:26,143 --> 00:03:29,080
mamy nowy typ danych
nazywa kolejki, które możemy teraz

66
00:03:29,080 --> 00:03:30,630
deklarować zmienne tego typu danych.

67
00:03:30,630 --> 00:03:35,350
I nieco myląco, zdecydowałem
do wywołania tej kolejki q, list

68
00:03:35,350 --> 00:03:38,090
q zamiast typu danych q.

69
00:03:38,090 --> 00:03:39,600
>> Więc tutaj jest nasza kolejka.

70
00:03:39,600 --> 00:03:40,700
Jest to struktura.

71
00:03:40,700 --> 00:03:45,730
Zawiera ona trzy osoby lub trzy
Pola, tablica wielkości pojemności.

72
00:03:45,730 --> 00:03:47,340
W tym przypadku pojemność wynosi 10.

73
00:03:47,340 --> 00:03:49,580
A ta tablica jest
zamiar trzymać liczby całkowite.

74
00:03:49,580 --> 00:03:55,240
Na zielono jest przednia naszej kolejki,
Kolejnym elementem być usunięte, a na czerwono

75
00:03:55,240 --> 00:03:58,610
będzie wielkość kolejki
jak wiele elementów są obecnie

76
00:03:58,610 --> 00:04:01,190
istniejących w kolejce.

77
00:04:01,190 --> 00:04:05,300
Więc jeśli mówimy q.front równi
0, i wielkość q.size równa 0--

78
00:04:05,300 --> 00:04:07,120
My kładziemy 0s w tych dziedzinach.

79
00:04:07,120 --> 00:04:11,070
I w tym momencie, że jesteśmy dość dużo
gotowy do rozpoczęcia pracy z naszej kolejki.

80
00:04:11,070 --> 00:04:14,140
>> Więc pierwsza operacja możemy
wykonanie jest enqueue coś,

81
00:04:14,140 --> 00:04:16,860
aby dodać nowy element do
Koniec kolejki.

82
00:04:16,860 --> 00:04:19,089
No co trzeba
to w ogólnym przypadku?

83
00:04:19,089 --> 00:04:23,690
Cóż ta funkcja enqueue potrzeb
przyjąć wskaźnik do naszej kolejki.

84
00:04:23,690 --> 00:04:26,370
Ponownie, jeśli oświadczył
nasza kolejka na całym świecie,

85
00:04:26,370 --> 00:04:29,490
nie będzie musiał to zrobić
jest to konieczne, ale w ogóle,

86
00:04:29,490 --> 00:04:32,330
należy przyjąć wskaźniki
struktur danych

87
00:04:32,330 --> 00:04:35,040
tak, ponieważ w przeciwnym razie,
jesteśmy przechodzi value-- jesteśmy

88
00:04:35,040 --> 00:04:38,140
przekazując kopie kolejce,
i tak nie jesteśmy rzeczywiście się zmienia

89
00:04:38,140 --> 00:04:41,050
kolejka, że ​​chcemy zmienić.

90
00:04:41,050 --> 00:04:44,860
>> Inna sprawa, że ​​musi zrobić, to zaakceptować
element danych odpowiedniego typu.

91
00:04:44,860 --> 00:04:46,818
Także w tym przypadku jest
będzie całkowite,

92
00:04:46,818 --> 00:04:49,330
ale można dowolnie
zadeklarować typ danych jako wartości

93
00:04:49,330 --> 00:04:51,160
i wykorzystują to bardziej ogólnie.

94
00:04:51,160 --> 00:04:56,030
To element chcemy enqueue,
chcemy dodać na końcu kolejki.

95
00:04:56,030 --> 00:04:58,573
Wtedy rzeczywiście chcesz
umieścić te dane w kolejce.

96
00:04:58,573 --> 00:05:01,490
W tym przypadku, umieszczenie go w
prawidłowe położenie naszej tablicy,

97
00:05:01,490 --> 00:05:05,040
a następnie chcemy zmienić rozmiar
z kolejki, ile elementów mamy

98
00:05:05,040 --> 00:05:07,050
Obecnie posiadamy.

99
00:05:07,050 --> 00:05:07,990
>> Więc zaczynajmy.

100
00:05:07,990 --> 00:05:10,890
Oto znowu, że ogólnie
deklaracja funkcji formą

101
00:05:10,890 --> 00:05:13,980
za to, co enqueue może wyglądać.

102
00:05:13,980 --> 00:05:14,910
I jedziemy.

103
00:05:14,910 --> 00:05:18,335
Miejmy enqueue numer
28 do kolejki.

104
00:05:18,335 --> 00:05:19,460
Więc co zrobimy?

105
00:05:19,460 --> 00:05:23,390
Cóż, przed naszym kolejce jest
w 0 ° C, a wielkością naszego kolejki

106
00:05:23,390 --> 00:05:29,680
jest w stanie 0, a więc prawdopodobnie chcesz umieścić
liczba 28 w liczbie elementów tablicy

107
00:05:29,680 --> 00:05:31,124
0, tak?

108
00:05:31,124 --> 00:05:32,540
Więc my teraz umieszczone, że tam jest.

109
00:05:32,540 --> 00:05:34,820
Więc teraz, co musimy zmienić?

110
00:05:34,820 --> 00:05:37,090
Nie chcemy, aby zmienić
przód kolejki,

111
00:05:37,090 --> 00:05:40,850
bo chcemy wiedzieć, co elementu
Może musimy z kolejki później.

112
00:05:40,850 --> 00:05:44,020
Więc powodem mamy przodu nie
jest swego rodzaju wskaźnik, co jest

113
00:05:44,020 --> 00:05:46,439
najstarszą rzeczą w tablicy.

114
00:05:46,439 --> 00:05:49,730
Cóż najstarszą rzeczą w array-- w
Fakt, jedyną rzeczą w tablicy w prawo

115
00:05:49,730 --> 00:05:53,540
now-- wynosi 28, co jest
w miejscu tablicy 0.

116
00:05:53,540 --> 00:05:56,160
Więc nie chcę
zmienić ten numer zielony,

117
00:05:56,160 --> 00:05:57,910
dlatego, że to najstarszy elementem.

118
00:05:57,910 --> 00:06:00,510
Przeciwnie, chcemy zmienić rozmiar.

119
00:06:00,510 --> 00:06:04,110
Więc w tym przypadku, będziemy
zwiększyć rozmiar do 1.

120
00:06:04,110 --> 00:06:08,430
>> Teraz ogólny rodzaj idei, gdzie
Kolejnym elementem jest zamiar iść w kolejce

121
00:06:08,430 --> 00:06:12,310
jest dodanie tych dwóch liczb
razem, przód i wielkości,

122
00:06:12,310 --> 00:06:16,390
a powiem ci, gdzie obok
element w kolejce pójdzie.

123
00:06:16,390 --> 00:06:18,130
Więc teraz niech enqueue inny numer.

124
00:06:18,130 --> 00:06:20,250
Miejmy enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Więc 33 pójdzie do
położenie tablicy 0 oraz 1.

126
00:06:24,480 --> 00:06:26,840
Więc w tym przypadku, to będzie
, aby przejść do lokalizacji tablicy 1,

127
00:06:26,840 --> 00:06:29,500
a teraz wielkość naszej kolejce 2.

128
00:06:29,500 --> 00:06:31,840
>> Ponownie, nie zmieniamy
przód naszej kolejki,

129
00:06:31,840 --> 00:06:34,730
ponieważ 28 jest nadal
Najstarszym elementem, a my

130
00:06:34,730 --> 00:06:38,220
chcą to-- kiedy w końcu się
do usuwające wiadomości z kolejki, usuwanie elementów

131
00:06:38,220 --> 00:06:43,300
z tej kolejki, chcemy wiedzieć
gdzie najstarszym elementem jest.

132
00:06:43,300 --> 00:06:48,620
A więc zawsze należy zachować
niektóre wskaźnik, gdzie to jest.

133
00:06:48,620 --> 00:06:50,410
Więc to, co jest tam na 0.

134
00:06:50,410 --> 00:06:52,910
To, co tam jest przednia.

135
00:06:52,910 --> 00:06:55,022
>> Niech w Kolejkuj jeden element, 19.

136
00:06:55,022 --> 00:06:56,980
Jestem pewien, że można się domyślić
gdzie 19 pójdzie.

137
00:06:56,980 --> 00:06:59,860
To będzie iść do
Tablica liczba lokalizacja 2.

138
00:06:59,860 --> 00:07:01,570
To 0 plus 2.

139
00:07:01,570 --> 00:07:03,199
A teraz wielkość naszej kolejce 3.

140
00:07:03,199 --> 00:07:04,240
Mamy 3 elementy w nim.

141
00:07:04,240 --> 00:07:08,490
Więc jeśli byliśmy i nie będziemy
do teraz, enqueue kolejny element,

142
00:07:08,490 --> 00:07:11,370
byłoby to na miejscu tablicy
numer 3, a wielkość naszej kolejki

143
00:07:11,370 --> 00:07:13,160
będzie 4.

144
00:07:13,160 --> 00:07:15,279
Więc my skolejkowany teraz kilka elementów.

145
00:07:15,279 --> 00:07:16,570
Teraz zacznijmy je usunąć.

146
00:07:16,570 --> 00:07:19,450
Miejmy dequeue je z kolejki.

147
00:07:19,450 --> 00:07:23,340
>> Tak podobny do pop, która jest swego rodzaju
analogu tego dla stosów

148
00:07:23,340 --> 00:07:26,180
rozkolejkowania musi zaakceptować
wskaźnik do queue-- ponownie

149
00:07:26,180 --> 00:07:28,140
chyba to globalnie oświadczył.

150
00:07:28,140 --> 00:07:31,610
Teraz chcemy zmienić lokalizację
z przodu kolejki.

151
00:07:31,610 --> 00:07:35,050
To gdzie to rodzaj przychodzi
do gry, że zmienna z przodu,

152
00:07:35,050 --> 00:07:37,310
bo kiedy usuniemy
element, chcemy

153
00:07:37,310 --> 00:07:40,720
aby przejść do następnego najstarszego elementu.

154
00:07:40,720 --> 00:07:44,180
>> Następnie chcemy, aby zmniejszyć
wielkość kolejki

155
00:07:44,180 --> 00:07:47,130
a następnie chcemy zwrócić wartość
które zostały usunięte z kolejki.

156
00:07:47,130 --> 00:07:48,921
Ponownie, nie chcemy, aby po prostu wyrzucić.

157
00:07:48,921 --> 00:07:51,170
My prawdopodobnie wyodrębnianiu
to z queue-- jesteśmy

158
00:07:51,170 --> 00:07:54,170
usuwające wiadomości z kolejki, bo dbamy o nią.

159
00:07:54,170 --> 00:08:01,080
Dlatego chcemy, to funkcja zwraca
element danych wartości typu.

160
00:08:01,080 --> 00:08:04,360
Ponownie, w tym przypadku, wartość ta jest liczbą całkowitą.

161
00:08:04,360 --> 00:08:05,670
>> Więc teraz niech dequeue coś.

162
00:08:05,670 --> 00:08:09,310
Miejmy usunąć element z kolejki.

163
00:08:09,310 --> 00:08:15,970
Jeśli mówimy, int x równa & q, handlowe i q--
jeszcze, że jest to wskaźnik do tego q danych

164
00:08:15,970 --> 00:08:20,177
structure-- co elementem
będzie rozkolejkowywana?

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

166
00:08:23,840 --> 00:08:29,480
W tym przypadku, ponieważ jest to pierwszy
in, first out struktury danych, FIFO,

167
00:08:29,480 --> 00:08:33,690
pierwszą rzeczą, jaką wkładamy w to
kolejka 28, a więc w tym wypadku

168
00:08:33,690 --> 00:08:37,245
mamy zamiar podjąć 28 z
kolejka, a nie 19, co jest czym

169
00:08:37,245 --> 00:08:38,870
byśmy zrobili, gdyby to był stos.

170
00:08:38,870 --> 00:08:42,220
Mamy zamiar wziąć 28 z kolejki.

171
00:08:42,220 --> 00:08:44,960
>> Podobny do tego, co zrobiliśmy z
stos, nie jesteśmy w rzeczywistości

172
00:08:44,960 --> 00:08:47,345
zamierza usunąć 28
od samej kolejki

173
00:08:47,345 --> 00:08:49,470
jesteśmy po prostu się do rodzaju
z udawać, że nie ma.

174
00:08:49,470 --> 00:08:51,678
Tak to się tam
w pamięci, ale jesteśmy po prostu

175
00:08:51,678 --> 00:08:57,820
będzie rodzaj zignorować przesuwając
pozostałe dwa obszary naszej danych q

176
00:08:57,820 --> 00:08:58,830
Struktura.

177
00:08:58,830 --> 00:09:00,230
Mamy zamiar zmienić front.

178
00:09:00,230 --> 00:09:04,290
Q.front teraz będzie
za 1, bo to jest teraz

179
00:09:04,290 --> 00:09:07,740
najstarszym elementem mamy w naszym
kolejki, bo my już usunięty 28,

180
00:09:07,740 --> 00:09:10,460
który był byłym najstarszym elementem.

181
00:09:10,460 --> 00:09:13,540
>> A teraz chcemy zmienić
wielkość kolejki

182
00:09:13,540 --> 00:09:15,780
dwa elementy zamiast trzech.

183
00:09:15,780 --> 00:09:20,450
Teraz pamiętam wcześniej powiedziałem, kiedy
Aby dodać elementy do kolejki,

184
00:09:20,450 --> 00:09:26,000
umieścić go w miejscu tablicy
która jest sumą przedniej i wielkości.

185
00:09:26,000 --> 00:09:29,050
Więc w tym przypadku, jesteśmy w trakcie wdrażania
Opisz następny element w kolejce,

186
00:09:29,050 --> 00:09:33,360
w miejscu tablicy 3 oraz
zobaczymy, że w drugim.

187
00:09:33,360 --> 00:09:35,730
>> Więc my teraz rozkolejkowywana nasze
Pierwszy element z kolejki.

188
00:09:35,730 --> 00:09:36,480
Zróbmy to jeszcze raz.

189
00:09:36,480 --> 00:09:38,696
Miejmy usunąć inny
elementu z kolejki.

190
00:09:38,696 --> 00:09:42,400
W przypadku, obecny najstarszych
elementem jest lokalizacja tablicy 1.

191
00:09:42,400 --> 00:09:44,220
To, co q.front mówi nam.

192
00:09:44,220 --> 00:09:46,980
To zielone pole mówi nam, że
to jest najstarszym elementem.

193
00:09:46,980 --> 00:09:49,310
I tak, x będzie 33.

194
00:09:49,310 --> 00:09:52,130
Będziemy po prostu rodzaj zapomnieć
że 33 istnieje w tablicy,

195
00:09:52,130 --> 00:09:55,100
a my powiedzieć, że pory
Nowy najstarszy element w kolejce

196
00:09:55,100 --> 00:09:58,900
jest w miejscu tablicy 2, a wielkość
kolejki, liczba elementów

197
00:09:58,900 --> 00:10:02,152
mamy w kolejce, to 1.

198
00:10:02,152 --> 00:10:05,110
Teraz enqueue coś, a ja
Ten rodzaj dał się drugi temu

199
00:10:05,110 --> 00:10:10,340
ale jeśli chcemy umieścić 40 Into the
Kolejka, gdzie jest 40 pójdzie?

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

201
00:10:12,880 --> 00:10:17,730
Dobrze byliśmy wprowadzenie go
w q.front oraz kolejki wielkości,

202
00:10:17,730 --> 00:10:20,850
i tak ma sens
faktycznie umieścić 40 tutaj.

203
00:10:20,850 --> 00:10:22,840
Teraz zauważyć, że w
jakiś punkt, jedziemy

204
00:10:22,840 --> 00:10:27,980
aby dostać się do końca
nasza tablica wewnątrz q,

205
00:10:27,980 --> 00:10:32,010
ale wygaszone 28 i 33--
są faktycznie technicznie

206
00:10:32,010 --> 00:10:33,300
otwarte przestrzenie, prawda?

207
00:10:33,300 --> 00:10:36,040
I tak, możemy eventually--
że zasada dodawania

208
00:10:36,040 --> 00:10:40,390
te dwa together-- możemy w końcu
muszą mod o wielkości pojemności

209
00:10:40,390 --> 00:10:41,410
więc możemy owinąć wokół.

210
00:10:41,410 --> 00:10:43,620
>> Więc jeśli mamy do elementu
Numer 10, jeśli będziemy

211
00:10:43,620 --> 00:10:48,790
zastępując go w elemencie numer 10, my mieliśmy
rzeczywiście umieścić go w miejscu tablicy 0.

212
00:10:48,790 --> 00:10:50,997
A jeśli mieliśmy
Tablica miejscowość-- mi wybaczyć,

213
00:10:50,997 --> 00:10:53,080
jeśli dodaliśmy je razem,
i udało nam się liczba

214
00:10:53,080 --> 00:10:56,330
11 byłoby gdzie musimy umieścić
to, co nie występuje w tym array--

215
00:10:56,330 --> 00:10:58,200
byłoby dzieje poza granicami.

216
00:10:58,200 --> 00:11:03,367
Możemy mod przez 10 i umieścić
to w miejscu tablicy 1.

217
00:11:03,367 --> 00:11:04,450
Tak to jest, jak działa kolejki.

218
00:11:04,450 --> 00:11:08,540
Oni zawsze będzie przejść od lewej
do prawej ewentualnie zawinięcia.

219
00:11:08,540 --> 00:11:11,280
I wiesz, że są one
całości, jeżeli rozmiar, że czerwone pole,

220
00:11:11,280 --> 00:11:13,710
staje się równa pojemności.

221
00:11:13,710 --> 00:11:16,720
I tak po dodaliśmy 40 do
Kolejka, oraz co trzeba zrobić?

222
00:11:16,720 --> 00:11:19,890
Cóż, najstarszym elementem
w kolejce jest jeszcze 19,

223
00:11:19,890 --> 00:11:21,990
tak, że nie chcemy, aby zmienić
przód kolejki,

224
00:11:21,990 --> 00:11:23,820
ale teraz mamy dwa
Elementy w kolejce

225
00:11:23,820 --> 00:11:28,710
i tak chcemy zwiększyć
nasza wielkość od 1 do 2.

226
00:11:28,710 --> 00:11:31,820
>> To dość dużo go
pracy z kolejek macierzy oparte

227
00:11:31,820 --> 00:11:33,630
i podobne w stos,
jest również sposób

228
00:11:33,630 --> 00:11:36,450
zaimplementować kolejkę jako połączonej listy.

229
00:11:36,450 --> 00:11:40,150
Teraz, jeśli tego typu struktura danych
Wygląda znajomo, to jest.

230
00:11:40,150 --> 00:11:43,780
To nie jest pojedynczo związane listy,
jest to podwójnie połączonej listy.

231
00:11:43,780 --> 00:11:46,790
A teraz, na marginesie, to jest
w rzeczywistości można zrealizować

232
00:11:46,790 --> 00:11:50,160
kolejka jako pojedynczo połączonej listy, ale
Myślę, że w zakresie wizualizacji,

233
00:11:50,160 --> 00:11:53,350
to faktycznie może pomóc, aby zobaczyć
to jako podwójnie związaną listy.

234
00:11:53,350 --> 00:11:56,850
Ale to jest na pewno możliwe
zrobić to jako pojedynczo połączonej listy.

235
00:11:56,850 --> 00:12:00,110
>> Warto więc spojrzeć na
co to może wyglądać.

236
00:12:00,110 --> 00:12:02,750
Jeśli chcemy enquue--
tak i teraz znów jesteśmy

237
00:12:02,750 --> 00:12:05,360
przejście do połączonej listy
na podstawie modelu tutaj.

238
00:12:05,360 --> 00:12:08,420
Jeśli chcemy enqueue, chcemy
aby dodać nowy element, dobrze

239
00:12:08,420 --> 00:12:09,730
co musimy zrobić?

240
00:12:09,730 --> 00:12:12,770
Cóż, przede wszystkim dlatego,
dodajemy na końcu

241
00:12:12,770 --> 00:12:15,520
i usunięcie z
począwszy, prawdopodobnie

242
00:12:15,520 --> 00:12:20,050
chcą utrzymać wskaźniki do zarówno
głowa i ogon połączonej listy?

243
00:12:20,050 --> 00:12:22,660
Ogon jest inne określenie
końcem połączonym listy

244
00:12:22,660 --> 00:12:24,496
ostatni element w połączonej listy.

245
00:12:24,496 --> 00:12:26,620
A to będzie prawdopodobnie,
kolejny korzystny nas

246
00:12:26,620 --> 00:12:28,477
jeśli są zmienne globalne.

247
00:12:28,477 --> 00:12:31,060
Ale teraz, jeśli chcemy, aby dodać nowy
elementem tego, co mamy robić?

248
00:12:31,060 --> 00:12:35,262
Co nam po prostu [? Malak?] lub dynamicznie
przeznaczyć nasz nowy węzeł dla siebie.

249
00:12:35,262 --> 00:12:38,220
A potem, po prostu lubię, gdy dodamy dowolny
elementem podwójnie połączonej listy my,

250
00:12:38,220 --> 00:12:40,410
Wystarczy sortować of--
te ostatnie trzy kroki tutaj

251
00:12:40,410 --> 00:12:43,330
są po prostu wszystko o przesunięcie
wskaźniki w sposób prawidłowy

252
00:12:43,330 --> 00:12:46,710
tak, że element zostanie dodany do
łańcuch bez zerwania łańcucha

253
00:12:46,710 --> 00:12:49,580
lub co jakiś błąd
lub z jakiegoś wypadku

254
00:12:49,580 --> 00:12:54,505
zdarzyć, którym przypadkowo
sierocych niektóre elementy naszej kolejki.

255
00:12:54,505 --> 00:12:55,880
Oto, co to może wyglądać.

256
00:12:55,880 --> 00:13:00,980
Chcemy, aby dodać element
10 do końca tej kolejce.

257
00:13:00,980 --> 00:13:03,380
Więc najstarszym elementem tutaj
reprezentowany jest przez głowę.

258
00:13:03,380 --> 00:13:06,800
To pierwsza rzecz, którą umieścić
w tej hipotetycznej kolejce tutaj.

259
00:13:06,800 --> 00:13:10,430
I ogon, 13, jest najbardziej
ostatnio dodane element.

260
00:13:10,430 --> 00:13:17,030
I tak, jeśli chcemy enqueue 10 do
ta kolejka, chcemy umieścić go po 13.

261
00:13:17,030 --> 00:13:19,860
I tak będziemy dynamicznie
przydzielić miejsca dla nowego węzła

262
00:13:19,860 --> 00:13:23,280
i sprawdzić, czy wartość null, aby upewnić się,
nie mamy awarię pamięci.

263
00:13:23,280 --> 00:13:27,040
Następnie jedziemy do
miejsce 10 w tym węźle,

264
00:13:27,040 --> 00:13:30,030
a teraz musimy być ostrożni
o tym, jak zorganizować wskaźniki

265
00:13:30,030 --> 00:13:32,180
więc nie przerwać łańcuch.

266
00:13:32,180 --> 00:13:38,910
>> Możemy ustawić 10 za poprzednie pole
zwrócić z powrotem do starego ogona,

267
00:13:38,910 --> 00:13:41,620
i od '10 będzie
Nowy ogon w pewnym momencie

268
00:13:41,620 --> 00:13:44,459
od czasu, gdy wszystkie z tych
Łańcuchy są połączone

269
00:13:44,459 --> 00:13:46,250
nic nie przyjdzie
po 10 teraz.

270
00:13:46,250 --> 00:13:49,880
I tak 10 w następny wskaźnik
będzie wskazywać na null,

271
00:13:49,880 --> 00:13:53,580
a następnie po tym jak to zrobić, po mamy
podłączony 10 do tyłu do łańcucha

272
00:13:53,580 --> 00:13:57,780
możemy wziąć starą głowę, albo, przepraszam
ja, stary ogon kolejki.

273
00:13:57,780 --> 00:14:02,980
Stary koniec kolejki
13, i sprawiają, że wskazują na 10.

274
00:14:02,980 --> 00:14:08,220
A teraz, w tym momencie, mamy
skolejkowany numer 10 w tej kolejce.

275
00:14:08,220 --> 00:14:14,740
Wszystko, co musimy zrobić, to po prostu przenieść
Ogon pkt do 10 zamiast do 13.

276
00:14:14,740 --> 00:14:17,630
>> Usuwające wiadomości z kolejki jest rzeczywiście
bardzo podobne do popping

277
00:14:17,630 --> 00:14:21,710
ze stosu, który jest
realizowane jako połączonego listy

278
00:14:21,710 --> 00:14:24,040
jeśli widziałem film stosów.

279
00:14:24,040 --> 00:14:27,280
Wszystko, co musimy zrobić, to rozpocząć się
począwszy, znaleźć drugi element,

280
00:14:27,280 --> 00:14:30,480
zwolnienia pierwszego elementu
a następnie przesuń głowicę

281
00:14:30,480 --> 00:14:32,930
punkt drugiego elementu.

282
00:14:32,930 --> 00:14:37,920
Chyba lepiej go wizualizować
po prostu być bardzo jasne o tym.

283
00:14:37,920 --> 00:14:39,230
Więc oto kolejny nasz kolejki.

284
00:14:39,230 --> 00:14:42,600
12 jest najstarszym elementem
w naszej kolejki, głowę.

285
00:14:42,600 --> 00:14:46,210
10 jest najnowszym elementem
w naszej kolejki, ogonie.

286
00:14:46,210 --> 00:14:49,310
>> I tak, gdy chcemy
z kolejki element,

287
00:14:49,310 --> 00:14:52,202
chcemy usunąć najstarszy element.

288
00:14:52,202 --> 00:14:52,910
Więc co robimy?

289
00:14:52,910 --> 00:14:55,243
Cóż możemy ustawić wskaźnik przejścia
który zaczyna się na głowie

290
00:14:55,243 --> 00:14:57,840
i przenieść go tak, że
Wskazuje to na drugim elemencie

291
00:14:57,840 --> 00:15:02,290
tego queue-- coś mówiąc TRAV
wynosi trav strzałkę obok, na przykład

292
00:15:02,290 --> 00:15:07,170
ruszy trav nie zwrócić się do
15, które, po tym jak z kolejki 12,

293
00:15:07,170 --> 00:15:13,030
usuwamy lub po 12, będzie
stają się wówczas najstarszym elementem.

294
00:15:13,030 --> 00:15:16,360
>> Teraz musimy trzymać się na pierwszym
elementem przez głowicę wskaźnika

295
00:15:16,360 --> 00:15:19,440
i drugi element
poprzez trav wskaźnika.

296
00:15:19,440 --> 00:15:25,170
Możemy teraz wolną głowę, a następnie możemy
powiedzieć, nic nie przychodzi przed 15 już.

297
00:15:25,170 --> 00:15:29,990
Tak więc możemy zmienić 15 poprzednią
wskaźnik do punktu na null,

298
00:15:29,990 --> 00:15:31,874
i po prostu przesunąć głowę nad.

299
00:15:31,874 --> 00:15:32,540
A tam idziemy.

300
00:15:32,540 --> 00:15:35,840
Teraz mamy powodzeniem
rozkolejkowywana 12, a teraz

301
00:15:35,840 --> 00:15:39,180
mieć inną kolejkę 4 elementów.

302
00:15:39,180 --> 00:15:41,700
To dość dużo wszystko
nie ma kolejek,

303
00:15:41,700 --> 00:15:45,810
oba oparte na tablicy i linkowane lista oparta.

304
00:15:45,810 --> 00:15:46,860
Jestem Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
To CS 50.

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