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

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

3
00:00:07,370 --> 00:00:09,870
Dette er trolig kommer til å føle seg
som en liten bit av déjà vu.

4
00:00:09,870 --> 00:00:13,850
Det kommer til et veldig lignende konsept,
bare med en liten vri på den.

5
00:00:13,850 --> 00:00:15,530
Vi kommer til å snakke nå om køer.

6
00:00:15,530 --> 00:00:19,350
Slik at en kø, ligner på en stabel,
er en annen form for datastruktur

7
00:00:19,350 --> 00:00:22,412
som vi kan bruke til å vedlikeholde
data på en organisert måte.

8
00:00:22,412 --> 00:00:24,120
I likhet med en stabel,
det kan gjennomføres

9
00:00:24,120 --> 00:00:27,000
som en matrise eller en lenket liste.

10
00:00:27,000 --> 00:00:30,320
I motsetning til en stabel, reglene
som vi bruker for å bestemme

11
00:00:30,320 --> 00:00:34,210
når ting blir lagt til og fjernet fra
en kø er litt annerledes.

12
00:00:34,210 --> 00:00:36,590
>> I motsetning til en stabel, hvilken
er en LIFO struktur,

13
00:00:36,590 --> 00:00:45,610
sist inn, først ut er en kø en FIFO
struktur, FIFO, først inn, først ut.

14
00:00:45,610 --> 00:00:49,320
Nå køer, har du sannsynligvis
har en analogi til køer.

15
00:00:49,320 --> 00:00:52,820
Hvis du noen gang har vært i kø på
en fornøyelsespark eller i en bank,

16
00:00:52,820 --> 00:00:56,430
det er liksom en fairness
implementere struktur.

17
00:00:56,430 --> 00:00:59,160
Den første personen i kø på
Banken er den første personen

18
00:00:59,160 --> 00:01:00,760
hvem som får snakke med fortelleren.

19
00:01:00,760 --> 00:01:03,522
>> Det ville være en slags rase
til bunnen dersom den eneste måten

20
00:01:03,522 --> 00:01:06,730
du fikk til å snakke med teller på
banken var å være den siste personen i kø.

21
00:01:06,730 --> 00:01:09,146
Alle ville alltid vil
å være den siste personen i kø,

22
00:01:09,146 --> 00:01:12,580
og personen som var der først
som har ventet på en stund,

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

24
00:01:14,715 --> 00:01:17,590
før de har en sjanse til å faktisk
ta ut penger i banken.

25
00:01:17,590 --> 00:01:22,510
Og så køene er liksom den
rettferdighet implementere struktur.

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

27
00:01:25,780 --> 00:01:28,160
at køene er en annen måte å gjøre det.

28
00:01:28,160 --> 00:01:32,420
Så igjen en kø er først inn, først
ut, versus en stabel som sist inn,

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

30
00:01:34,440 --> 00:01:36,190
I likhet med en stabel,
vi har to operasjoner

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

32
00:01:38,470 --> 00:01:43,910
Navnene er enqueue, som er å legge
et nytt element til slutten av køen,

33
00:01:43,910 --> 00:01:47,330
og dequeue, som er
for å fjerne den eldste

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

35
00:01:49,670 --> 00:01:53,600
Så vi kommer til å legge til elementer
på slutten av køen,

36
00:01:53,600 --> 00:01:57,220
og vi kommer til å fjerne elementer
fra forsiden av køen.

37
00:01:57,220 --> 00:02:00,790
Igjen, med bunken, ble vi legger til
elementer til toppen av bunken

38
00:02:00,790 --> 00:02:03,380
og fjerne elementer
fra toppen av bunken.

39
00:02:03,380 --> 00:02:07,570
Så med enqueue, det er å legge til
Til slutt fjernes fra forsiden.

40
00:02:07,570 --> 00:02:10,639
Så den eldste ting der
er alltid den neste tingen

41
00:02:10,639 --> 00:02:13,620
å komme ut hvis vi prøver
og dequeue noe.

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

43
00:02:18,330 --> 00:02:20,110
og knyttet-liste basert implementeringer.

