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

2
00:00:05,204 --> 00:00:07,370
DOUG LLOYD: Kaya kung na sa iyo
pinapanood ang mga video sa stack,

3
00:00:07,370 --> 00:00:09,870
ito ay marahil pagpunta sa pakiramdam
tulad ng isang maliit na piraso ng deja vu.

4
00:00:09,870 --> 00:00:13,850
Ito ay pagpunta sa isang halos katulad na konsepto,
sa pamamagitan lamang ng isang bahagyang iba ng kahulugan sa mga ito.

5
00:00:13,850 --> 00:00:15,530
Kami ay pagpunta sa makipag-usap ngayon tungkol sa queue.

6
00:00:15,530 --> 00:00:19,350
Kaya isang pila, katulad ng isang stack,
ay isa pang uri ng mga istraktura ng data

7
00:00:19,350 --> 00:00:22,412
na maaari naming gamitin upang mapanatili ang
data sa isang organisadong paraan.

8
00:00:22,412 --> 00:00:24,120
Katulad sa isang stack,
ito ay ipinatupad

9
00:00:24,120 --> 00:00:27,000
bilang isang array o isang listahan ng mga link.

10
00:00:27,000 --> 00:00:30,320
Hindi tulad ng isang stack, ang mga patakaran
na ginagamit namin upang matukoy

11
00:00:30,320 --> 00:00:34,210
kapag ang mga bagay makakuha ng idinagdag at inalis mula sa
isang pila ay Medyo naiiba.

12
00:00:34,210 --> 00:00:36,590
>> Hindi tulad ng isang stack, na
ay isang istraktura LIFO,

13
00:00:36,590 --> 00:00:45,610
huling in, unang-out, isang pila ay isang FIFO
istraktura, FIFO, sa unang, unang out.

14
00:00:45,610 --> 00:00:49,320
Ngayon queues, ikaw ay malamang na
Mayroon isang pagkakatulad sa queue.

15
00:00:49,320 --> 00:00:52,820
Kung sakaling kayo ay sa linya sa
isang amusement park o sa isang bangko,

16
00:00:52,820 --> 00:00:56,430
may uri ng isang pagkamakatarungan
pagpapatupad ng istraktura.

17
00:00:56,430 --> 00:00:59,160
Ang unang tao sa linya sa
ang bangko ay ang unang tao

18
00:00:59,160 --> 00:01:00,760
sino upang makipag-usap sa teller.

19
00:01:00,760 --> 00:01:03,522
>> Gusto Ito ay uri ng isang lahi
hanggang sa ibaba kung ang tanging paraan

20
00:01:03,522 --> 00:01:06,730
nakuha mo na magsalita sa mga teller sa
bank ay upang maging ang huling tao sa linya.

21
00:01:06,730 --> 00:01:09,146
Laging gusto ng lahat ng tao
na ang huling tao sa linya,

22
00:01:09,146 --> 00:01:12,580
at ang mga tao na noon ay doon muna
sino ay naghihintay para sa isang habang,

23
00:01:12,580 --> 00:01:14,715
maaaring doon para sa oras,
at oras, at oras

24
00:01:14,715 --> 00:01:17,590
bago sila magkaroon ng pagkakataon na talagang
withdraw ng pera sa bangko.

25
00:01:17,590 --> 00:01:22,510
At kaya queue ay isang uri ng
pagkamakatarungan pagpapatupad istraktura.

26
00:01:22,510 --> 00:01:25,780
Ngunit iyon ay hindi nangangahulugan na
na stack ay isang masamang bagay, lamang

27
00:01:25,780 --> 00:01:28,160
na queue ay isa pang paraan upang gawin ito.

28
00:01:28,160 --> 00:01:32,420
Kaya muli isang pila ay sa unang, unang
out, kumpara sa isang stack na huling in,

29
00:01:32,420 --> 00:01:34,440
out muna.

30
00:01:34,440 --> 00:01:36,190
Katulad sa isang stack,
kami ay may dalawang mga operasyon

31
00:01:36,190 --> 00:01:38,470
maaari naming gawin sa queue.

32
00:01:38,470 --> 00:01:43,910
Ang mga pangalan ay enqueue, na kung saan ay ang magdagdag
ng isang bagong sangkap sa dulo ng pila,

33
00:01:43,910 --> 00:01:47,330
at dequeue, na kung saan ay
alisin ang pinakaluma

34
00:01:47,330 --> 00:01:49,670
elemento mula sa harap ng pila.

35
00:01:49,670 --> 00:01:53,600
Kaya kami ay pagpunta sa magdagdag ng mga elemento
papunta sa dulo ng pila,

36
00:01:53,600 --> 00:01:57,220
at kami ay pagpunta sa alisin ang mga elemento
mula sa harap ng pila.

37
00:01:57,220 --> 00:02:00,790
Muli, sa stack, ay namin ang pagdaragdag
mga elemento sa itaas ng stack

