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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Så hvis du har
set videoen på stakken,

3
00:00:07,370 --> 00:00:09,870
Dette er sandsynligvis kommer til at føle
ligesom en lille smule af deja vu.

4
00:00:09,870 --> 00:00:13,850
Det kommer til at en meget lignende koncept,
bare med en lille twist på den.

5
00:00:13,850 --> 00:00:15,530
Vi kommer til at tale nu om køer.

6
00:00:15,530 --> 00:00:19,350
Så en kø, svarende til en stabel,
er en anden form for datastruktur

7
00:00:19,350 --> 00:00:22,412
at vi kan bruge til at opretholde
data på en organiseret måde.

8
00:00:22,412 --> 00:00:24,120
Svarende til en stabel,
det kan gennemføres

9
00:00:24,120 --> 00:00:27,000
som en matrix eller et koblet liste.

10
00:00:27,000 --> 00:00:30,320
I modsætning til en stabel, reglerne
som vi bruger til at bestemme

11
00:00:30,320 --> 00:00:34,210
når tingene bliver tilføjet og fjernet fra
en kø er en lille smule anderledes.

12
00:00:34,210 --> 00:00:36,590
>> I modsætning til en stak, som
er en LIFO struktur,

13
00:00:36,590 --> 00:00:45,610
sidste ind, først ud, en kø er en FIFO
struktur, FIFO, først ind, først ud.

14
00:00:45,610 --> 00:00:49,320
Nu køer, har du sandsynligvis
have en analogi til køer.

15
00:00:49,320 --> 00:00:52,820
Hvis du nogensinde har været i overensstemmelse med
en forlystelsespark eller i en bank,

16
00:00:52,820 --> 00:00:56,430
der er en slags retfærdighed
gennemføre struktur.

17
00:00:56,430 --> 00:00:59,160
Den første person i kø ved
banken er den første person

18
00:00:59,160 --> 00:01:00,760
der får lov til at tale til Teller.

19
00:01:00,760 --> 00:01:03,522
>> Det ville være en slags løb
til bunden, hvis den eneste måde

20
00:01:03,522 --> 00:01:06,730
du fik til at tale med teller på
banken var at være den sidste person på linje.

21
00:01:06,730 --> 00:01:09,146
Alle ville altid ønsker
at være den sidste person på linje,

22
00:01:09,146 --> 00:01:12,580
og den person, der var der først
der har ventet på et stykke tid,

23
00:01:12,580 --> 00:01:14,715
kunne være der i timevis,
og timer, og timer

24
00:01:14,715 --> 00:01:17,590
før de har en chance for rent faktisk
trække nogen penge i banken.

25
00:01:17,590 --> 00:01:22,510
Og så køerne er sortering af
fairness gennemføre struktur.

26
00:01:22,510 --> 00:01:25,780
Men det betyder ikke nødvendigvis,
at stakke er en dårlig ting, bare

27
00:01:25,780 --> 00:01:28,160
at køer er en anden måde at gøre det.

28
00:01:28,160 --> 00:01:32,420
Så igen en kø er først ind, først
ud, versus en stak som varer i,

29
00:01:32,420 --> 00:01:34,440
først ud.

30
00:01:34,440 --> 00:01:36,190
Svarende til en stabel,
vi har to operationer

31
00:01:36,190 --> 00:01:38,470
at vi kan udføre på køer.

32
00:01:38,470 --> 00:01:43,910
Navnene er enqueue, som er at tilføje
et nyt element til enden af ​​køen,

33
00:01:43,910 --> 00:01:47,330
og dequeue, som er
at fjerne den ældste

34
00:01:47,330 --> 00:01:49,670
element fra forrest i køen.

35
00:01:49,670 --> 00:01:53,600
Så vi kommer til at tilføje elementer
på enden af ​​køen,

36
00:01:53,600 --> 00:01:57,220
og vi vil fjerne elementer
fra forrest i køen.

37
00:01:57,220 --> 00:02:00,790
Igen, med stakken, vi tilføjer
elementer til toppen af ​​stablen

38
00:02:00,790 --> 00:02:03,380
og fjerne elementer
fra toppen af ​​stakken.