44
00:02:20,110 --> 00:02:24,620
Vi starter igjen med
arraybaserte implementeringer.

45
00:02:24,620 --> 00:02:27,070
Strukturen definisjon
ser ganske lik.

46
00:02:27,070 --> 00:02:30,720
Vi har et annet utvalg
det av datatype verdi,

47
00:02:30,720 --> 00:02:32,690
slik at den kan holde vilkårlige datatyper.

48
00:02:32,690 --> 00:02:35,570
Vi igjen kommer til å bruke
heltall i dette eksempelet.

49
00:02:35,570 --> 00:02:39,830
>> Og akkurat som med vår
matrise-baserte stabelen implementering,

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

51
00:02:42,340 --> 00:02:46,850
har den begrensningen at C slag
av håndhever på oss, som er vi

52
00:02:46,850 --> 00:02:51,670
har ikke noe dynamikk i vår
evne til å vokse og krympe matrisen.

53
00:02:51,670 --> 00:02:55,710
Vi må bestemme på begynnelsen
hva er det maksimale antall ting

54
00:02:55,710 --> 00:02:59,300
at vi kan sette inn i dette
kø, og i dette tilfellet

55
00:02:59,300 --> 00:03:02,070
kapasiteten vil være noen pund
definert konstant i koden vår.

56
00:03:02,070 --> 00:03:05,430
Og i forbindelse med denne
video, er kapasiteten kommer til å være 10.

57
00:03:05,430 --> 00:03:07,690
>> Vi trenger å holde styr på
foran i køen

58
00:03:07,690 --> 00:03:11,160
slik at vi vet hvilke element
vi ønsker å dequeue,

59
00:03:11,160 --> 00:03:15,070
og vi må også holde styr på
noe else-- antallet elementer

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
Legg merke vi ikke å holde styr
på slutten av køen, bare

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

63
00:03:21,150 --> 00:03:24,310
Og grunnen til det vil forhåpentligvis
bli litt klarere i et øyeblikk.

64
00:03:24,310 --> 00:03:26,143
Når vi har fullført
denne typen definisjon,

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

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

67
00:03:30,630 --> 00:03:35,350
Og litt forvirrende, jeg har bestemt meg
å kalle denne køen q, bokstaven

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

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

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

71
00:03:40,700 --> 00:03:45,730
Den inneholder tre medlemmer eller tre-
felt, en rekke størrelse KAPASITET.

72
00:03:45,730 --> 00:03:47,340
I dette tilfellet er KAPASITET 10.

73
00:03:47,340 --> 00:03:49,580
Og denne matrisen er
kommer til å holde heltall.

74
00:03:49,580 --> 00:03:55,240
I grønn er forsiden av vår køen,
ved siden av elementet som skal fjernes, og i rødt

75
00:03:55,240 --> 00:03:58,610
vil være størrelsen på køen,
hvor mange elementer er for tiden

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 sier q.front equals
0, og q.size størrelse tilsvarer 0--

78
00:04:05,300 --> 00:04:07,120
vi setter 0s inn i disse feltene.

79
00:04:07,120 --> 00:04:11,070
Og på dette punktet, er vi ganske mye
klar til å begynne å jobbe med våre køen.

80
00:04:11,070 --> 00:04:14,140
>> Så den første operasjonen vi kan
utføre er å Enqueue noe,

81
00:04:14,140 --> 00:04:16,860
å legge til et nytt element til
slutten av køen.

82
00:04:16,860 --> 00:04:19,089
Vel hva trenger vi å
gjøre i det generelle tilfellet?

83
00:04:19,089 --> 00:04:23,690
Vel denne funksjonen Enqueue behov
å akseptere en peker til vår køen.

84
00:04:23,690 --> 00:04:26,370
Igjen, hvis vi hadde erklært
vår køen globalt,

85
00:04:26,370 --> 00:04:29,490
vi ville ikke trenger å gjøre dette
nødvendigvis, men generelt, vi

86
00:04:29,490 --> 00:04:32,330
må godta pekere
til datastrukturer

87
00:04:32,330 --> 00:04:35,040
som dette, fordi ellers
vi er forbi value-- vi er

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

