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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Så om du har
såg videon på stacken,

3
00:00:07,370 --> 00:00:09,870
Detta är förmodligen kommer att känna
som en liten bit av deja vu.

4
00:00:09,870 --> 00:00:13,850
Det kommer att en mycket liknande koncept,
bara med en liten twist på det.

5
00:00:13,850 --> 00:00:15,530
Vi kommer att prata nu om köer.

6
00:00:15,530 --> 00:00:19,350
Så en kö, som liknar en stapel,
är en annan typ av datastruktur

7
00:00:19,350 --> 00:00:22,412
att vi kan använda för att upprätthålla
data på ett organiserat sätt.

8
00:00:22,412 --> 00:00:24,120
Liknar en stapel,
det kan genomföras

9
00:00:24,120 --> 00:00:27,000
som en matris eller en länkad lista.

10
00:00:27,000 --> 00:00:30,320
Till skillnad från en stapel, regler
som vi använder för att avgöra

11
00:00:30,320 --> 00:00:34,210
När det blir till och tas bort från
en kö är lite annorlunda.

12
00:00:34,210 --> 00:00:36,590
>> Till skillnad från en stapel, som
är en LIFO-struktur,

13
00:00:36,590 --> 00:00:45,610
sist in, först ut, är en kö en FIFO
struktur, FIFO, först in, först ut.

14
00:00:45,610 --> 00:00:49,320
Nu köer, du förmodligen
har en analogi med köer.

15
00:00:49,320 --> 00:00:52,820
Om du någonsin har varit i linje med
en nöjespark eller en bank,

16
00:00:52,820 --> 00:00:56,430
Det är typ av en så kallad fairness
genomförandestruktur.

17
00:00:56,430 --> 00:00:59,160
Den första personen i kön på
banken är den första personen

18
00:00:59,160 --> 00:01:00,760
vem som får tala till teller.

19
00:01:00,760 --> 00:01:03,522
>> Det skulle vara en slags tävling
till botten om det enda sättet

20
00:01:03,522 --> 00:01:06,730
du fick tala med teller vid
bank skulle vara den sista personen i kön.

21
00:01:06,730 --> 00:01:09,146
Alla skulle alltid vill
att vara den sista personen i linje,

22
00:01:09,146 --> 00:01:12,580
och den person som var där först
som har väntat på ett tag,

23
00:01:12,580 --> 00:01:14,715
kunde vara där i timmar,
och timmar och timmar

24
00:01:14,715 --> 00:01:17,590
innan de har en chans att faktiskt
återkalla några pengar på banken.

25
00:01:17,590 --> 00:01:22,510
Och så köer är typ av
rättvisa genomförandestruktur.

26
00:01:22,510 --> 00:01:25,780
Men det betyder inte nödvändigtvis
att staplar är en dålig sak, bara

27
00:01:25,780 --> 00:01:28,160
att köerna är ett annat sätt att göra det.

28
00:01:28,160 --> 00:01:32,420
Så återigen en kö är först in, först
ut, jämfört med en stapel som sist in

29
00:01:32,420 --> 00:01:34,440
först ut.

30
00:01:34,440 --> 00:01:36,190
Liknar en stapel,
Vi har två operationer

31
00:01:36,190 --> 00:01:38,470
att vi kan utföra på köer.

32
00:01:38,470 --> 00:01:43,910
Namnen är enqueue, vilket är att tillsätta
ett nytt element till slutet av kön,

33
00:01:43,910 --> 00:01:47,330
och avköa, vilket är
för att ta bort det äldsta

34
00:01:47,330 --> 00:01:49,670
elementet från framsidan av kön.

35
00:01:49,670 --> 00:01:53,600
Så vi kommer att lägga till element
på änden av kön,

36
00:01:53,600 --> 00:01:57,220
och vi kommer att ta bort element
från framsidan av kön.

37
00:01:57,220 --> 00:02:00,790
Återigen, med stapeln, vi tillsätta
element till toppen av stacken

38
00:02:00,790 --> 00:02:03,380
och ta bort element
från toppen av stacken.

39
00:02:03,380 --> 00:02:07,570
Så med enqueue, det bidrar till
slutet, avlägsnande från fronten.