39
00:02:03,380 --> 00:02:07,570
Så med enqueue, er det at tilføje til
Til sidst fjernes fra forsiden.

40
00:02:07,570 --> 00:02:10,639
Så den ældste ting derinde
er altid den næste ting

41
00:02:10,639 --> 00:02:13,620
til at komme ud, hvis vi prøver
og dequeue noget.

42
00:02:13,620 --> 00:02:18,330
>> Så igen, med køer, vi kan
array-baserede implementeringer

43
00:02:18,330 --> 00:02:20,110
og forbundet listen på grundlag implementeringer.

44
00:02:20,110 --> 00:02:24,620
Vi starter igen med
Array-baserede implementeringer.

45
00:02:24,620 --> 00:02:27,070
Definitionen struktur
ser temmelig ens.

46
00:02:27,070 --> 00:02:30,720
Vi har en anden matrix
der af datatypen værdi,

47
00:02:30,720 --> 00:02:32,690
så det kan holde vilkårlige datatyper.

48
00:02:32,690 --> 00:02:35,570
Vi igen kommer til at bruge
heltal i dette eksempel.

49
00:02:35,570 --> 00:02:39,830
>> Og ligesom med vores
matrix-baseret stabel gennemførelse,

50
00:02:39,830 --> 00:02:42,340
fordi vi bruger en
array, vi nødvendigvis

51
00:02:42,340 --> 00:02:46,850
har denne begrænsning, at C slags
af håndhæver på os, som er, at vi

52
00:02:46,850 --> 00:02:51,670
ikke har nogen dynamik i vores
evne til at vokse og skrumpe array.

53
00:02:51,670 --> 00:02:55,710
Vi er nødt til at beslutte, i begyndelsen
hvad der er det maksimale antal ting

54
00:02:55,710 --> 00:02:59,300
at vi kan sætte ind i denne
kø, og i dette tilfælde,

55
00:02:59,300 --> 00:03:02,070
kapacitet ville være nogle pund
defineret konstant i vores kode.

56
00:03:02,070 --> 00:03:05,430
Og for så vidt angår dette
video, er kapaciteten vil være 10.

57
00:03:05,430 --> 00:03:07,690
>> Vi har brug for at holde styr på
Den forrest i køen

58
00:03:07,690 --> 00:03:11,160
så vi ved, hvilke elementer
vi ønsker at dequeue,

59
00:03:11,160 --> 00:03:15,070
og vi har også brug for at holde styr på
noget else-- antallet af elementer

60
00:03:15,070 --> 00:03:16,690
at vi har i vores kø.

61
00:03:16,690 --> 00:03:19,360
Bemærk vi ikke holde styr
af enden af ​​køen, lige

62
00:03:19,360 --> 00:03:21,150
størrelsen af ​​køen.

63
00:03:21,150 --> 00:03:24,310
Og grunden til, der vil forhåbentlig
blive lidt klarere i et øjeblik.

64
00:03:24,310 --> 00:03:26,143
Når vi har gennemført
denne type definition,

65
00:03:26,143 --> 00:03:29,080
vi har en ny datatype
kaldet kø, som vi nu kan

66
00:03:29,080 --> 00:03:30,630
erklære variabler af denne datatype.

67
00:03:30,630 --> 00:03:35,350
Og noget forvirrende, har jeg besluttet
at kalde dette kø q, bogstavet

68
00:03:35,350 --> 00:03:38,090
q stedet for datatypen q.

69
00:03:38,090 --> 00:03:39,600
>> Så her er vores kø.

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

71
00:03:40,700 --> 00:03:45,730
Den indeholder tre medlemmer eller tre
felter, et array af størrelse KAPACITET.

72
00:03:45,730 --> 00:03:47,340
I dette tilfælde, kapacitet er 10.

73
00:03:47,340 --> 00:03:49,580
Og dette array er
kommer til at holde heltal.

74
00:03:49,580 --> 00:03:55,240
I er grøn foran vores køen
næste element, der skal fjernes, og i rødt

75
00:03:55,240 --> 00:03:58,610
bliver størrelsen af ​​køen,
hvor mange elementer er i øjeblikket

76
00:03:58,610 --> 00:04:01,190
eksisterende i køen.