38
00:02:00,790 --> 00:02:03,380
at pag-aalis ng mga elemento
mula sa tuktok ng stack.

39
00:02:03,380 --> 00:02:07,570
Kaya sa enqueue, ito ay ang pagdaragdag sa
Sa katapusan, pag-alis mula sa harap.

40
00:02:07,570 --> 00:02:10,639
Kaya ang pinakaluma bagay sa doon
palaging ay ang susunod na bagay

41
00:02:10,639 --> 00:02:13,620
sa labas kung susubukan namin
at dequeue isang bagay.

42
00:02:13,620 --> 00:02:18,330
>> Kaya muli, sa queue, maaari naming
pagpapatupad array-based

43
00:02:18,330 --> 00:02:20,110
at naka-link-list batay pagpapatupad.

44
00:02:20,110 --> 00:02:24,620
Sisimulan naming muli gamit
array-based na pagpapatupad.

45
00:02:24,620 --> 00:02:27,070
Ang kahulugan ng istraktura
mukhang medyo katulad.

46
00:02:27,070 --> 00:02:30,720
Mayroon kaming isa pang array
doon ng halaga uri ng data,

47
00:02:30,720 --> 00:02:32,690
kaya ito ay maaaring humawak ng arbitrary uri ng data.

48
00:02:32,690 --> 00:02:35,570
Muli Kami ay pagpunta sa gamitin ang
integer sa halimbawang ito.

49
00:02:35,570 --> 00:02:39,830
>> At tulad ng sa aming mga
array-based stack pagpapatupad,

50
00:02:39,830 --> 00:02:42,340
dahil kami ay gumagamit ng isang
array, kami ay palaging

51
00:02:42,340 --> 00:02:46,850
Mayroon limitasyon na na C uri
ng nagpapatupad ka sa amin, na kung saan ay namin

52
00:02:46,850 --> 00:02:51,670
walang anumang dynamism sa ating
kakayahan sa paglaki at pag-urong ng array.

53
00:02:51,670 --> 00:02:55,710
Mayroon kaming upang magpasya sa simula
kung ano ang pinakamataas na bilang ng mga bagay-bagay

54
00:02:55,710 --> 00:02:59,300
na maaari naming ilagay sa ito
pila, at sa kasong ito,

55
00:02:59,300 --> 00:03:02,070
kapasidad ay ang ilang pound
tinukoy pare-pareho sa aming mga code.

56
00:03:02,070 --> 00:03:05,430
At para sa mga layunin ng
video, kapasidad ay magiging 10.

57
00:03:05,430 --> 00:03:07,690
>> Kailangan namin upang subaybayan ang mga
sa harap ng pila

58
00:03:07,690 --> 00:03:11,160
upang malaman namin kung aling mga elemento
gusto naming dequeue,

59
00:03:11,160 --> 00:03:15,070
at kailangan din namin upang subaybayan ang mga
isang bagay else-- ang bilang ng mga elemento

60
00:03:15,070 --> 00:03:16,690
na mayroon kami sa aming pila.

61
00:03:16,690 --> 00:03:19,360
Pansinin na hindi kami nag-iingat subaybayan
mga dulo ng pila, makatarungan

62
00:03:19,360 --> 00:03:21,150
ang laki ng queue.

63
00:03:21,150 --> 00:03:24,310
At ang mga dahilan para sa na ay inaasahan namin na
maging mas malinaw ng kaunti sa isang sandali.

64
00:03:24,310 --> 00:03:26,143
Kapag nakumpleto namin
sa ganitong uri ng kahulugan,

65
00:03:26,143 --> 00:03:29,080
kami ay may isang bagong uri ng data
tinatawag queue, na kung saan maaari naming ngayon

66
00:03:29,080 --> 00:03:30,630
magpahayag ng variable na ng uri ng data.

67
00:03:30,630 --> 00:03:35,350
At medyo confusingly, ako ay nagpasya
upang tumawag queue q ito, ang mga titik

68
00:03:35,350 --> 00:03:38,090
q sa halip na ang uri ng data q.

69
00:03:38,090 --> 00:03:39,600
>> Kaya dito ay ang aming queue.

70
00:03:39,600 --> 00:03:40,700
Ito ay isang istraktura.

71
00:03:40,700 --> 00:03:45,730
Ito ay naglalaman ng tatlong miyembro o tatlong
larangan, isang hanay ng mga laki ng kapasidad.

72
00:03:45,730 --> 00:03:47,340
Sa kasong ito, kapasidad ay 10.

73
00:03:47,340 --> 00:03:49,580
At ito array ay
pagpunta sa hold integer.

74
00:03:49,580 --> 00:03:55,240
Sa green ay ang harap ng aming pila, ang
susunod na elemento na aalisin, at sa pula

75
00:03:55,240 --> 00:03:58,610
ay ang laki ng pila,
kung gaano karaming mga elemento ay kasalukuyan

76
00:03:58,610 --> 00:04:01,190
umiiral sa queue.