40
00:02:07,570 --> 00:02:10,639
Så äldsta sak där
är alltid nästa sak

41
00:02:10,639 --> 00:02:13,620
att komma ut om vi försöker
och avköa något.

42
00:02:13,620 --> 00:02:18,330
>> Så återigen, med köer, vi kan
arraybaserade implementeringar

43
00:02:18,330 --> 00:02:20,110
och länkade lista baserad implementationer.

44
00:02:20,110 --> 00:02:24,620
Vi börjar igen med
array-baserade implementeringar.

45
00:02:24,620 --> 00:02:27,070
Definitionen strukturen
ser ganska likartade.

46
00:02:27,070 --> 00:02:30,720
Vi har en annan array
det av datatyp värde,

47
00:02:30,720 --> 00:02:32,690
så det kan hålla godtyckliga datatyper.

48
00:02:32,690 --> 00:02:35,570
Vi återigen kommer att använda
heltal i detta exempel.

49
00:02:35,570 --> 00:02:39,830
>> Och precis som med vår
array-baserade stack genomförandet,

50
00:02:39,830 --> 00:02:42,340
eftersom vi använder en
array, vi nödvändigtvis

51
00:02:42,340 --> 00:02:46,850
har denna begränsning att C typ
av upprätt på oss, som är vi

52
00:02:46,850 --> 00:02:51,670
har inte någon dynamik i vår
förmåga att växa och krympa arrayen.

53
00:02:51,670 --> 00:02:55,710
Vi måste bestämma i början
vad som är det maximala antal saker

54
00:02:55,710 --> 00:02:59,300
att vi kan sätta in detta
kö, och i detta fall,

55
00:02:59,300 --> 00:03:02,070
kapacitet skulle vara någon pund
definierad konstant i vår kod.

56
00:03:02,070 --> 00:03:05,430
Och för detta
video, kapaciteten kommer att bli 10.

57
00:03:05,430 --> 00:03:07,690
>> Vi måste hålla reda på
framsidan av kön

58
00:03:07,690 --> 00:03:11,160
så vi vet vilket element
Vi vill avköa,

59
00:03:11,160 --> 00:03:15,070
och vi måste också hålla reda på
något else-- antalet element

60
00:03:15,070 --> 00:03:16,690
som vi har i vår kö.

61
00:03:16,690 --> 00:03:19,360
Lägg märke till att vi inte hålla reda
i slutet av kön, bara

62
00:03:19,360 --> 00:03:21,150
storleken på kön.

63
00:03:21,150 --> 00:03:24,310
Och anledningen till det kommer förhoppningsvis
blivit lite tydligare i ett ögonblick.

64
00:03:24,310 --> 00:03:26,143
När vi har avslutat
denna definition typ,

65
00:03:26,143 --> 00:03:29,080
vi har en ny datatyp
kallas kö, som vi kan nu

66
00:03:29,080 --> 00:03:30,630
deklarera variabler av den datatypen.

67
00:03:30,630 --> 00:03:35,350
Och något förvirrande, har jag beslutat
att kalla detta kö q, bokstaven

68
00:03:35,350 --> 00:03:38,090
q i stället för datatypen q.

69
00:03:38,090 --> 00:03:39,600
>> Så här är vår kö.

70
00:03:39,600 --> 00:03:40,700
Det är en struktur.

71
00:03:40,700 --> 00:03:45,730
Den innehåller tre ledamöter eller tre
fält, en matris med storlek kapacitet.

72
00:03:45,730 --> 00:03:47,340
I det här fallet är KAPACITET 10.

73
00:03:47,340 --> 00:03:49,580
Och denna matris är
kommer att hålla heltal.

74
00:03:49,580 --> 00:03:55,240
I grönt är framsidan av vår kö, den
nästa element som skall avlägsnas, och i rött

75
00:03:55,240 --> 00:03:58,610
kommer att vara storleken på kön,
hur många element är närvarande

76
00:03:58,610 --> 00:04:01,190
existerande i kön.

77
00:04:01,190 --> 00:04:05,300
Så om vi säger q.front jämlikar
0, och q.size storlek lika 0--