77
00:04:01,190 --> 00:04:05,300
Så hvis vi siger q.front ligemænd
0, og q.size størrelse lig 0--

78
00:04:05,300 --> 00:04:07,120
vi sætter 0'erne i disse områder.

79
00:04:07,120 --> 00:04:11,070
Og på dette punkt, vi er ret meget
klar til at begynde at arbejde med vores kø.

80
00:04:11,070 --> 00:04:14,140
>> Så den første operation, vi kan
udføre, er at enqueue noget,

81
00:04:14,140 --> 00:04:16,860
at tilføje et nyt element til
enden af ​​køen.

82
00:04:16,860 --> 00:04:19,089
Nå, hvad skal vi
gøre i det generelle tilfælde?

83
00:04:19,089 --> 00:04:23,690
Nå denne funktion enqueue behov
at acceptere en pointer til vores kø.

84
00:04:23,690 --> 00:04:26,370
Igen, hvis vi havde erklæret
vores kø globalt,

85
00:04:26,370 --> 00:04:29,490
ville vi ikke behøver at gøre det
nødvendigvis, men generelt vi

86
00:04:29,490 --> 00:04:32,330
nødt til at acceptere pointers
til datastrukturer

87
00:04:32,330 --> 00:04:35,040
som dette, for ellers,
vi passerer ved value-- vi er

88
00:04:35,040 --> 00:04:38,140
passerer i kopier af køen,
og så vi faktisk ikke ændrer

89
00:04:38,140 --> 00:04:41,050
køen, at vi agter at ændre.

90
00:04:41,050 --> 00:04:44,860
>> Den anden ting, den har brug for at gøre, er at acceptere
en dataelement i den relevante type.

91
00:04:44,860 --> 00:04:46,818
Igen, i dette tilfælde, er det
vil være heltal,

92
00:04:46,818 --> 00:04:49,330
men du kunne vilkårligt
erklære datatype som værdi

93
00:04:49,330 --> 00:04:51,160
og bruge denne mere generelt.

94
00:04:51,160 --> 00:04:56,030
Det er det element, vi ønsker at enqueue,
Vi ønsker at tilføje til slutningen af ​​køen.

95
00:04:56,030 --> 00:04:58,573
Så vi faktisk ønsker at
placere, at data i køen.

96
00:04:58,573 --> 00:05:01,490
I dette tilfælde, at placere den i
korrekte placering af vores array,

97
00:05:01,490 --> 00:05:05,040
og så ønsker vi at ændre størrelsen
af køen, hvor mange elementer, vi

98
00:05:05,040 --> 00:05:07,050
har i øjeblikket.

99
00:05:07,050 --> 00:05:07,990
>> Så lad os komme i gang.

100
00:05:07,990 --> 00:05:10,890
Her er, igen, at generelle
formular funktion erklæring

101
00:05:10,890 --> 00:05:13,980
for hvad enqueue kunne se ud.

102
00:05:13,980 --> 00:05:14,910
Og her går vi.

103
00:05:14,910 --> 00:05:18,335
Lad os enqueue antallet
28 ind i køen.

104
00:05:18,335 --> 00:05:19,460
Så hvad skal vi gøre?

105
00:05:19,460 --> 00:05:23,390
Nå, den forreste del af vores kø er
ved 0 og størrelsen af ​​vores kø

106
00:05:23,390 --> 00:05:29,680
er på 0, og så vi sandsynligvis ønsker at sætte
nummer 28 i arrayelement nummer

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

108
00:05:31,124 --> 00:05:32,540
Så vi har nu placeret, at derinde.

109
00:05:32,540 --> 00:05:34,820
Så nu, hvad har vi brug for at ændre?

110
00:05:34,820 --> 00:05:37,090
Vi ønsker ikke at ændre
forsiden af ​​køen,

111
00:05:37,090 --> 00:05:40,850
fordi vi ønsker at vide, hvad element
vi måske nødt til at dequeue senere.

112
00:05:40,850 --> 00:05:44,020
Så årsagen til at vi har foran der
er en slags en indikator for, hvad der er

113
00:05:44,020 --> 00:05:46,439
den ældste ting i arrayet.

114
00:05:46,439 --> 00:05:49,730
Nå den ældste ting i array-- i
Faktisk er den eneste ting i array højre