77
00:04:01,190 --> 00:04:05,300
Kaya kung sinasabi namin q.front equals
0, at laki q.size katumbas 0--

78
00:04:05,300 --> 00:04:07,120
kami ay paglalagay ng 0s sa mga patlang.

79
00:04:07,120 --> 00:04:11,070
At sa puntong ito, hindi namin medyo marami
handa na upang simulan ang nagtatrabaho sa aming pila.

80
00:04:11,070 --> 00:04:14,140
>> Kaya ang unang operasyon ng aming makakaya
maisagawa ay upang enqueue ang isang bagay,

81
00:04:14,140 --> 00:04:16,860
upang magdagdag ng isang bagong sangkap sa
ang dulo ng pila.

82
00:04:16,860 --> 00:04:19,089
Well kung ano ang kailangan namin upang
gawin sa pangkalahatang kaso?

83
00:04:19,089 --> 00:04:23,690
Well ang function na ito enqueue pangangailangan
upang tanggapin ang isang pointer sa aming pila.

84
00:04:23,690 --> 00:04:26,370
Muli, kung maisaysay na namin
aming queue globally,

85
00:04:26,370 --> 00:04:29,490
hindi namin kailangan upang gawin ito
kinakailangan, ngunit sa pangkalahatan, kami ay

86
00:04:29,490 --> 00:04:32,330
kailangang tanggapin payo
na istruktura ng data

87
00:04:32,330 --> 00:04:35,040
tulad nito, dahil kung hindi man,
kami ay pagpasa sa pamamagitan value-- hindi namin

88
00:04:35,040 --> 00:04:38,140
pagpasa sa kopya ng pila,
at sa gayon kami ay hindi tunay na pagbabago

89
00:04:38,140 --> 00:04:41,050
pila na balak namin na baguhin.

90
00:04:41,050 --> 00:04:44,860
>> Ang iba pang mga bagay na kinakailangan nito upang gawin ay tanggapin
isang elemento ng data sa mga naaangkop na uri.

91
00:04:44,860 --> 00:04:46,818
Muli, sa kasong ito, ito ay
magiging integer,

92
00:04:46,818 --> 00:04:49,330
ngunit maaari mong nagkataon
Ipinahahayag ng mga uri ng data bilang halaga

93
00:04:49,330 --> 00:04:51,160
at gamitin ito sa mas pangkalahatang.

94
00:04:51,160 --> 00:04:56,030
Iyan ay ang elemento na gusto naming enqueue,
gusto naming idagdag sa dulo ng pila.

95
00:04:56,030 --> 00:04:58,573
Pagkatapos talaga namin nais na
ilagay ang data na iyon sa pila.

96
00:04:58,573 --> 00:05:01,490
Sa kasong ito, ilagay ito sa
tamang lokasyon ng aming array,

97
00:05:01,490 --> 00:05:05,040
at pagkatapos ay gusto naming baguhin ang laki
ng pila, kung ilang mga elemento namin

98
00:05:05,040 --> 00:05:07,050
may kasalukuyang.

99
00:05:07,050 --> 00:05:07,990
>> Kaya sabihin makapagsimula.

100
00:05:07,990 --> 00:05:10,890
Narito ang, muli, na pangkalahatang
anyo function deklarasyon

101
00:05:10,890 --> 00:05:13,980
para sa kung ano ang maaaring enqueue hitsura.

102
00:05:13,980 --> 00:05:14,910
At ayan na naman.

103
00:05:14,910 --> 00:05:18,335
Enqueue ni ang bilang Ipaalam
28 sa queue.

104
00:05:18,335 --> 00:05:19,460
Kaya ano pa ang gagawin natin?

105
00:05:19,460 --> 00:05:23,390
Well, sa harap ng aming pila ay
sa 0, at ang laki ng aming mga queue

106
00:05:23,390 --> 00:05:29,680
ay sa 0, at kaya malamang na namin nais na ilagay ang
ang bilang 28 sa number element ng array

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

108
00:05:31,124 --> 00:05:32,540
Kaya ngayon inilagay namin na lumalabag sa doon.

109
00:05:32,540 --> 00:05:34,820
Kaya ngayon kung ano ang kailangan namin upang baguhin?

110
00:05:34,820 --> 00:05:37,090
Hindi namin nais na baguhin
sa harap ng pila,

111
00:05:37,090 --> 00:05:40,850
dahil gusto naming malaman kung ano ang element
maaaring kailanganin naming dequeue mamaya.

112
00:05:40,850 --> 00:05:44,020
Kaya ang dahilan na namin front doon
ay isang uri ng isang tagapagpahiwatig ng kung ano ang

113
00:05:44,020 --> 00:05:46,439
ang pinakalumang bagay sa array.

114
00:05:46,439 --> 00:05:49,730
Well ang pinakaluma bagay sa array-- in
katunayan, ang tanging bagay na sa array karapatan