89
00:04:38,140 --> 00:04:41,050
køen som vi har tenkt å endre.

90
00:04:41,050 --> 00:04:44,860
>> Den andre tingen den trenger å gjøre er å akseptere
et dataelement av riktig type.

91
00:04:44,860 --> 00:04:46,818
Igjen, i dette tilfellet, er det
kommer til å være heltall,

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

93
00:04:49,330 --> 00:04:51,160
og bruke dette mer generelt.

94
00:04:51,160 --> 00:04:56,030
Det er elementet vi ønsker å Enqueue,
vi ønsker å legge til enden av køen.

95
00:04:56,030 --> 00:04:58,573
Så vi faktisk ønsker å
plasserer disse dataene i køen.

96
00:04:58,573 --> 00:05:01,490
I dette tilfellet, å plassere den i
riktig plassering av vårt utvalg,

97
00:05:01,490 --> 00:05:05,040
og da vi ønsker å endre størrelsen
av køen, hvor mange elementer vi

98
00:05:05,040 --> 00:05:07,050
for tiden.

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

100
00:05:07,990 --> 00:05:10,890
Her er igjen, at generell
skjema funksjon erklæring

101
00:05:10,890 --> 00:05:13,980
for hva enqueue kan se ut.

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

103
00:05:14,910 --> 00:05:18,335
La oss Enqueue antall
28 inn i køen.

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

105
00:05:19,460 --> 00:05:23,390
Vel, er det foran våre kø
på 0, og størrelsen på vår kø

106
00:05:23,390 --> 00:05:29,680
er på 0, og så vi ønsker sannsynligvis å sette
antall 28 i array element nummer

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

108
00:05:31,124 --> 00:05:32,540
Så vi har nå lagt den inn der.

109
00:05:32,540 --> 00:05:34,820
Så nå hva trenger vi å endre?

110
00:05:34,820 --> 00:05:37,090
Vi ønsker ikke å endre
foran i køen,

111
00:05:37,090 --> 00:05:40,850
fordi vi ønsker å vite hva element
vi må kanskje dequeue senere.

112
00:05:40,850 --> 00:05:44,020
Så grunnen til at vi har foran der
er liksom en indikator på hva som er

113
00:05:44,020 --> 00:05:46,439
den eldste tingen i matrisen.

114
00:05:46,439 --> 00:05:49,730
Vel den eldste tingen i array-- i
Faktisk, den eneste i rekken riktig

115
00:05:49,730 --> 00:05:53,540
now-- er 28, noe som er
på rekke plassering 0.

116
00:05:53,540 --> 00:05:56,160
Så vi ønsker ikke å
endre det grønne nummeret,

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

118
00:05:57,910 --> 00:06:00,510
Snarere, vi ønsker å endre størrelsen.

119
00:06:00,510 --> 00:06:04,110
Så i dette tilfellet, vil vi
øke størrelsen til en.

120
00:06:04,110 --> 00:06:08,430
>> Nå en generell slags idé om hvor
neste elementet kommer til å gå i en kø

121
00:06:08,430 --> 00:06:12,310
er å legge til disse to tallene
sammen, front og størrelse,

122
00:06:12,310 --> 00:06:16,390
og som vil fortelle deg hvor neste
element i køen kommer til å gå.

123
00:06:16,390 --> 00:06:18,130
Så nå la oss Enqueue et annet nummer.

124
00:06:18,130 --> 00:06:20,250
La oss Enqueue 33.

125
00:06:20,250 --> 00:06:24,480
Så 33 kommer til å gå inn
matrise plassering 0 pluss 1.

126
00:06:24,480 --> 00:06:26,840
Så i dette tilfellet, det kommer
å gå inn i rekke områder 1,

127
00:06:26,840 --> 00:06:29,500
og nå på størrelse med vår køen er 2.

128
00:06:29,500 --> 00:06:31,840
>> Igjen, vi er ikke i endring
forsiden av våre kø,

129
00:06:31,840 --> 00:06:34,730
fordi 28 er fremdeles
eldste element, og vi

130
00:06:34,730 --> 00:06:38,220
Vil to-- når vi til slutt får
til dequeuing, fjerne elementer