78
00:04:05,300 --> 00:04:07,120
vi sätter 0s i dessa områden.

79
00:04:07,120 --> 00:04:11,070
Och på denna punkt, vi är ganska mycket
redo att börja arbeta med vår kö.

80
00:04:11,070 --> 00:04:14,140
>> Så den första operationen kan vi
göra är att köa något,

81
00:04:14,140 --> 00:04:16,860
att lägga ett nytt element i
slutet av kön.

82
00:04:16,860 --> 00:04:19,089
Och vad behöver vi
göra i det allmänna fallet?

83
00:04:19,089 --> 00:04:23,690
Väl denna funktion köa behov
att acceptera en pekare till vår kö.

84
00:04:23,690 --> 00:04:26,370
Återigen, om vi hade förklarat
vår kö globalt,

85
00:04:26,370 --> 00:04:29,490
Vi skulle inte behöva göra detta
nödvändigtvis, men i allmänhet, vi

86
00:04:29,490 --> 00:04:32,330
måste acceptera pekare
till datastrukturer

87
00:04:32,330 --> 00:04:35,040
så här, för annars,
vi passerar value-- vi är

88
00:04:35,040 --> 00:04:38,140
passerar i kopior av kö,
och så att vi inte är faktiskt förändras

89
00:04:38,140 --> 00:04:41,050
kön som vi har för avsikt att ändra.

90
00:04:41,050 --> 00:04:44,860
>> Den andra saken som behövs för att göra är acceptera
ett dataelement av lämplig typ.

91
00:04:44,860 --> 00:04:46,818
Återigen, i detta fall är det
kommer att vara heltal,

92
00:04:46,818 --> 00:04:49,330
men du kunde godtyckligt
förklara datatyp som värdet

93
00:04:49,330 --> 00:04:51,160
och använda denna mer allmänt.

94
00:04:51,160 --> 00:04:56,030
Det är elementet vill vi köa,
vi vill lägga till i slutet av kön.

95
00:04:56,030 --> 00:04:58,573
Då kan vi verkligen vill
Placera att data i kön.

96
00:04:58,573 --> 00:05:01,490
I det här fallet, placera den i
korrekt placering av vår samling,

97
00:05:01,490 --> 00:05:05,040
och sedan vill vi ändra storlek
av kön, hur många element vi

98
00:05:05,040 --> 00:05:07,050
för närvarande har.

99
00:05:07,050 --> 00:05:07,990
>> Så låt oss komma igång.

100
00:05:07,990 --> 00:05:10,890
Här är återigen den allmänna
formulär funktionsdeklarationen

101
00:05:10,890 --> 00:05:13,980
för vad enqueue kan se ut.

102
00:05:13,980 --> 00:05:14,910
Och nu kör vi.

103
00:05:14,910 --> 00:05:18,335
Låt oss köa numret
28 in i kön.

104
00:05:18,335 --> 00:05:19,460
Så vad ska vi göra?

105
00:05:19,460 --> 00:05:23,390
Tja, är framsidan av vår kö
vid 0, och storleken på vår kö

106
00:05:23,390 --> 00:05:29,680
är 0, och så vill vi nog sätta
antalet 28 i array elementnummer

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

108
00:05:31,124 --> 00:05:32,540
Så vi har nu lagt det där.

109
00:05:32,540 --> 00:05:34,820
Så nu vad vi behöver ändra?

110
00:05:34,820 --> 00:05:37,090
Vi vill inte ändra
framsidan av kön,

111
00:05:37,090 --> 00:05:40,850
eftersom vi vill veta vad elementet
Vi kanske behöver avköa senare.

112
00:05:40,850 --> 00:05:44,020
Så anledningen till att vi har framsidan finns
är typ av en indikator på vad som är

113
00:05:44,020 --> 00:05:46,439
det äldsta sak i arrayen.

114
00:05:46,439 --> 00:05:49,730
Tja äldsta sak i array-- i
Faktum är att den enda i gruppen rätt

115
00:05:49,730 --> 00:05:53,540
now-- är 28, som är
på array plats 0.

116
00:05:53,540 --> 00:05:56,160
Så vi vill inte
ändra på det gröna nummer,