115
00:05:49,730 --> 00:05:53,540
nu-- er 28, hvilket er
ved opstilling placering 0.

116
00:05:53,540 --> 00:05:56,160
Så vi ønsker ikke at
ændre det grønne nummer,

117
00:05:56,160 --> 00:05:57,910
fordi det er den ældste element.

118
00:05:57,910 --> 00:06:00,510
Snarere, vi ønsker at ændre størrelsen.

119
00:06:00,510 --> 00:06:04,110
Så i dette tilfælde, vi får
trinstørrelsen til 1.

120
00:06:04,110 --> 00:06:08,430
>> Nu en generel form for ide om, hvor
næste element kommer til at gå i en kø

121
00:06:08,430 --> 00:06:12,310
er at tilføje disse to tal
sammen foran og størrelse,

122
00:06:12,310 --> 00:06:16,390
og der vil fortælle dig, hvor den næste
element i køen kommer til at gå.

123
00:06:16,390 --> 00:06:18,130
Så lad os nu enqueue andet nummer.

124
00:06:18,130 --> 00:06:20,250
Lad os Sæt i kø 33.

125
00:06:20,250 --> 00:06:24,480
Så 33 kommer til at gå ind
matrix placering 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Så i dette tilfælde, det vil
at gå ind matrix placering 1,

127
00:06:26,840 --> 00:06:29,500
og nu størrelsen af ​​vores køen er 2.

128
00:06:29,500 --> 00:06:31,840
>> Igen, vi ikke ændrer
forsiden af ​​vores køen,

129
00:06:31,840 --> 00:06:34,730
fordi 28 er stadig den
ældste element, og vi

130
00:06:34,730 --> 00:06:38,220
ønsker at-- når vi til sidst får
at dequeuing, fjerne elementer

131
00:06:38,220 --> 00:06:43,300
fra denne kø, vi ønsker at vide
hvor den ældste element er.

132
00:06:43,300 --> 00:06:48,620
Og så vi altid nødt til at opretholde
nogle indikator for, hvor det er.

133
00:06:48,620 --> 00:06:50,410
Så det er hvad de 0 er der for.

134
00:06:50,410 --> 00:06:52,910
Det er, hvad foran er der for.

135
00:06:52,910 --> 00:06:55,022
>> Lad os i enqueue endnu element, 19.

136
00:06:55,022 --> 00:06:56,980
Jeg er sikker på du kan gætte
hvor 19 kommer til at gå.

137
00:06:56,980 --> 00:06:59,860
Det kommer til at gå ind i
matrix placering nummer 2.

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

139
00:07:01,570 --> 00:07:03,199
Og nu størrelsen af ​​vores kø er 3.

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

141
00:07:04,240 --> 00:07:08,490
Så hvis vi skulle, og vi vil ikke
til lige nu, enqueue et andet element,

142
00:07:08,490 --> 00:07:11,370
det ville gå ind matrix placering
nummer 3, og størrelsen af ​​vores kø

143
00:07:11,370 --> 00:07:13,160
ville være 4.

144
00:07:13,160 --> 00:07:15,279
Så vi har kø flere elementer nu.

145
00:07:15,279 --> 00:07:16,570
Lad os nu begynde at fjerne dem.

146
00:07:16,570 --> 00:07:19,450
Lad os dequeue dem fra køen.

147
00:07:19,450 --> 00:07:23,340
>> Så ligner pop, som er sortering
af analogen af ​​dette for stakke,

148
00:07:23,340 --> 00:07:26,180
dequeue nødt til at acceptere en
pointer til queue-- igen,

149
00:07:26,180 --> 00:07:28,140
medmindre det globalt erklærede.

150
00:07:28,140 --> 00:07:31,610
Nu ønsker vi at ændre placeringen
af forrest i køen.

151
00:07:31,610 --> 00:07:35,050
Det er her, det slags kommer
i spil, det forreste variabel,

152
00:07:35,050 --> 00:07:37,310
fordi når vi fjerner
et element, vi ønsker

153
00:07:37,310 --> 00:07:40,720
at flytte det til det næste ældste element.

154
00:07:40,720 --> 00:07:44,180
>> Så vi ønsker at mindske
størrelsen af ​​køen,