131
00:06:38,220 --> 00:06:43,300
fra denne køen, ønsker vi å vite
der den eldste element er.

132
00:06:43,300 --> 00:06:48,620
Og så må vi alltid å opprettholde
noen indikator på hvor det er.

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

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

135
00:06:52,910 --> 00:06:55,022
>> La oss i enqueue ett element, 19.

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

137
00:06:56,980 --> 00:06:59,860
Det kommer til å gå inn
matrise plassering nummer to.

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

139
00:07:01,570 --> 00:07:03,199
Og nå på størrelse med vår køen er 3.

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

141
00:07:04,240 --> 00:07:08,490
Så hvis vi skulle, og vi kommer ikke til
til akkurat nå, Enqueue et annet element,

142
00:07:08,490 --> 00:07:11,370
det ville gå inn i matrisen plassering
nummer 3, og størrelsen på vår kø

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

144
00:07:13,160 --> 00:07:15,279
Så vi har enqueued flere elementer nå.

145
00:07:15,279 --> 00:07:16,570
Nå la oss begynne å fjerne dem.

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

147
00:07:19,450 --> 00:07:23,340
>> Så lik pop, som er slags
på analog av denne for stabler

148
00:07:23,340 --> 00:07:26,180
dequeue må akseptere en
pekeren til queue-- igjen,

149
00:07:26,180 --> 00:07:28,140
med mindre det er globalt deklarert.

150
00:07:28,140 --> 00:07:31,610
Nå ønsker vi å endre plasseringen
på forsiden av køen.

151
00:07:31,610 --> 00:07:35,050
Det er der det liksom kommer
inn i bildet, den fronten 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
å flytte den til neste eldste element.

154
00:07:40,720 --> 00:07:44,180
>> Da ønsker vi å redusere
størrelsen på køen,

155
00:07:44,180 --> 00:07:47,130
og da vi ønsker å returnere verdien
som ble fjernet fra køen.

156
00:07:47,130 --> 00:07:48,921
Igjen, vi ønsker ikke å bare forkaste det.

157
00:07:48,921 --> 00:07:51,170
Vi antagelig pakker ut
det fra queue-- vi er

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

159
00:07:54,170 --> 00:08:01,080
Så vi ønsker denne funksjonen til å returnere
et dataelement av type verdi.

160
00:08:01,080 --> 00:08:04,360
Igjen, i dette tilfellet, er verdien heltall.

161
00:08:04,360 --> 00:08:05,670
>> Så nå la oss dequeue noe.

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

163
00:08:09,310 --> 00:08:15,970
Hvis vi sier int x lik & q, ampersand q--
igjen det er en peker til denne q data

164
00:08:15,970 --> 00:08:20,177
structure-- hva element
kommer til å bli dequeued?

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

166
00:08:23,840 --> 00:08:29,480
I dette tilfelle, fordi det er en første
inn, først ut datastruktur, FIFO,

167
00:08:29,480 --> 00:08:33,690
Det første vi legger i dette
Køen var 28, og slik at i dette tilfellet,

168
00:08:33,690 --> 00:08:37,245
vi kommer til å ta 28 av
køen, ikke 19, som er hva

169
00:08:37,245 --> 00:08:38,870
vi ville ha gjort hvis dette var en stabel.

170
00:08:38,870 --> 00:08:42,220
Vi kommer til å ta 28 ut av køen.

171
00:08:42,220 --> 00:08:44,960
>> I likhet med hva vi gjorde med
en stabel, vi er faktisk ikke

172
00:08:44,960 --> 00:08:47,345
kommer til å slette 28
fra køen selv,

173
00:08:47,345 --> 00:08:49,470
vi skal bare snill
av late som om det ikke er der.

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

175
00:08:51,678 --> 00:08:57,820
kommer til slags ignorere det ved å flytte
de to andre felt 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 kommer til å endre forsiden.

178
00:09:00,230 --> 00:09:04,290
Q.front skal nå
være en, fordi det er nå

179
00:09:04,290 --> 00:09:07,740
den eldste elementet vi har i vår
køen, fordi vi allerede har fjernet 28,

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