117
00:05:56,160 --> 00:05:57,910
eftersom det är den äldsta elementet.

118
00:05:57,910 --> 00:06:00,510
Snarare vill vi ändra storleken.

119
00:06:00,510 --> 00:06:04,110
Så i det här fallet, vi ska
öka storleken till ett.

120
00:06:04,110 --> 00:06:08,430
>> Nu har en allmän slags uppfattning om var
nästa element kommer att gå i en kö

121
00:06:08,430 --> 00:06:12,310
är att lägga till dessa två siffror
tillsammans, fram och storlek,

122
00:06:12,310 --> 00:06:16,390
och som kommer att tala om var nästa
elementet i kön kommer att gå.

123
00:06:16,390 --> 00:06:18,130
Så nu ska vi köa ett annat nummer.

124
00:06:18,130 --> 00:06:20,250
Låt oss köa 33.

125
00:06:20,250 --> 00:06:24,480
Så 33 kommer att gå in i
array plats 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Så i detta fall, det kommer
att gå in array plats 1,

127
00:06:26,840 --> 00:06:29,500
och nu storleken på vår kö är 2.

128
00:06:29,500 --> 00:06:31,840
>> Återigen, vi ändrar inte
framsidan av vår kö,

129
00:06:31,840 --> 00:06:34,730
eftersom 28 är fortfarande den
äldsta elementet, och vi

130
00:06:34,730 --> 00:06:38,220
vill att-- när vi får så småningom
att dequeuing, ta bort element

131
00:06:38,220 --> 00:06:43,300
från denna kö, vill vi veta
där den äldsta elementet är.

132
00:06:43,300 --> 00:06:48,620
Och så måste vi alltid att behålla
någon indikation på var det är.

133
00:06:48,620 --> 00:06:50,410
Så det är vad det 0 är där för.

134
00:06:50,410 --> 00:06:52,910
Det är vad fronten är där för.

135
00:06:52,910 --> 00:06:55,022
>> Låt oss i enqueue ytterligare en beståndsdel, 19.

136
00:06:55,022 --> 00:06:56,980
Jag är säker på att du kan gissa
där 19 kommer att gå.

137
00:06:56,980 --> 00:06:59,860
Det kommer att gå in
array plats nummer två.

138
00:06:59,860 --> 00:07:01,570
Det är 0 plus två.

139
00:07:01,570 --> 00:07:03,199
Och nu storleken på vår kö är 3.

140
00:07:03,199 --> 00:07:04,240
Vi har 3 element i den.

141
00:07:04,240 --> 00:07:08,490
Så om vi skulle, och vi kommer inte
just nu, köa ett annat element,

142
00:07:08,490 --> 00:07:11,370
Det skulle gå in array plats
nummer 3, och storleken på vår kö

143
00:07:11,370 --> 00:07:13,160
skulle vara 4.

144
00:07:13,160 --> 00:07:15,279
Så vi har kö flera element nu.

145
00:07:15,279 --> 00:07:16,570
Nu börjar ta bort dem.

146
00:07:16,570 --> 00:07:19,450
Låt oss avköa dem från kön.

147
00:07:19,450 --> 00:07:23,340
>> Så lik pop, som är typ
av analogen av denna för staplar,

148
00:07:23,340 --> 00:07:26,180
dequeue måste acceptera en
pekare till queue-- igen,

149
00:07:26,180 --> 00:07:28,140
om det inte är globalt deklarerade.

150
00:07:28,140 --> 00:07:31,610
Nu vill vi ändra platsen
av den främre delen av kön.

151
00:07:31,610 --> 00:07:35,050
Det är här det slags kommer
i spelet, den fronten variabel,

152
00:07:35,050 --> 00:07:37,310
eftersom när vi tar bort
ett element, vill vi

153
00:07:37,310 --> 00:07:40,720
att flytta den till den näst äldsta elementet.

154
00:07:40,720 --> 00:07:44,180
>> Då kan vi vill minska
storleken på kön,

155
00:07:44,180 --> 00:07:47,130
och sedan vill vi att returnera värdet
som togs bort från kön.