155
00:07:44,180 --> 00:07:47,130
og så vil vi returnere værdien
der blev fjernet fra køen.

156
00:07:47,130 --> 00:07:48,921
Igen, vi ikke ønsker at bare kassere det.

157
00:07:48,921 --> 00:07:51,170
Vi formentlig er udvinder
det fra queue-- vi er

158
00:07:51,170 --> 00:07:54,170
dequeuing det, fordi vi bekymrer os om det.

159
00:07:54,170 --> 00:08:01,080
Så vi ønsker denne funktion til at vende tilbage
en dataelement af typen værdi.

160
00:08:01,080 --> 00:08:04,360
Igen, i dette tilfælde, er et helt tal værdi.

161
00:08:04,360 --> 00:08:05,670
>> Så lad os nu dequeue noget.

162
00:08:05,670 --> 00:08:09,310
Lad os fjerne et element fra køen.

163
00:08:09,310 --> 00:08:15,970
Hvis vi siger, int x lig & q, tegnet q--
igen, det er en pointer til denne q data

164
00:08:15,970 --> 00:08:20,177
structure-- hvad element
vil blive dequeued?

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

166
00:08:23,840 --> 00:08:29,480
I dette tilfælde, fordi det er en første
ind, først ud datastruktur, FIFO,

167
00:08:29,480 --> 00:08:33,690
den første ting, vi sætter ind i denne
køen var 28, og så i dette tilfælde,

168
00:08:33,690 --> 00:08:37,245
vi kommer til at tage 28 ud af
køen, ikke 19, hvilket er, hvad

169
00:08:37,245 --> 00:08:38,870
vi ville have gjort, hvis det var en stak.

170
00:08:38,870 --> 00:08:42,220
Vi kommer til at tage 28 ud af køen.

171
00:08:42,220 --> 00:08:44,960
>> Svarer til, hvad vi gjorde med
en stak, men vi er faktisk ikke

172
00:08:44,960 --> 00:08:47,345
ved at slette 28
fra køen selv,

173
00:08:47,345 --> 00:08:49,470
vi bare at slags
af lade som om det ikke er der.

174
00:08:49,470 --> 00:08:51,678
Så det kommer til at blive der
i hukommelsen, men vi er bare

175
00:08:51,678 --> 00:08:57,820
kommer til at slags ignorere det ved at flytte
de to andre områder af vores q data

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

177
00:08:58,830 --> 00:09:00,230
Vi kommer til at ændre fronten.

178
00:09:00,230 --> 00:09:04,290
Q.front nu kommer til at
være 1, fordi der nu er

179
00:09:04,290 --> 00:09:07,740
den ældste element, vi har i vores
kø, fordi vi allerede har fjernet 28,

180
00:09:07,740 --> 00:09:10,460
som var den tidligere ældste element.

181
00:09:10,460 --> 00:09:13,540
>> Og nu, vi ønsker at ændre
størrelsen af ​​køen

182
00:09:13,540 --> 00:09:15,780
til to elementer i stedet for tre.

183
00:09:15,780 --> 00:09:20,450
Husk nu tidligere sagde jeg, da vi
ønsker at tilføje elementer til køen,

184
00:09:20,450 --> 00:09:26,000
vi sætte det i et array placering
som er summen af ​​den forreste og størrelse.

185
00:09:26,000 --> 00:09:29,050
Så i dette tilfælde, er vi stadig sætte
det, det næste element i køen,

186
00:09:29,050 --> 00:09:33,360
i matrix Sted 3, og
Vi vil se, at i en anden.

187
00:09:33,360 --> 00:09:35,730
>> Så vi har nu dequeued vores
første element fra køen.

188
00:09:35,730 --> 00:09:36,480
Lad os gøre det igen.

189
00:09:36,480 --> 00:09:38,696
Lad os fjerne en anden
element fra køen.

190
00:09:38,696 --> 00:09:42,400
I tilfælde, den nuværende ældste
element er matrix placering 1.

191
00:09:42,400 --> 00:09:44,220
Det er, hvad q.front fortæller os.

192
00:09:44,220 --> 00:09:46,980
Det grønne boks fortæller os, at
det er den ældste element.