115
00:05:49,730 --> 00:05:53,540
now-- ay 28, na kung saan ay
sa array lokasyon 0.

116
00:05:53,540 --> 00:05:56,160
Kaya hindi namin nais na
baguhin na green number,

117
00:05:56,160 --> 00:05:57,910
dahil iyon ang pinakaluma element.

118
00:05:57,910 --> 00:06:00,510
Sa halip, gusto naming baguhin ang laki.

119
00:06:00,510 --> 00:06:04,110
Kaya sa kasong ito, ipapakita namin
dagdagan size sa 1.

120
00:06:04,110 --> 00:06:08,430
>> Ngayon ang isang pangkalahatang uri ng ideya ng kung saan ang
susunod na elemento ay pagpunta sa pumunta sa isang queue

121
00:06:08,430 --> 00:06:12,310
ay upang magdagdag ng mga dalawang numero
sama-sama, ang harap at laki,

122
00:06:12,310 --> 00:06:16,390
at makikita na ang magsasabi sa iyo kung saan ang susunod
element sa pila ay pagpunta sa pumunta.

123
00:06:16,390 --> 00:06:18,130
Kaya enqueue ni isa pang numero ngayon hayaan.

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

125
00:06:20,250 --> 00:06:24,480
Kaya 33 ay pagpunta sa pumunta sa
array lokasyon 0 plus 1.

126
00:06:24,480 --> 00:06:26,840
Kaya sa kasong ito, ito ay pagpunta
upang pumunta sa lokasyon array 1,

127
00:06:26,840 --> 00:06:29,500
at ngayon ang laki ng aming pila ay 2.

128
00:06:29,500 --> 00:06:31,840
>> Muli, hindi namin binabago
sa harap ng aming pila,

129
00:06:31,840 --> 00:06:34,730
dahil 28 pa rin ang
pinakaluma element, at kami

130
00:06:34,730 --> 00:06:38,220
gusto to-- kapag huli naming makuha
upang dequeuing, pag-alis mga elemento

131
00:06:38,220 --> 00:06:43,300
na ito mula sa queue, gusto naming malaman
kung saan ang pinakaluma element ay.

132
00:06:43,300 --> 00:06:48,620
At kaya laging kailangan namin upang mapanatili ang
ilang tagapagpahiwatig ng kung saan na.

133
00:06:48,620 --> 00:06:50,410
Kaya na kung ano ang 0 ay may para sa.

134
00:06:50,410 --> 00:06:52,910
Iyon ay kung ano harap ay may para sa.

135
00:06:52,910 --> 00:06:55,022
>> Sabihin sa enqueue isa pang elemento, 19.

136
00:06:55,022 --> 00:06:56,980
Ako ba na maaari mong hulaan
kung saan 19 ay pagpunta sa pumunta.

137
00:06:56,980 --> 00:06:59,860
Ito ay pagpunta sa pumunta sa
array lokasyon number 2.

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

139
00:07:01,570 --> 00:07:03,199
At ngayon, ang laki ng aming mga queue ay 3.

140
00:07:03,199 --> 00:07:04,240
Kami ay may 3 mga elemento sa loob nito.

141
00:07:04,240 --> 00:07:08,490
Kaya kung kami ay sa, at hindi namin ang pagpunta
sa ngayon, enqueue isa pang elemento,

142
00:07:08,490 --> 00:07:11,370
ito ay pumunta sa lokasyon array
number 3, at ang laki ng aming mga queue

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

144
00:07:13,160 --> 00:07:15,279
Kaya enqueued namin ang ilang mga elemento na ngayon.

145
00:07:15,279 --> 00:07:16,570
Ngayon sabihin simulan upang alisin ang mga ito ipaalam.

146
00:07:16,570 --> 00:07:19,450
Dequeue ni ito mula sa queue Hayaan.

147
00:07:19,450 --> 00:07:23,340
>> Kaya katulad ng pop, na kung saan ay uri
ng analog ng ito para sa mga stack,

148
00:07:23,340 --> 00:07:26,180
pangangailangan dequeue upang tanggapin ang isang
pointer muli sa queue--,

149
00:07:26,180 --> 00:07:28,140
maliban kung globally ito ay ipinahayag.

150
00:07:28,140 --> 00:07:31,610
Ngayon gusto naming upang baguhin ang lokasyon
ng harap ng pila.

151
00:07:31,610 --> 00:07:35,050
Ito ay kung saan ito uri ng pagdating
sa play, na front variable,

152
00:07:35,050 --> 00:07:37,310
dahil sa sandaling namin tanggalin
isang elemento, gusto naming

153
00:07:37,310 --> 00:07:40,720
upang ilipat ito sa susunod na pinakamatandang element.

154
00:07:40,720 --> 00:07:44,180
>> Pagkatapos gusto naming bawasan
ang laki ng pila,

155
00:07:44,180 --> 00:07:47,130
at pagkatapos ay nais naming ibalik ang halaga
na ay tinanggal mula sa pila.