156
00:07:47,130 --> 00:07:48,921
Återigen, vill vi inte bara kasta det.

157
00:07:48,921 --> 00:07:51,170
Vi förmodligen utvinner
det från queue-- vi

158
00:07:51,170 --> 00:07:54,170
dequeuing det eftersom vi bryr oss om det.

159
00:07:54,170 --> 00:08:01,080
Så vi vill här funktionen för att återvända
en dataelement av typen värde.

160
00:08:01,080 --> 00:08:04,360
Återigen, i det här fallet, är värdet heltal.

161
00:08:04,360 --> 00:08:05,670
>> Så nu ska vi avköa något.

162
00:08:05,670 --> 00:08:09,310
Låt oss ta bort ett element från kön.

163
00:08:09,310 --> 00:08:15,970
Om vi ​​säger int x lika & q,-tecken q--
igen som är en pekare till denna q uppgifter

164
00:08:15,970 --> 00:08:20,177
structure-- vad elementet
kommer att ur kön?

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

166
00:08:23,840 --> 00:08:29,480
I detta fall, eftersom det är ett första
in, först ut datastruktur, FIFO,

167
00:08:29,480 --> 00:08:33,690
det första vi lagt ned på detta
kön var 28, och så i detta fall,

168
00:08:33,690 --> 00:08:37,245
vi kommer att ta 28 av
kön, inte 19, vilket är vad

169
00:08:37,245 --> 00:08:38,870
vi skulle ha gjort om det var en stapel.

170
00:08:38,870 --> 00:08:42,220
Vi kommer att ta 28 av kön.

171
00:08:42,220 --> 00:08:44,960
>> I likhet med vad vi gjorde med
en bunt, kan vi faktiskt inte

172
00:08:44,960 --> 00:08:47,345
kommer att ta bort 28
ur kön i sig,

173
00:08:47,345 --> 00:08:49,470
Vi kommer bara att typ
av låtsas att det inte finns.

174
00:08:49,470 --> 00:08:51,678
Så det kommer att stanna kvar
i minnet, men vi är bara

175
00:08:51,678 --> 00:08:57,820
kommer att typ av ignorera det genom att flytta
de andra två områden av vår Q-data

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

177
00:08:58,830 --> 00:09:00,230
Vi ska ändra på framsidan.

178
00:09:00,230 --> 00:09:04,290
Q.front kommer nu att
vara en, eftersom det är nu

179
00:09:04,290 --> 00:09:07,740
den äldsta elementet vi har i vår
kö, eftersom vi redan har tagit bort 28,

180
00:09:07,740 --> 00:09:10,460
som var den tidigare äldsta elementet.

181
00:09:10,460 --> 00:09:13,540
>> Och nu vill vi ändra
storleken på kön

182
00:09:13,540 --> 00:09:15,780
till två element i stället för tre.

183
00:09:15,780 --> 00:09:20,450
Nu minns tidigare sagt jag när vi
vill lägga till element i kön,

184
00:09:20,450 --> 00:09:26,000
Vi lägger det i en array plats
som är summan av främre och storlek.

185
00:09:26,000 --> 00:09:29,050
Så i det här fallet, är vi fortfarande sätta
det, nästa element i kön,

186
00:09:29,050 --> 00:09:33,360
i array plats 3, och
Vi ser att i en sekund.

187
00:09:33,360 --> 00:09:35,730
>> Så vi har nu ur kön vår
första element från kön.

188
00:09:35,730 --> 00:09:36,480
Låt oss göra det igen.

189
00:09:36,480 --> 00:09:38,696
Låt oss ta en annan
elementet från kön.

190
00:09:38,696 --> 00:09:42,400
I fallet, den nuvarande äldsta
elementet är array plats 1.

191
00:09:42,400 --> 00:09:44,220
Det är vad q.front berättar.

192
00:09:44,220 --> 00:09:46,980
Det gröna rutan berättar att
det är det äldsta elementet.

193
00:09:46,980 --> 00:09:49,310
Och så kommer x att bli 33.

194
00:09:49,310 --> 00:09:52,130
Vi ska bara slags glömma
att 33 existerar i arrayen,