181
00:09:10,460 --> 00:09:13,540
>> Og nå, vi ønsker å endre
størrelsen på 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
Nå husker tidligere jeg sa når vi
ønsker å legge til elementer i køen,

184
00:09:20,450 --> 00:09:26,000
vi setter det i en matrise sted
som er summen av fronten og størrelse.

185
00:09:26,000 --> 00:09:29,050
Så i dette tilfellet, er vi fremdeles sette
det, det neste elementet i køen,

186
00:09:29,050 --> 00:09:33,360
i matrisen plassering 3, og
vi får se det i et sekund.

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

188
00:09:35,730 --> 00:09:36,480
La oss gjøre det igjen.

189
00:09:36,480 --> 00:09:38,696
La oss ta et annet
element fra køen.

190
00:09:38,696 --> 00:09:42,400
I det tilfelle gjeldende eldste
element er rekke områder 1.

191
00:09:42,400 --> 00:09:44,220
Det er hva q.front forteller oss.

192
00:09:44,220 --> 00:09:46,980
Det grønne boksen forteller oss at
det er den eldste element.

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

194
00:09:49,310 --> 00:09:52,130
Vi vil bare slags glemme
som 33 eksisterer i matrisen,

195
00:09:52,130 --> 00:09:55,100
og vi vil si at nå, det
ny eldste element i køen

196
00:09:55,100 --> 00:09:58,900
er på rekke plassering 2, og størrelsen
av køen, antall elementer

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

198
00:10:02,152 --> 00:10:05,110
Nå la oss Enqueue noe, og jeg
slags ga dette bort en andre siden,

199
00:10:05,110 --> 00:10:10,340
men hvis vi ønsker å sette 40 inn i
køen, der er 40 kommer til å gå?

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

201
00:10:12,880 --> 00:10:17,730
Vel, vi har vært å sette det
i q.front pluss kø størrelse,

202
00:10:17,730 --> 00:10:20,850
og så det er fornuftig å
faktisk å sette 40 her.

203
00:10:20,850 --> 00:10:22,840
Nå merker at i
enkelte punkt, skal vi

204
00:10:22,840 --> 00:10:27,980
for å komme til enden av
vår rekke innsiden av q,

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

206
00:10:32,010 --> 00:10:33,300
åpne plasser, ikke sant?

207
00:10:33,300 --> 00:10:36,040
Og så kan vi eventually--
som regel med å legge

208
00:10:36,040 --> 00:10:40,390
disse to together-- vi kan til slutt
må mod av størrelsen på kapasitet

209
00:10:40,390 --> 00:10:41,410
slik at vi kan vikle seg rundt.

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

211
00:10:43,620 --> 00:10:48,790
erstatte den i element nummer 10, ville vi
faktisk sette den i matrisen plassering 0.

212
00:10:48,790 --> 00:10:50,997
Og hvis vi skulle
matrise beliggenhet-- unnskylde meg,

213
00:10:50,997 --> 00:10:53,080
hvis vi har lagt dem opp sammen,
og vi fikk nummer

214
00:10:53,080 --> 00:10:56,330
11 ville være der vi måtte sette
den, noe som ikke eksisterer i denne array--

215
00:10:56,330 --> 00:10:58,200
det ville være å gå ut av banen.

216
00:10:58,200 --> 00:11:03,367
Vi kunne mod med 10 og sette
det i matrisen plassering 1.

217
00:11:03,367 --> 00:11:04,450
Så det er hvordan køer fungere.

218
00:11:04,450 --> 00:11:08,540
De er alltid kommer til å gå fra venstre
til høyre og muligens vikle rundt.

219
00:11:08,540 --> 00:11:11,280
Og du vet at de er
full hvis størrelse, at røde boksen,

220
00:11:11,280 --> 00:11:13,710
blir lik kapasitet.

221
00:11:13,710 --> 00:11:16,720
Og så etter at vi har lagt 40 til
køen, vel hva trenger vi å gjøre?

222
00:11:16,720 --> 00:11:19,890
Vel, den eldste element
i køen er fortsatt 19,