193
00:09:46,980 --> 00:09:49,310
Og så vil x blive 33.

194
00:09:49,310 --> 00:09:52,130
Vi vil bare slags glemmer
at 33 findes i arrayet,

195
00:09:52,130 --> 00:09:55,100
og vi vil sige, at nu, at
nye ældste element i køen

196
00:09:55,100 --> 00:09:58,900
er matrix placering 2, og størrelsen
i køen, antallet af elementer

197
00:09:58,900 --> 00:10:02,152
vi har i køen, er 1.

198
00:10:02,152 --> 00:10:05,110
Lad os nu enqueue noget, og jeg
slags gav dette væk et sekund siden,

199
00:10:05,110 --> 00:10:10,340
men hvis vi ønsker at sætte 40 ind i
kø, hvor er 40 kommer til at gå?

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

201
00:10:12,880 --> 00:10:17,730
Godt vi har været at sætte det
i q.front plus køstørrelsen,

202
00:10:17,730 --> 00:10:20,850
og så det giver mening at
faktisk at sætte 40 her.

203
00:10:20,850 --> 00:10:22,840
Nu bemærke, at på
et tidspunkt, vil vi

204
00:10:22,840 --> 00:10:27,980
at komme til udgangen af
vores matrix inde i q,

205
00:10:27,980 --> 00:10:32,010
men det falmede ud 28 og 33--
de er faktisk, teknisk

206
00:10:32,010 --> 00:10:33,300
åbne rum, ikke?

207
00:10:33,300 --> 00:10:36,040
Og så kan vi eventually--
denne regel for at tilføje

208
00:10:36,040 --> 00:10:40,390
de to together-- vi kan i sidste ende
skal mod ved størrelsen af ​​kapaciteten

209
00:10:40,390 --> 00:10:41,410
så vi kan wrap omkring.

210
00:10:41,410 --> 00:10:43,620
>> Så hvis vi kommer til element
nummer 10, hvis vi er

211
00:10:43,620 --> 00:10:48,790
erstatte det i element nummer 10, vi havde
faktisk sætte det i matrix placering 0.

212
00:10:48,790 --> 00:10:50,997
Og hvis vi skulle
vifte Beliggende- undskyld mig,

213
00:10:50,997 --> 00:10:53,080
hvis vi tilføjet dem op sammen,
og vi fik til nummer

214
00:10:53,080 --> 00:10:56,330
11 ville være, hvor vi ville have til at sætte
det, som ikke findes i denne array--

215
00:10:56,330 --> 00:10:58,200
Det ville være at gå ud af banen.

216
00:10:58,200 --> 00:11:03,367
Vi kunne MoD med 10 og lægge
det i matrix placering 1.

217
00:11:03,367 --> 00:11:04,450
Så det er sådan køer virker.

218
00:11:04,450 --> 00:11:08,540
De er altid kommer til at gå fra venstre
til højre og muligvis wrap omkring.

219
00:11:08,540 --> 00:11:11,280
Og du ved, at de er
fuld, hvis størrelse, at røde felt,

220
00:11:11,280 --> 00:11:13,710
bliver lig med kapaciteten.

221
00:11:13,710 --> 00:11:16,720
Og så efter vi har tilføjet 40 til den
kø, godt hvad skal vi gøre?

222
00:11:16,720 --> 00:11:19,890
Nå, den ældste element
i køen er stadig 19,

223
00:11:19,890 --> 00:11:21,990
så vi ikke ønsker at ændre
forsiden af ​​køen,

224
00:11:21,990 --> 00:11:23,820
men nu har vi to
elementer i køen,

225
00:11:23,820 --> 00:11:28,710
og så vi ønsker at øge
vores størrelse fra 1 til 2.

226
00:11:28,710 --> 00:11:31,820
>> Det er temmelig meget det med
arbejder med array-baserede køer,

227
00:11:31,820 --> 00:11:33,630
og lignende til at stable,
Der er også en måde

228
00:11:33,630 --> 00:11:36,450
at gennemføre en kø som sammenkædet liste.

229
00:11:36,450 --> 00:11:40,150
Nu, hvis disse data strukturtype
ser bekendt for dig, det er.