156
00:07:47,130 --> 00:07:48,921
Muli, hindi namin nais upang itapon lamang ito.

157
00:07:48,921 --> 00:07:51,170
Siguro Kami ay extract
ito mula sa mga queue-- hindi namin

158
00:07:51,170 --> 00:07:54,170
dequeuing ito dahil pinapahalagahan namin ang tungkol dito.

159
00:07:54,170 --> 00:08:01,080
Kaya gusto namin ang function na ito upang bumalik
isang elemento ng data ng halaga type.

160
00:08:01,080 --> 00:08:04,360
Muli, sa kasong ito, ang halaga ay integer.

161
00:08:04,360 --> 00:08:05,670
>> Kaya dequeue ni ng isang bagay sa ngayon.

162
00:08:05,670 --> 00:08:09,310
Alisin ni isang elemento mula sa pila Hayaan.

163
00:08:09,310 --> 00:08:15,970
Kung sinasabi nating int x ay katumbas ng & q, ampersand q--
muli na isang pointer sa q data

164
00:08:15,970 --> 00:08:20,177
structure-- ano element
ay magiging dequeued?

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

166
00:08:23,840 --> 00:08:29,480
Sa kasong ito, sapagkat ito ay isang unang
in, first out istraktura ng data, FIFO,

167
00:08:29,480 --> 00:08:33,690
ang unang bagay na namin ilagay sa ito
queue ay 28, at kaya sa kasong ito,

168
00:08:33,690 --> 00:08:37,245
kami ay pagpunta sa tumagal ng 28 labas ng
pila, hindi 19, na kung saan ay kung ano ang

169
00:08:37,245 --> 00:08:38,870
Gusto kaming ginawa kung ito ay isang stack.

170
00:08:38,870 --> 00:08:42,220
Kami ay pagpunta sa tumagal ng 28 labas ng queue.

171
00:08:42,220 --> 00:08:44,960
>> Katulad sa kung ano ang ginawa namin sa
isang stack, hindi kami talaga

172
00:08:44,960 --> 00:08:47,345
pagpunta sa tanggalin ang 28
mula sa pila mismo,

173
00:08:47,345 --> 00:08:49,470
lang namin ang pagpunta sa uri
ng magpanggap na ito ay hindi doon.

174
00:08:49,470 --> 00:08:51,678
Kaya ito ay pagpunta upang manatili doon
sa memorya, ngunit hindi namin lamang

175
00:08:51,678 --> 00:08:57,820
pagpunta sa uri ng balewalain ito sa pamamagitan ng paggalaw
ang iba pang dalawang mga patlang ng aming q data

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

177
00:08:58,830 --> 00:09:00,230
Kami ay pagpunta upang baguhin ang front.

178
00:09:00,230 --> 00:09:04,290
Q.front ngayon ay pagpunta sa
1, dahil iyon ay ngayon

179
00:09:04,290 --> 00:09:07,740
ang pinakalumang element na namin sa aming
pila, dahil mayroon na inalis na namin ang 28,

180
00:09:07,740 --> 00:09:10,460
na kung saan ay ang dating pinakaluma element.

181
00:09:10,460 --> 00:09:13,540
>> At ngayon, gusto naming baguhin
ang laki ng pila

182
00:09:13,540 --> 00:09:15,780
sa dalawang mga elemento sa halip na tatlo.

183
00:09:15,780 --> 00:09:20,450
Ngayon tandaan sinabi ko mas maaga kapag kami
nais na magdagdag ng mga elemento sa pila,

184
00:09:20,450 --> 00:09:26,000
inilalagay namin ang mga ito sa isang lokasyon array
na kung saan ay ang kabuuan ng harap at laki.

185
00:09:26,000 --> 00:09:29,050
Kaya sa kasong ito, hindi pa rin namin ang paglalagay ng
ito, ang susunod na elemento sa pila,

186
00:09:29,050 --> 00:09:33,360
sa array lokasyon 3, at
kami ay makikita na sa isang segundo.

187
00:09:33,360 --> 00:09:35,730
>> Kaya ngayon dequeued namin ang aming
unang elemento mula sa pila.

188
00:09:35,730 --> 00:09:36,480
Gawin natin ito muli.

189
00:09:36,480 --> 00:09:38,696
Ni alisin ang isa pang Ipaalam
elemento mula sa pila.

190
00:09:38,696 --> 00:09:42,400
Sa kaso, ang kasalukuyang pinakamatandang
element ay lokasyon array 1.

191
00:09:42,400 --> 00:09:44,220
Iyan ay kung ano ang sinasabi q.front amin.

192
00:09:44,220 --> 00:09:46,980
Sinasabi sa atin na ang berdeng kahon na
iyan ay ang pinakaluma element.

193
00:09:46,980 --> 00:09:49,310
At ito, x ay magiging 33.

194
00:09:49,310 --> 00:09:52,130
Susubukan naming uri ng lamang kalimutan
na 33 umiiral sa array,