223
00:11:19,890 --> 00:11:21,990
slik at vi ikke ønsker å endre
foran i køen,

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

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

226
00:11:28,710 --> 00:11:31,820
>> Det er ganske mye det med
arbeider med tabellbaserte køer,

227
00:11:31,820 --> 00:11:33,630
og lignende for å stable,
Det er også en vei

228
00:11:33,630 --> 00:11:36,450
å gjennomføre en kø som en lenket liste.

229
00:11:36,450 --> 00:11:40,150
Nå hvis dette datastruktur typen
ser kjent ut for deg, er det.

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

231
00:11:43,780 --> 00:11:46,790
Og nå, som en side, er det
faktisk mulig å gjennomføre

232
00:11:46,790 --> 00:11:50,160
en kø som en enkeltvis lenket liste, men
Jeg tenker i form av visualisering,

233
00:11:50,160 --> 00:11:53,350
det kan faktisk bidra til å vise
dette som en dobbelt lenket liste.

234
00:11:53,350 --> 00:11:56,850
Men det er absolutt mulig å
gjøre dette som en enkeltvis lenket liste.

235
00:11:56,850 --> 00:12:00,110
>> Så la oss ta en titt på
hva dette kan se ut.

236
00:12:00,110 --> 00:12:02,750
Hvis vi ønsker å enquue--
så nå, igjen er vi

237
00:12:02,750 --> 00:12:05,360
bytte til en koblet-liste
basert modell her.

238
00:12:05,360 --> 00:12:08,420
Hvis vi ønsker å Enqueue, vi ønsker
å legge til et nytt element, godt

239
00:12:08,420 --> 00:12:09,730
Hva må vi gjøre?

240
00:12:09,730 --> 00:12:12,770
Vel, først av alt, fordi
vi legger til slutten

241
00:12:12,770 --> 00:12:15,520
og fjerne fra
begynnelse, vi sannsynligvis

242
00:12:15,520 --> 00:12:20,050
ønsker å opprettholde pekere til både
hodet og halen av lenket liste?

243
00:12:20,050 --> 00:12:22,660
Halen er en annen betegnelse for
enden av lenket liste,

244
00:12:22,660 --> 00:12:24,496
det siste elementet i lenket liste.

245
00:12:24,496 --> 00:12:26,620
Og disse vil trolig,
igjen, være gunstig for oss

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

247
00:12:28,477 --> 00:12:31,060
Men nå hvis vi ønsker å legge til en ny
element hva har vi å gjøre?

248
00:12:31,060 --> 00:12:35,262
Hva vi bare [? malak?] eller dynamisk
fordele vår nye knutepunktet for oss selv.

249
00:12:35,262 --> 00:12:38,220
Og så, akkurat som når vi legger alle
element til en dobbelt lenket liste vi,

250
00:12:38,220 --> 00:12:40,410
må bare sortere of--
de tre siste trinnene her

251
00:12:40,410 --> 00:12:43,330
er bare om å flytte
pekere i den riktige måten

252
00:12:43,330 --> 00:12:46,710
slik at elementet blir lagt til
kjedet uten å bryte kjeden

253
00:12:46,710 --> 00:12:49,580
eller lage noen slags feil
eller å ha noen form for ulykke

254
00:12:49,580 --> 00:12:54,505
skje der vi tilfeldigvis
foreldreløs noen elementer av vår køen.

255
00:12:54,505 --> 00:12:55,880
Her er hva dette kan se ut.

256
00:12:55,880 --> 00:13:00,980
Vi ønsker å legge til elementet
10 til enden av denne køen.

257
00:13:00,980 --> 00:13:03,380
Så den eldste element her
er representert ved hodet.

258
00:13:03,380 --> 00:13:06,800
Det er det første vi legger
inn i dette hypotetiske kø her.

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

260
00:13:10,430 --> 00:13:17,030
Og så hvis vi ønsker å Enqueue 10 inn
denne køen, ønsker vi å sette det etter 13.

261
00:13:17,030 --> 00:13:19,860
Og så vi kommer til å dynamisk
tildele plass for en ny node

262
00:13:19,860 --> 00:13:23,280
og se etter null for å være sikker
vi ikke har en hukommelsessvikt.