195
00:09:52,130 --> 00:09:55,100
och vi kommer att säga att nu, den
ny äldsta elementet i kön

196
00:09:55,100 --> 00:09:58,900
är array plats 2, och storleken
av kön, antalet element

197
00:09:58,900 --> 00:10:02,152
vi har i kön, är 1.

198
00:10:02,152 --> 00:10:05,110
Nu ska köa något, och jag
sorts gav detta bort en sekund sedan,

199
00:10:05,110 --> 00:10:10,340
men om vi vill sätta 40 i
kö, där är 40 kommer att gå?

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

201
00:10:12,880 --> 00:10:17,730
Jo vi har skjutit det
i q.front plus köstorleken,

202
00:10:17,730 --> 00:10:20,850
och så är det klokt att
faktiskt sätta 40 här.

203
00:10:20,850 --> 00:10:22,840
Nu märker att åtmin
någon gång kommer vi

204
00:10:22,840 --> 00:10:27,980
att komma till slutet av
vår samling inne i q,

205
00:10:27,980 --> 00:10:32,010
men det tonas ut 28 och 33--
de är faktiskt, tekniskt

206
00:10:32,010 --> 00:10:33,300
öppna ytor, eller hur?

207
00:10:33,300 --> 00:10:36,040
Och så kan vi eventually--
denna regel att lägga

208
00:10:36,040 --> 00:10:40,390
dessa två together-- vi kan så småningom
behöver mod av storleken på kapacitet

209
00:10:40,390 --> 00:10:41,410
så att vi kan linda runt.

210
00:10:41,410 --> 00:10:43,620
>> Så om vi får till elementet
nummer 10, om vi är

211
00:10:43,620 --> 00:10:48,790
ersätta den i elementet nummer 10, skulle vi
faktiskt lägga den i array plats 0.

212
00:10:48,790 --> 00:10:50,997
Och om vi skulle
array location-- ursäkta mig,

213
00:10:50,997 --> 00:10:53,080
om vi lagt upp dem tillsammans,
och vi fick till nummer

214
00:10:53,080 --> 00:10:56,330
11 skulle vara där vi skulle behöva sätta
den, vilket inte existerar i denna array--

215
00:10:56,330 --> 00:10:58,200
Det skulle vara att gå out of bounds.

216
00:10:58,200 --> 00:11:03,367
Vi kunde mod med 10 och sätta
det array plats 1.

217
00:11:03,367 --> 00:11:04,450
Så det är hur köerna fungerar.

218
00:11:04,450 --> 00:11:08,540
De kommer alltid att gå från vänster
till höger och eventuellt lindas runt.

219
00:11:08,540 --> 00:11:11,280
Och du vet att de är
full om storlek, att röd ruta,

220
00:11:11,280 --> 00:11:13,710
blir lika med kapaciteten.

221
00:11:13,710 --> 00:11:16,720
Och så när vi har lagt 40 till
kö, och vad behöver vi göra?

222
00:11:16,720 --> 00:11:19,890
Tja, det äldsta elementet
i kön är fortfarande 19,

223
00:11:19,890 --> 00:11:21,990
så att vi inte vill ändra
framsidan av kön,

224
00:11:21,990 --> 00:11:23,820
men nu har vi två
element i kön,

225
00:11:23,820 --> 00:11:28,710
och så vi vill öka
vår storlek 1-2.

226
00:11:28,710 --> 00:11:31,820
>> Det är ganska mycket det med
arbeta med arraybaserade köer,

227
00:11:31,820 --> 00:11:33,630
och liknande att stapla,
det är också ett sätt

228
00:11:33,630 --> 00:11:36,450
att implementera en kö som en länkad lista.

229
00:11:36,450 --> 00:11:40,150
Nu om denna datastruktur typ
ser bekant för dig, är det.

230
00:11:40,150 --> 00:11:43,780
Det är inte en enskilt länkad lista,
Det är en dubbelt länkad lista.

231
00:11:43,780 --> 00:11:46,790
Och nu, som en sidoreplik, är det
faktiskt är möjligt att genomföra

232
00:11:46,790 --> 00:11:50,160
en kö som ett enskilt länkad lista, men
Jag tänker i termer av visualisering,