195
00:09:52,130 --> 00:09:55,100
at kami na sabihin na ngayon, ang mga
bagong pinakaluma element sa pila

196
00:09:55,100 --> 00:09:58,900
ay array lokasyon 2, at ang laki
ng pila, ang bilang ng mga elemento

197
00:09:58,900 --> 00:10:02,152
kami ay may sa pila, ay 1.

198
00:10:02,152 --> 00:10:05,110
Ngayon enqueue ang isang bagay hayaan, at ako
uri ng ibinigay na ito ang layo sa isang segundo ang nakalipas,

199
00:10:05,110 --> 00:10:10,340
ngunit kung nais namin na ilagay ang 40 sa
queue, kung saan ay 40 pagpunta sa pumunta?

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

201
00:10:12,880 --> 00:10:17,730
Well kami ay paglagay ito
sa q.front plus queue laki,

202
00:10:17,730 --> 00:10:20,850
at kung kaya't makatuwiran na
aktwal na ilagay ang 40 dito.

203
00:10:20,850 --> 00:10:22,840
Ngayon pansinin na sa
ilang mga punto, kami ay pagpunta

204
00:10:22,840 --> 00:10:27,980
upang makakuha ng hanggang sa dulo ng
aming array sa loob ng q,

205
00:10:27,980 --> 00:10:32,010
ngunit na kupas out 28 at 33--
ang mga ito ay tunay na, technically

206
00:10:32,010 --> 00:10:33,300
buksan ang mga puwang, di ba?

207
00:10:33,300 --> 00:10:36,040
At ito, maaari naming eventually--
na patakaran ng pagdaragdag

208
00:10:36,040 --> 00:10:40,390
mga dalawang together-- maaari naming kalaunan
kailangang mod pamamagitan ng sukat ng kapasidad

209
00:10:40,390 --> 00:10:41,410
upang maaari naming wrapper sa paligid.

210
00:10:41,410 --> 00:10:43,620
>> Kaya kung makuha namin sa element
number 10, kung hindi namin

211
00:10:43,620 --> 00:10:48,790
palitan ito sa elemento bilang 10, gusto namin
tunay na ilagay ito sa array lokasyon 0.

212
00:10:48,790 --> 00:10:50,997
At kung kami ay pagpunta sa
array location-- patawarin ninyo ako,

213
00:10:50,997 --> 00:10:53,080
kung idinagdag namin ang mga ito up magkasama,
at nakuha namin sa numero ng

214
00:10:53,080 --> 00:10:56,330
11 ay kung saan kami ay may sa ilagay
ito, na kung saan ay hindi na umiiral sa ganitong array--

215
00:10:56,330 --> 00:10:58,200
ay ito ay pagpunta sa labas ng hangganan.

216
00:10:58,200 --> 00:11:03,367
Kami ay maaaring mod sa pamamagitan ng 10 at ilagay
ito sa lokasyon ng array 1.

217
00:11:03,367 --> 00:11:04,450
Kaya na kung paano gumagana queue.

218
00:11:04,450 --> 00:11:08,540
Sila ay palaging pagpunta upang pumunta mula sa kaliwa
papunta sa kanan at posibleng wrapper sa paligid.

219
00:11:08,540 --> 00:11:11,280
At alam mo na ang mga ito
ganap na kung ang laki, na red box,

220
00:11:11,280 --> 00:11:13,710
nagiging katumbas ng kapasidad.

221
00:11:13,710 --> 00:11:16,720
At kaya pagkatapos nagdagdag kami ng 40 sa
queue, na rin kung ano ang kailangan namin upang gawin?

222
00:11:16,720 --> 00:11:19,890
Well, ang pinakalumang element
sa pila ay 19 pa rin,

223
00:11:19,890 --> 00:11:21,990
kaya hindi namin nais na baguhin
sa harap ng pila,

224
00:11:21,990 --> 00:11:23,820
ngunit ngayon ay mayroon kaming dalawang
elemento sa pila,

225
00:11:23,820 --> 00:11:28,710
at kaya gusto naming dagdagan
aming sukat mula sa 1 sa 2.

226
00:11:28,710 --> 00:11:31,820
>> Iyan ay medyo magkano ito sa
nagtatrabaho sa array-based queues,

227
00:11:31,820 --> 00:11:33,630
at katulad ng stack,
diyan ay din ng isang paraan

228
00:11:33,630 --> 00:11:36,450
upang ipatupad ang isang queue ng isang naka-link na listahan.

229
00:11:36,450 --> 00:11:40,150
Ngayon kung ang ganitong uri ng istraktura ng data
Mukhang pamilyar sa iyo, ito ay.

230
00:11:40,150 --> 00:11:43,780
Ito ay hindi isang isa-isa naka-link na listahan,
ito ay isang doble-link na listahan.

231
00:11:43,780 --> 00:11:46,790
At ngayon, bilang isang bukod, ito ay
tunay na posible upang ipatupad