263
00:13:23,280 --> 00:13:27,040
Så skal vi til
plassere 10 inn som node,

264
00:13:27,040 --> 00:13:30,030
og nå må vi være forsiktige
om hvordan vi organiserer pekere

265
00:13:30,030 --> 00:13:32,180
slik at vi ikke bryte kjeden.

266
00:13:32,180 --> 00:13:38,910
>> Vi kan sette 10 tidligere felt
å peke tilbake til den gamle halen,

267
00:13:38,910 --> 00:13:41,620
og siden '10 vil bli
ny hale på et tidspunkt

268
00:13:41,620 --> 00:13:44,459
da alle disse
kjedene er koblet til,

269
00:13:44,459 --> 00:13:46,250
ingenting kommer til å komme
etter 10 akkurat nå.

270
00:13:46,250 --> 00:13:49,880
Og så 10 neste pekeren
vil peke til null,

271
00:13:49,880 --> 00:13:53,580
og deretter etter at vi gjør dette, etter at vi har
koblet 10 bakover til kjeden,

272
00:13:53,580 --> 00:13:57,780
vi kan ta den gamle hodet, eller unnskyldning
meg, den gamle halen av køen.

273
00:13:57,780 --> 00:14:02,980
Den gamle slutten av køen,
13, og gjøre det vise til 10.

274
00:14:02,980 --> 00:14:08,220
Og nå, på dette punktet, har vi
enqueued tallet 10 i denne kø.

275
00:14:08,220 --> 00:14:14,740
Alt vi trenger å gjøre nå er bare å flytte
halen til å peke til 10 i stedet for til 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing er faktisk
meget lik dukker

277
00:14:17,630 --> 00:14:21,710
fra en stabel som er
implementert som en lenket liste

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

279
00:14:24,040 --> 00:14:27,280
Alt vi trenger å gjøre er å starte på
begynner, finne det andre elementet,

280
00:14:27,280 --> 00:14:30,480
frigjøre det første element,
og deretter bevege hodet

281
00:14:30,480 --> 00:14:32,930
for å peke på det andre elementet.

282
00:14:32,930 --> 00:14:37,920
Sannsynligvis bedre å visualisere det
bare for å være ekstra tydelig om det.

283
00:14:37,920 --> 00:14:39,230
Så her er vår køen igjen.

284
00:14:39,230 --> 00:14:42,600
12 er den eldste element
i vår kø, hodet.

285
00:14:42,600 --> 00:14:46,210
10 er det nyeste elementet
i vår kø, vår hale.

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

287
00:14:49,310 --> 00:14:52,202
vi ønsker å fjerne den eldste element.

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

289
00:14:52,910 --> 00:14:55,243
Vel vi satt en traversering peker
som starter på hodet,

290
00:14:55,243 --> 00:14:57,840
og vi flytte det slik at det
peker mot det andre elementet

291
00:14:57,840 --> 00:15:02,290
av denne queue-- noe ved å si trav
tilsvarer trav-pilen ved, for eksempel,

292
00:15:02,290 --> 00:15:07,170
ville flytte trav det å peke på
15, som etter vi dequeue 12,

293
00:15:07,170 --> 00:15:13,030
eller etter at vi fjerner 12, vil
bli den daværende eldste element.

294
00:15:13,030 --> 00:15:16,360
>> Nå har vi fått tak på den første
element via pekeren hodet

295
00:15:16,360 --> 00:15:19,440
og det andre element
via pekeren trav.

296
00:15:19,440 --> 00:15:25,170
Vi kan nå gratis hodet, og så kan vi
sier ingenting kommer før 15 lenger.

297
00:15:25,170 --> 00:15:29,990
Så vi kan endre 15 tidligere
pekeren til å peke til null,

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

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

300
00:15:32,540 --> 00:15:35,840
Nå har vi lykkes
dequeued 12, og nå er vi

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

302
00:15:39,180 --> 00:15:41,700
Det er ganske mye alt
det er til køer,

303
00:15:41,700 --> 00:15:45,810
både matrise-basert og knyttet-liste basert.

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