233
00:11:50,160 --> 00:11:53,350
det faktiskt kan bidra till att visa
detta som en dubbellänkad lista.

234
00:11:53,350 --> 00:11:56,850
Men det är definitivt möjligt att
gör detta som ett enskilt länkad lista.

235
00:11:56,850 --> 00:12:00,110
>> Så låt oss ta en titt på
vad detta kan se ut.

236
00:12:00,110 --> 00:12:02,750
Om vi ​​vill enquue--
så nu, återigen vi är

237
00:12:02,750 --> 00:12:05,360
byta till en länkad-lista
baserad modell här.

238
00:12:05,360 --> 00:12:08,420
Om vi ​​vill köa, vi vill
att lägga ett nytt element, och

239
00:12:08,420 --> 00:12:09,730
Vad behöver vi göra?

240
00:12:09,730 --> 00:12:12,770
Jo, först och främst, eftersom
Vi lägger till slutet

241
00:12:12,770 --> 00:12:15,520
och avlägsnande från
början, vi förmodligen

242
00:12:15,520 --> 00:12:20,050
vill behålla pekare till både
huvudet och svansen på den länkade listan?

243
00:12:20,050 --> 00:12:22,660
Tail är en annan term för
I slutet av den länkade listan,

244
00:12:22,660 --> 00:12:24,496
det sista elementet i den länkade listan.

245
00:12:24,496 --> 00:12:26,620
Och dessa kommer förmodligen,
igen, vara till nytta för oss

246
00:12:26,620 --> 00:12:28,477
om de är globala variabler.

247
00:12:28,477 --> 00:12:31,060
Men nu om vi vill lägga till en ny
elementet vad har vi att göra?

248
00:12:31,060 --> 00:12:35,262
Vad vi bara [? Malak?] eller dynamiskt
fördela vår nya noden för oss själva.

249
00:12:35,262 --> 00:12:38,220
Och sedan, precis som när vi lägger något
elementet till en dubbellänkad lista som vi,

250
00:12:38,220 --> 00:12:40,410
bara att sortera of--
dessa tre sista stegen här

251
00:12:40,410 --> 00:12:43,330
är bara handlar om att flytta
pekare på rätt sätt

252
00:12:43,330 --> 00:12:46,710
så att elementet läggs till
kedjan utan att bryta kedjan

253
00:12:46,710 --> 00:12:49,580
eller göra någon form av misstag
eller har någon form av olycka

254
00:12:49,580 --> 00:12:54,505
hända där vi av misstag
överge vissa delar av vår kö.

255
00:12:54,505 --> 00:12:55,880
Här är vad detta skulle kunna se ut.

256
00:12:55,880 --> 00:13:00,980
Vi vill lägga till elementet
10 till slutet av denna kö.

257
00:13:00,980 --> 00:13:03,380
Så den äldsta elementet här
representeras av huvudet.

258
00:13:03,380 --> 00:13:06,800
Det är det första vi lägger
in i detta hypotetiska kö här.

259
00:13:06,800 --> 00:13:10,430
Och svans, 13, är den mest
nyligen lagt element.

260
00:13:10,430 --> 00:13:17,030
Och så om vi vill köa 10 i
denna kö, vill vi uttrycka det efter 13.

261
00:13:17,030 --> 00:13:19,860
Och så vi kommer att dynamiskt
allokera utrymme för en ny nod

262
00:13:19,860 --> 00:13:23,280
och kontrollera null för att se
vi har inte ett minnesfel.

263
00:13:23,280 --> 00:13:27,040
Då vi kommer att
placera 10 till denna nod,

264
00:13:27,040 --> 00:13:30,030
och nu måste vi vara försiktiga
om hur vi organiserar pekare

265
00:13:30,030 --> 00:13:32,180
så att vi inte bryter kedjan.

266
00:13:32,180 --> 00:13:38,910
>> Vi kan sätta 10 tidigare fält
att peka tillbaka till den gamla svansen,

267
00:13:38,910 --> 00:13:41,620
och sedan '10 kommer att vara
ny svans vid något tillfälle