232
00:11:46,790 --> 00:11:50,160
isang pila bilang isang isa-isa naka-link na listahan, ngunit
Sa tingin ko sa mga tuntunin ng visualization,

233
00:11:50,160 --> 00:11:53,350
ito ang tunay na maaaring makatulong upang tingnan
ito bilang isang doble-link na listahan.

234
00:11:53,350 --> 00:11:56,850
Ngunit ito ay tiyak na posible na
gawin ito bilang isang isa-isa naka-link na listahan.

235
00:11:56,850 --> 00:12:00,110
>> Kaya sabihin magkaroon ng isang pagtingin sa
kung ano ang maaaring magmukhang.

236
00:12:00,110 --> 00:12:02,750
Kung gusto naming enquue--
kaya ngayon, muli kami ay

237
00:12:02,750 --> 00:12:05,360
lumipat sa isang naka-link-list
based modelo dito.

238
00:12:05,360 --> 00:12:08,420
Kung gusto naming enqueue, gusto naming
upang magdagdag ng isang bagong sangkap, well

239
00:12:08,420 --> 00:12:09,730
kung ano ang kailangan namin upang gawin?

240
00:12:09,730 --> 00:12:12,770
Well, una sa lahat, dahil
kami ay nagdadagdag ng hanggang sa dulo

241
00:12:12,770 --> 00:12:15,520
at pag-aalis mula sa
simula, kami ay marahil

242
00:12:15,520 --> 00:12:20,050
gusto mong mapanatili ang mga payo sa kapwa ang
ulo at ang buntot ng listahan ng mga link?

243
00:12:20,050 --> 00:12:22,660
Buntot pagiging isa pang term para
sa dulo ng listahan ng mga link,

244
00:12:22,660 --> 00:12:24,496
ang huling elemento sa mga naka-link na listahan.

245
00:12:24,496 --> 00:12:26,620
At ang mga ito ay marahil,
muli, maging kapaki-pakinabang sa amin

246
00:12:26,620 --> 00:12:28,477
kung ang mga ito ay mga pangkalahatang variable.

247
00:12:28,477 --> 00:12:31,060
Ngunit ngayon kung gusto naming idagdag ang isang bagong
element ano ang kailangan nating gawin?

248
00:12:31,060 --> 00:12:35,262
Kung ano ang aming lamang [? malak?] o dynamic
magtalaga ng aming bagong node para sa ating sarili.

249
00:12:35,262 --> 00:12:38,220
At pagkatapos, tulad lamang kapag nagdagdag kami ng anumang
sangkap sa isang doble-link list namin,

250
00:12:38,220 --> 00:12:40,410
mayroon lamang upang ayusin of--
mga huling tatlong hakbang dito

251
00:12:40,410 --> 00:12:43,330
ay lahat lamang tungkol sa paglipat sa
mga payo sa tamang paraan

252
00:12:43,330 --> 00:12:46,710
upang ang mga elemento naidadagdag
ang mga kadena na walang paglabag sa kadena

253
00:12:46,710 --> 00:12:49,580
o paggawa ng ilang uri ng mga pagkakamali
o pagkakaroon ng ilang uri ng mga aksidente

254
00:12:49,580 --> 00:12:54,505
mangyari kung saan namin sinasadyang
ulila ang ilang mga elemento ng aming queue.

255
00:12:54,505 --> 00:12:55,880
Narito kung ano ang maaaring magmukhang.

256
00:12:55,880 --> 00:13:00,980
Gusto naming idagdag ang elemento
10 hanggang sa dulo ng ito queue.

257
00:13:00,980 --> 00:13:03,380
Kaya ang pinakaluma elemento dito
ay kinakatawan ng ulo.

258
00:13:03,380 --> 00:13:06,800
Iyan ay ang unang bagay na inilalagay namin
sa hypothetical queue ito dito.

259
00:13:06,800 --> 00:13:10,430
At tail, 13, ay ang pinaka
kamakailang idinagdag na sangkap.

260
00:13:10,430 --> 00:13:17,030
At kaya kung gusto naming enqueue 10 sa
ito queue, gusto naming ilagay ito pagkatapos ng 13.

261
00:13:17,030 --> 00:13:19,860
At kaya kami ay pagpunta sa dynamically
maglaan ng espasyo para sa isang bagong node

262
00:13:19,860 --> 00:13:23,280
at suriin para sa null upang tiyakin
hindi namin ay may isang pagkabigo memory.

263
00:13:23,280 --> 00:13:27,040
Pagkatapos kami ay pagpunta sa
ilagay 10 sa na node,

264
00:13:27,040 --> 00:13:30,030
at ngayon ay kailangan naming maging maingat
tungkol sa kung paano namin ayusin ang mga payo

265
00:13:30,030 --> 00:13:32,180
kaya hindi namin basagin ang kadena.

266
00:13:32,180 --> 00:13:38,910
>> Maaari naming i-set ng 10 ni nakaraang field
upang ituro bumalik sa lumang buntot,