230
00:11:40,150 --> 00:11:43,780
Det er ikke en enkeltvis linket liste,
det er en dobbelt linket liste.

231
00:11:43,780 --> 00:11:46,790
Og nu, som en sidebemærkning, er det
faktisk er muligt at gennemføre

232
00:11:46,790 --> 00:11:50,160
en kø som et enkelt bundet liste, men
Jeg tænker i visualisering,

233
00:11:50,160 --> 00:11:53,350
det rent faktisk kan bidrage til at se
dette som en dobbelt sammenkædet liste.

234
00:11:53,350 --> 00:11:56,850
Men det er absolut muligt at
gøre dette som en enkelt bundet listen.

235
00:11:56,850 --> 00:12:00,110
>> Så lad os få et kig på
hvad det kunne se ud.

236
00:12:00,110 --> 00:12:02,750
Hvis vi ønsker at enquue--
så nu, igen er vi

237
00:12:02,750 --> 00:12:05,360
skifte til en sammenkædet liste
baseret model her.

238
00:12:05,360 --> 00:12:08,420
Hvis vi ønsker at enqueue, vi ønsker
at tilføje et nyt element, godt

239
00:12:08,420 --> 00:12:09,730
hvad skal vi gøre?

240
00:12:09,730 --> 00:12:12,770
Nå, først og fremmest fordi
vi tilføjer til enden

241
00:12:12,770 --> 00:12:15,520
og fjernelse fra
begynder, vi sandsynligvis

242
00:12:15,520 --> 00:12:20,050
ønsker at opretholde pegepinde til både
hoved og halen af ​​linkede liste?

243
00:12:20,050 --> 00:12:22,660
Hale er et andet ord for
slutningen af ​​linkede liste,

244
00:12:22,660 --> 00:12:24,496
det sidste element i den linkede liste.

245
00:12:24,496 --> 00:12:26,620
Og disse vil formentlig,
igen, være til gavn for os

246
00:12:26,620 --> 00:12:28,477
hvis de er globale variabler.

247
00:12:28,477 --> 00:12:31,060
Men nu, hvis vi ønsker at tilføje en ny
element hvad har vi at gøre?

248
00:12:31,060 --> 00:12:35,262
Det, vi bare [? Malak?] eller dynamisk
allokere vores nye node for os selv.

249
00:12:35,262 --> 00:12:38,220
Og så, ligesom når vi tilføje
element til en dobbelt sammenkædet liste vi,

250
00:12:38,220 --> 00:12:40,410
bare nødt til at sortere of--
de tre sidstnævnte trin her

251
00:12:40,410 --> 00:12:43,330
er bare alt om at flytte
pejlemærker i den korrekte måde

252
00:12:43,330 --> 00:12:46,710
således at elementet bliver tilføjet til
kæden uden at bryde kæden

253
00:12:46,710 --> 00:12:49,580
eller gøre en slags fejl
eller har en slags ulykker

254
00:12:49,580 --> 00:12:54,505
ske, hvorved vi ved et uheld
forældreløs nogle elementer i vores kø.

255
00:12:54,505 --> 00:12:55,880
Her er, hvad det kan se ud.

256
00:12:55,880 --> 00:13:00,980
Vi ønsker at tilføje elementet
10 til enden af ​​denne kø.

257
00:13:00,980 --> 00:13:03,380
Så den ældste element her
er repræsenteret ved hovedet.

258
00:13:03,380 --> 00:13:06,800
Det er den første ting, vi sætter
i dette hypotetiske kø her.

259
00:13:06,800 --> 00:13:10,430
Og hale, 13, er den mest
nylig tilføjet element.

260
00:13:10,430 --> 00:13:17,030
Og så hvis vi ønsker at enqueue 10 ind
denne kø, vi ønsker at sætte det efter 13.

261
00:13:17,030 --> 00:13:19,860
Og så vil vi dynamisk
allokere plads til en ny node

262
00:13:19,860 --> 00:13:23,280
og kontrollere for null for at sikre,
vi ikke har en hukommelse fiasko.

263
00:13:23,280 --> 00:13:27,040
Så vi kommer til at
placere 10 i dette knudepunkt,

264
00:13:27,040 --> 00:13:30,030
og nu er vi nødt til at være forsigtige
om, hvordan vi organiserer pegepinde