268
00:13:41,620 --> 00:13:44,459
vid tiden alla dessa
kedjorna är anslutna,

269
00:13:44,459 --> 00:13:46,250
ingenting kommer att komma
efter 10 just nu.

270
00:13:46,250 --> 00:13:49,880
Och så 10 nästa pekare
kommer att peka på null,

271
00:13:49,880 --> 00:13:53,580
och sedan när vi gör detta, efter att vi har
anslutna 10 bakåt till kedjan,

272
00:13:53,580 --> 00:13:57,780
vi kan ta den gamla huvudet, eller ursäkt
mig, den gamla svansen hos kön.

273
00:13:57,780 --> 00:14:02,980
Den gamla slutet av kön,
13, och gör det pekar på 10.

274
00:14:02,980 --> 00:14:08,220
Och nu, på denna punkt, vi har
kö nummer 10 i denna kö.

275
00:14:08,220 --> 00:14:14,740
Allt vi behöver göra nu är bara att flytta
svans för att peka på 10 i stället för till 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing är faktiskt
mycket lik popping

277
00:14:17,630 --> 00:14:21,710
från en stapel som är
implementeras som en länkad lista

278
00:14:21,710 --> 00:14:24,040
Om du har sett staplar video.

279
00:14:24,040 --> 00:14:27,280
Allt vi behöver göra är att börja på
början, hitta den andra delen,

280
00:14:27,280 --> 00:14:30,480
frigöra det första elementet,
och sedan flytta huvudet

281
00:14:30,480 --> 00:14:32,930
att peka på det andra elementet.

282
00:14:32,930 --> 00:14:37,920
Förmodligen bättre för att visualisera det
bara för att vara extra tydlig med det.

283
00:14:37,920 --> 00:14:39,230
Så här är vår kö igen.

284
00:14:39,230 --> 00:14:42,600
12 är det äldsta elementet
i vår kö, huvudet.

285
00:14:42,600 --> 00:14:46,210
10 är den nyaste elementet
i vår kö, vår svans.

286
00:14:46,210 --> 00:14:49,310
>> Och så när vi vill
att avköa ett element,

287
00:14:49,310 --> 00:14:52,202
vi vill ta bort det äldsta elementet.

288
00:14:52,202 --> 00:14:52,910
Så vad gör vi?

289
00:14:52,910 --> 00:14:55,243
Jo vi sätter ett genomgångs pekare
som börjar i spetsen,

290
00:14:55,243 --> 00:14:57,840
och vi flyttar den så att den
pekar på det andra elementet

291
00:14:57,840 --> 00:15:02,290
av detta queue-- något genom att säga trav
lika trav pilen bredvid, till exempel,

292
00:15:02,290 --> 00:15:07,170
skulle flytta trav där för att peka på
15, som, efter att vi avköa 12,

293
00:15:07,170 --> 00:15:13,030
eller när vi tar bort 12, kommer
blir den då äldsta elementet.

294
00:15:13,030 --> 00:15:16,360
>> Nu har vi fått tag på den första
elementet via pekaren huvudet

295
00:15:16,360 --> 00:15:19,440
och det andra elementet
via pekaren trav.

296
00:15:19,440 --> 00:15:25,170
Vi kan nu gratis huvud, och då kan vi
säger ingenting kommer före den 15 längre.

297
00:15:25,170 --> 00:15:29,990
Så vi kan ändra 15 tidigare
pekare att peka på null,

298
00:15:29,990 --> 00:15:31,874
och vi rör oss bara huvudet över.

299
00:15:31,874 --> 00:15:32,540
Och det går vi.

300
00:15:32,540 --> 00:15:35,840
Nu har vi framgångsrikt
ur kön 12, och nu är vi

301
00:15:35,840 --> 00:15:39,180
har en annan kö av 4 element.

302
00:15:39,180 --> 00:15:41,700
Det är ganska mycket alla
Det finns köer,

303
00:15:41,700 --> 00:15:45,810
både array-baserade och länkade lista baserad.

304
00:15:45,810 --> 00:15:46,860
Jag är Doug Lloyd.

305
00:15:46,860 --> 00:15:49,100
Detta är CS 50.

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