267
00:13:38,910 --> 00:13:41,620
at dahil '10 ang magiging
bagong buntot sa ilang mga punto

268
00:13:41,620 --> 00:13:44,459
sa pamamagitan ng oras sa lahat ng mga
ay konektado chains,

269
00:13:44,459 --> 00:13:46,250
walang pupuntahan dumating
pagkatapos ng 10 ngayon.

270
00:13:46,250 --> 00:13:49,880
At kaya 10 ng susunod pointer
ay tumuturo sa null,

271
00:13:49,880 --> 00:13:53,580
at pagkatapos ay matapos namin gawin ito, pagkatapos namin nai
kay 10 paurong sa chain,

272
00:13:53,580 --> 00:13:57,780
maaari naming gawin ang mga lumang ulo, o, excuse
sa akin, ang lumang buntot ng queue.

273
00:13:57,780 --> 00:14:02,980
Ang lumang dulo ng pila,
13, at gawin itong point sa 10.

274
00:14:02,980 --> 00:14:08,220
At ngayon, sa puntong ito, kami ay
enqueued ang bilang 10 sa mga ito queue.

275
00:14:08,220 --> 00:14:14,740
Lahat ng kailangan naming gawin ngayon ay lamang ilipat ang
tail upang tumuro sa 10 sa halip ng hanggang 13.

276
00:14:14,740 --> 00:14:17,630
>> Dequeuing ay talagang
halos kapareho sa pop

277
00:14:17,630 --> 00:14:21,710
mula sa isang stack na
ipinatupad bilang isang listahan ng mga link

278
00:14:21,710 --> 00:14:24,040
kung nakita mo na ang mga stack video.

279
00:14:24,040 --> 00:14:27,280
Ang kailangan nating gawin ay magsimula sa
simula, hanapin ang pangalawang elemento,

280
00:14:27,280 --> 00:14:30,480
libre ang unang elemento,
at pagkatapos ay ilipat ang ulo

281
00:14:30,480 --> 00:14:32,930
upang ituro sa pangalawang elemento.

282
00:14:32,930 --> 00:14:37,920
Marahil mas mahusay na ilarawan sa isip ang mga ito
upang maging labis na malinaw tungkol sa mga ito lamang.

283
00:14:37,920 --> 00:14:39,230
Kaya narito muli ang aming queue.

284
00:14:39,230 --> 00:14:42,600
12 ay ang pinakaluma element
sa aming pila, sa ulo.

285
00:14:42,600 --> 00:14:46,210
10 ay ang pinakabago element
sa aming pila, ang aming buntot.

286
00:14:46,210 --> 00:14:49,310
>> At kaya kapag gusto namin
sa dequeue isang sangkap,

287
00:14:49,310 --> 00:14:52,202
gusto naming alisin ang pinakaluma element.

288
00:14:52,202 --> 00:14:52,910
Kaya kung ano ang gagawin namin?

289
00:14:52,910 --> 00:14:55,243
Well kaming magtakda ng isang traversal pointer
na nagsisimula sa ulo,

290
00:14:55,243 --> 00:14:57,840
at ilipat namin ito upang ito ay
puntos sa ang pangalawang elemento

291
00:14:57,840 --> 00:15:02,290
ng mga ito queue-- isang bagay sa pamamagitan ng pagsasabi trav
katumbas trav arrow kasunod, halimbawa,

292
00:15:02,290 --> 00:15:07,170
nais ilipat trav doon upang tumuro sa
15, na kung saan, pagkatapos naming dequeue 12,

293
00:15:07,170 --> 00:15:13,030
o pagkatapos naming alisin 12, ay
maging ang pagkatapos-pinakalumang element.

294
00:15:13,030 --> 00:15:16,360
>> Ngayon namin nakuha ng isang hold sa mga unang
element sa pamamagitan ng pointer ulo

295
00:15:16,360 --> 00:15:19,440
at ang pangalawang elemento
sa pamamagitan ng pointer trav.

296
00:15:19,440 --> 00:15:25,170
Maaari naming libreng ngayon ulo, at pagkatapos ay maaari naming
sabihin walang dumating bago 15 anymore.

297
00:15:25,170 --> 00:15:29,990
Kaya maaari naming baguhin ang 15 ni nakaraan
pointer upang tumuro sa null,

298
00:15:29,990 --> 00:15:31,874
at ilipat lang namin sa head over.

299
00:15:31,874 --> 00:15:32,540
At doon kami pumunta.

300
00:15:32,540 --> 00:15:35,840
Ngayon ay matagumpay na namin
dequeued 12, at ngayon kami ay

301
00:15:35,840 --> 00:15:39,180
may isa pang pila ng 4 elemento.

302
00:15:39,180 --> 00:15:41,700
Iyan ay medyo marami ang lahat ng
doon ay upang queues,

303
00:15:41,700 --> 00:15:45,810
parehong array-based at naka-link-list based.

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

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

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