265
00:13:30,030 --> 00:13:32,180
så vi ikke bryde kæden.

266
00:13:32,180 --> 00:13:38,910
>> Vi kan sætte 10 tidligere felt
at pege tilbage til det gamle hale,

267
00:13:38,910 --> 00:13:41,620
og da '10 vil blive
nye hale på et tidspunkt

268
00:13:41,620 --> 00:13:44,459
på det tidspunkt alle disse
kæder er forbundet,

269
00:13:44,459 --> 00:13:46,250
intet kommer til at komme
efter 10 lige nu.

270
00:13:46,250 --> 00:13:49,880
Og så 10 næste pointer
vil pege til null,

271
00:13:49,880 --> 00:13:53,580
og derefter efter vi gør det, efter at vi har
tilsluttet 10 bagud til kæden,

272
00:13:53,580 --> 00:13:57,780
vi kan tage det gamle hoved, eller, undskyldning
mig, den gamle hale i køen.

273
00:13:57,780 --> 00:14:02,980
Den gamle ende af køen,
13, og gøre det peger på 10.

274
00:14:02,980 --> 00:14:08,220
Og nu, på dette tidspunkt, har vi
kø nummer 10 i denne kø.

275
00:14:08,220 --> 00:14:14,740
Alt, hvad vi skal gøre nu er bare at flytte
hale til at pege på 10 i stedet for til 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing er faktisk
meget lig popping

277
00:14:17,630 --> 00:14:21,710
fra en stak, der er
implementeret som en sammenkædet liste

278
00:14:21,710 --> 00:14:24,040
hvis du har set den stakke video.

279
00:14:24,040 --> 00:14:27,280
Alt, hvad vi skal gøre, er at starte på
begynder, find det andet element,

280
00:14:27,280 --> 00:14:30,480
frigøre det første element,
og derefter flytte hovedet

281
00:14:30,480 --> 00:14:32,930
til at pege på det andet element.

282
00:14:32,930 --> 00:14:37,920
Sandsynligvis bedre at visualisere det
bare for at være ekstra klar over det.

283
00:14:37,920 --> 00:14:39,230
Så her er vores kø igen.

284
00:14:39,230 --> 00:14:42,600
12 er den ældste element
i vores kø, hovedet.

285
00:14:42,600 --> 00:14:46,210
10 er den nyeste element
i vores kø, vores hale.

286
00:14:46,210 --> 00:14:49,310
>> Og så når vi ønsker
at dequeue et element,

287
00:14:49,310 --> 00:14:52,202
Vi ønsker at fjerne det ældste element.

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

289
00:14:52,910 --> 00:14:55,243
Godt vi sat en traversal pointer
der starter i spidsen,

290
00:14:55,243 --> 00:14:57,840
og vi flytte det, så det
peger på det andet element

291
00:14:57,840 --> 00:15:02,290
af denne queue-- noget ved at sige trav
lig trav pil næste, for eksempel,

292
00:15:02,290 --> 00:15:07,170
ville flytte trav der til at pege på
15, som, efter at vi dequeue 12,

293
00:15:07,170 --> 00:15:13,030
eller efter at vi fjerner 12, vil
blive den daværende ældste element.

294
00:15:13,030 --> 00:15:16,360
>> Nu har vi fået fat på den første
element via markøren hovedet

295
00:15:16,360 --> 00:15:19,440
og det andet element
via markøren trav.

296
00:15:19,440 --> 00:15:25,170
Vi kan nu gratis hoved, og så kan vi
siger intet kommer før den 15. længere.

297
00:15:25,170 --> 00:15:29,990
Så vi kan ændre 15 tidligere
pointer til at pege til null,

298
00:15:29,990 --> 00:15:31,874
og vi bare flytte hovedet over.

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

300
00:15:32,540 --> 00:15:35,840
Nu har vi med succes
dequeued 12, og nu er vi

301
00:15:35,840 --> 00:15:39,180
har en anden kø af 4 elementer.

302
00:15:39,180 --> 00:15:41,700
Det er temmelig meget alle
der er at køer,

303
00:15:41,700 --> 00:15:45,810
både matrix-baserede og forbundet-liste baseret på.

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

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

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