1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Lahat ng mga karapatan,
kaya sa pamamagitan ng puntong ito ikaw ay

3
00:00:05,990 --> 00:00:09,020
malamang na medyo pamilyar
sa array at mga listahan ng link

4
00:00:09,020 --> 00:00:10,950
kung saan ay ang dalawang pangunahing
istruktura ng data na namin

5
00:00:10,950 --> 00:00:16,810
usapan tungkol sa para sa pagsunod sa mga hanay ng mga
data ng mga katulad na uri ng data na inayos.

6
00:00:16,810 --> 00:00:19,080
>> Ngayon kami ay pagpunta sa makipag-usap
tungkol sa isang pares ng mga pagkakaiba-iba

7
00:00:19,080 --> 00:00:20,330
sa array at mga listahan ng link.

8
00:00:20,330 --> 00:00:22,362
Sa video na ito kami ay pagpunta
makipag-usap tungkol stack.

9
00:00:22,362 --> 00:00:25,320
Partikular kami ay pagpunta sa makipag-usap
tungkol sa isang istraktura ng data na tinatawag na isang stack.

10
00:00:25,320 --> 00:00:28,510
Pagpapabalik mula sa mga nakaraang talakayan
tungkol sa mga payo at memorya,

11
00:00:28,510 --> 00:00:32,060
na ang stack ay din ang
pangalan para sa isang segment ng memory

12
00:00:32,060 --> 00:00:34,980
kung saan statically ipinahayag
na memorya memory na kayo

13
00:00:34,980 --> 00:00:38,730
pangalan, mga variable na pangalan mo, et
iba pa at pag-andar ng mga frame na kung saan namin din

14
00:00:38,730 --> 00:00:41,000
umiiral call frames stack.

15
00:00:41,000 --> 00:00:45,421
Kaya ito ay isang istraktura stack data
hindi isang segment stack ng memory.

16
00:00:45,421 --> 00:00:45,920
SIGE.

17
00:00:45,920 --> 00:00:46,890
>> Ngunit ano ang isang stack?

18
00:00:46,890 --> 00:00:49,220
Kaya ito ay medyo mas lamang ng isang
espesyal na uri ng istraktura

19
00:00:49,220 --> 00:00:51,190
na nagpapanatili ng data sa isang organisadong paraan.

20
00:00:51,190 --> 00:00:53,760
At may dalawang tunay
karaniwang mga paraan upang ipatupad

21
00:00:53,760 --> 00:00:57,380
stack gamit ang dalawang mga istraktura ng data
na hindi namin na pamilyar sa,

22
00:00:57,380 --> 00:01:00,340
array at mga listahan ng link.

23
00:01:00,340 --> 00:01:04,430
Kung bakit ang isang stack espesyal ay ang
paraan na kung saan inilalagay namin ang impormasyon

24
00:01:04,430 --> 00:01:08,200
sa stack, at ang paraan ng aming
tanggalin ang impormasyon mula sa stack.

25
00:01:08,200 --> 00:01:11,600
Sa partikular na may mga stack
ang mga tuntunin ay lamang ang pinaka

26
00:01:11,600 --> 00:01:15,830
kamakailan maaaring alisin karagdagang elemento.

27
00:01:15,830 --> 00:01:17,660
>> Kaya mag-isip tungkol sa mga ito tulad ng kung ito ay isang stack.

28
00:01:17,660 --> 00:01:21,170
Kami ay piling impormasyon
sa itaas ng kanyang sarili,

29
00:01:21,170 --> 00:01:24,271
at lamang ang mga bagay sa itaas
ng pile maaaring alisin.

30
00:01:24,271 --> 00:01:27,020
Hindi namin maaaring alisin ang mga bagay sa ilalim ng
dahil lahat ng iba pa gagawin

31
00:01:27,020 --> 00:01:28,020
tiklupin at mahulog.

32
00:01:28,020 --> 00:01:32,580
Kaya namin talagang ay pagbuo ng isang stack na
pagkatapos kami ay may sa alisin ang piraso ng piraso.

33
00:01:32,580 --> 00:01:36,590
Dahil dito ang aming karaniwang sumangguni
sa isang stack bilang isang istraktura LIFO,

34
00:01:36,590 --> 00:01:38,940
huling sa, first out.

35
00:01:38,940 --> 00:01:42,290
LIFO, tatagal, unang labas.

36
00:01:42,290 --> 00:01:45,635
>> Kaya dahil dito pagbabawal sa
kung paano maaaring idagdag ang impormasyon sa

37
00:01:45,635 --> 00:01:49,080
at inalis mula sa isang stack, may tunay na
lamang ng dalawang mga bagay na maaari naming gawin sa isang stack.

38
00:01:49,080 --> 00:01:52,010
Maaari naming itulak, kung saan ay ang
katawagan na ginagamit namin para sa pagdaragdag

39
00:01:52,010 --> 00:01:55,130
isang bagong sangkap sa itaas ng
stack, o kung ang stack ay hindi umiiral

40
00:01:55,130 --> 00:01:58,550
at kami ay ang paglikha ng ito mula sa simula,
paglikha ng stack sa unang lugar

41
00:01:58,550 --> 00:02:00,110
ay panunulak.

42
00:02:00,110 --> 00:02:04,990
At pagkatapos ay pop, na ang uri ng CS
kataga naming gamitin upang alisin ang mga pinaka-kamakailan

43
00:02:04,990 --> 00:02:08,330
dagdag na sangkap mula sa tuktok ng stack.

44
00:02:08,330 --> 00:02:11,130
>> Kaya kami ay pagpunta upang tumingin sa parehong
pagpapatupad, batay sa parehong array

45
00:02:11,130 --> 00:02:13,120
at naka-link na listahan batay.

46
00:02:13,120 --> 00:02:14,870
At kami ay pagpunta sa
magsimula sa array based.

47
00:02:14,870 --> 00:02:19,990
Kaya dito ay ang pangunahing ideya ng kung ano ang
ang istraktura stack data array batay

48
00:02:19,990 --> 00:02:21,140
ay ang hitsura.

49
00:02:21,140 --> 00:02:23,740
Kami ay may isang kahulugan ng nag-type dito.

50
00:02:23,740 --> 00:02:27,790
Sa loob ng na kami ay may dalawang mga kasapi
o mga patlang ng mga istraktura.

51
00:02:27,790 --> 00:02:29,880
Kami ay may isang array.

52
00:02:29,880 --> 00:02:32,400
At muli ako gamit ang
arbitrary halaga uri ng data.

53
00:02:32,400 --> 00:02:35,180
>> Kaya ito ay maaaring sa anumang mga uri ng data,
int char o ilang iba pang data

54
00:02:35,180 --> 00:02:37,080
type nilikha mo dati.

55
00:02:37,080 --> 00:02:39,861
Kaya kami ay may isang hanay ng mga kakayahan laki.

56
00:02:39,861 --> 00:02:44,010
Kapasidad na tinukoy constant ng kalahating kilong,
marahil sa ibang lugar sa aming file.

57
00:02:44,010 --> 00:02:47,550
Kaya mapapansin na sa partikular na
pagpapatupad namin ay lukso

58
00:02:47,550 --> 00:02:49,800
ang ating mga sarili bilang ay karaniwang
ang kaso sa array,

59
00:02:49,800 --> 00:02:53,170
na kung saan hindi namin maaaring magilas na baguhin ang laki,
kung saan may isang tiyak na bilang

60
00:02:53,170 --> 00:02:55,450
ng maximum na mga elemento na
maaari naming ilagay sa aming stack.

61
00:02:55,450 --> 00:02:57,930
Sa kasong ito ito ay elemento ng kapasidad.

62
00:02:57,930 --> 00:03:00,310
>> Panatilihin din kami ng track ng
sa itaas ng stack.

63
00:03:00,310 --> 00:03:04,350
Ano ang sangkap ay ang pinaka
kamakailang idinagdag sa stack?

64
00:03:04,350 --> 00:03:07,470
At kaya sinusubaybayan namin na
sa variable na tinatawag na top a.

65
00:03:07,470 --> 00:03:11,692
At lahat ng ito ay makakakuha ng abala magkasama
sa isang bagong uri ng data na tinatawag na isang stack.

66
00:03:11,692 --> 00:03:13,400
At sa sandaling kami ay nilikha
ang bagong uri ng data

67
00:03:13,400 --> 00:03:15,410
maaari naming ituring ito tulad ng
anumang iba pang uri ng data.

68
00:03:15,410 --> 00:03:20,970
Maaari naming ipahayag stack s, tulad ng
maaari naming gawin int x, o char y.

69
00:03:20,970 --> 00:03:22,990
At kapag kami sabihin stack
s, well kung ano ang mangyayari

70
00:03:22,990 --> 00:03:26,420
ay makakakuha tayo ng isang set ng mga
magtabi memory para sa amin.

71
00:03:26,420 --> 00:03:28,770
>> Sa kapasidad na kaso
Tila ako ay nagpasya

72
00:03:28,770 --> 00:03:33,470
ay 10 dahil Mayroon akong isang
single variable ng uri ng stack

73
00:03:33,470 --> 00:03:35,320
na naglalaman ng dalawang mga patlang na pagpapabalik.

74
00:03:35,320 --> 00:03:38,330
Ang dami, sa kasong ito ay pagpunta
upang maging isang array ng mga integer

75
00:03:38,330 --> 00:03:40,440
tulad ng kaso sa karamihan ng aking mga halimbawa.

76
00:03:40,440 --> 00:03:43,996
At isa pang integer variable
kaya ng pagtatago sa itaas,

77
00:03:43,996 --> 00:03:45,870
ang pinaka-kamakailang idinagdag
sangkap sa mga stack.

78
00:03:45,870 --> 00:03:50,290
Kaya isa single stack ng kung ano ang aming
tinukoy lamang ganito ang hitsura nito.

79
00:03:50,290 --> 00:03:53,190
Ito ay isang kahon na naglalaman ng
isang hanay ng mga 10 ano

80
00:03:53,190 --> 00:03:57,280
ay integer sa kasong ito at
isa pang integer variable doon sa green

81
00:03:57,280 --> 00:04:00,010
upang ipahiwatig ang tuktok ng stack.

82
00:04:00,010 --> 00:04:02,600
>> Upang i-set sa itaas ng
stack naming sabihin lamang s.top.

83
00:04:02,600 --> 00:04:04,890
Iyon ay kung paano namin ma-access ang isang
larangan ng isang istraktura pagpapabalik.

84
00:04:04,890 --> 00:04:10,460
s.top katumbas ng 0 epektibong
Ginagawa ito sa aming stack.

85
00:04:10,460 --> 00:04:12,960
Kaya muli kami ay may dalawang mga operasyon
maaari naming gawin ngayon.

86
00:04:12,960 --> 00:04:14,270
Maaari naming itulak at maaari naming pop.

87
00:04:14,270 --> 00:04:15,635
Magsimula tayo sa push Hayaan.

88
00:04:15,635 --> 00:04:18,260
Muli, panunulak ay nagdadagdag ng isang bagong
sangkap sa itaas ng stack.

89
00:04:18,260 --> 00:04:21,460
>> Kaya kung ano ang dapat nating gawin sa
array na ito pagpapatupad batay?

90
00:04:21,460 --> 00:04:23,210
Well sa pangkalahatan ang
push function ay pagpunta

91
00:04:23,210 --> 00:04:26,160
sa kailangan upang tanggapin ang isang
pointer sa stack.

92
00:04:26,160 --> 00:04:28,610
Ngayon kumuha ng isang pangalawang at sa tingin tungkol dito.

93
00:04:28,610 --> 00:04:32,840
Bakit gusto naming tanggapin
isang pointer sa stack?

94
00:04:32,840 --> 00:04:36,830
Pagpapabalik mula sa mga nakaraang mga video sa
variable na saklaw at mga payo,

95
00:04:36,830 --> 00:04:42,350
ano ang mangyayari kung ipinadala namin lamang
stack, s halip sa bilang parameter?

96
00:04:42,350 --> 00:04:45,770
Ano ang gusto talaga maipasa sa doon?

97
00:04:45,770 --> 00:04:49,430
Tandaan namin ang paglikha ng isang kopya
kapag pumasa namin ito sa isang function

98
00:04:49,430 --> 00:04:51,160
maliban kung ginagamit namin mga payo.

99
00:04:51,160 --> 00:04:55,380
At kaya itulak ang function na pangangailangan
upang tanggapin ang isang pointer sa stack

100
00:04:55,380 --> 00:04:59,160
kaya na namin ang aktwal na binabago
stack balak namin na baguhin.

101
00:04:59,160 --> 00:05:03,060
>> Marahil nais Ang iba pang bagay push to
tanggapin ang isang elemento ng data ng halaga type.

102
00:05:03,060 --> 00:05:06,970
Sa kasong ito, muli, na isang integer na
kami ay pagpunta upang idagdag sa tuktok ng stack.

103
00:05:06,970 --> 00:05:08,680
Kaya Mayroon namin ang aming dalawang mga parameter.

104
00:05:08,680 --> 00:05:11,310
Ano ang mga namin pagpunta sa
ngayon ang gagawin sa loob ng push?

105
00:05:11,310 --> 00:05:14,860
Well, kailangan lang, lamang kami ay pagpunta upang magdagdag ng
sangkap na sa tuktok ng stack

106
00:05:14,860 --> 00:05:22,860
at pagkatapos ay baguhin kung saan ang tuktok ng
ang stack ay, na s dot top halaga.

107
00:05:22,860 --> 00:05:25,639
Kaya ito ay kung ano ang isang function
deklarasyon para sa push

108
00:05:25,639 --> 00:05:27,680
maaaring magmukhang sa isang
array-based na pagpapatupad.

109
00:05:27,680 --> 00:05:30,967
>> Muli ito ay hindi isang mabigat na kautusan
na maaari mong baguhin ito at magkaroon ng

110
00:05:30,967 --> 00:05:32,050
mag-iba ang mga ito sa iba't ibang paraan.

111
00:05:32,050 --> 00:05:33,840
Marahil s ay ipinahayag globally.

112
00:05:33,840 --> 00:05:36,180
At kaya hindi mo kahit na kailangan
upang pumasa ito ay bilang isang parameter.

113
00:05:36,180 --> 00:05:39,125
Ito ay muli lamang ng isang
pangkalahatang mga kaso para sa push.

114
00:05:39,125 --> 00:05:41,000
At may mga iba't-ibang
mga paraan upang ipatupad ito.

115
00:05:41,000 --> 00:05:42,810
Ngunit sa kasong ito ang aming
push ay pagpunta sa tumagal

116
00:05:42,810 --> 00:05:48,540
dalawang argumento, isang pointer sa isang stack at
isang elemento ng data ng halaga type, integer

117
00:05:48,540 --> 00:05:49,840
sa kasong ito.

118
00:05:49,840 --> 00:05:52,100
>> Kaya ipinahayag namin s, kami ay
Sinabi s.top katumbas ng 0.

119
00:05:52,100 --> 00:05:55,969
Ngayon natin itulak ang ipaalam
number 28 papunta sa stack.

120
00:05:55,969 --> 00:05:57,010
Well kung ano ang ibig sabihin nito?

121
00:05:57,010 --> 00:05:59,600
Well kasalukuyang ang
tuktok ng stack ay 0.

122
00:05:59,600 --> 00:06:01,350
At kaya kung ano talaga ang
pagpunta sa mangyari ay

123
00:06:01,350 --> 00:06:05,820
kami ay pagpunta sa stick sa bilang
28 sa array lokasyon 0.

124
00:06:05,820 --> 00:06:09,540
Medyo prangka, kanan, na
ay ang top at ngayon kami ay handa na upang patakbuhin.

125
00:06:09,540 --> 00:06:12,910
At pagkatapos ay kailangan namin upang baguhin kung ano ang
sa itaas ng stack ay.

126
00:06:12,910 --> 00:06:15,130
Kaya na ang mga susunod na panahon
itulak namin ang isang elemento sa,

127
00:06:15,130 --> 00:06:18,017
kami ay pagpunta sa store na ito sa
lokasyon array, marahil ay hindi 0.

128
00:06:18,017 --> 00:06:20,100
Hindi namin nais na patungan
kung ano ang namin lamang ilagay doon.

129
00:06:20,100 --> 00:06:23,510
At kaya kailangan lang ilipat namin sa itaas hanggang 1.

130
00:06:23,510 --> 00:06:24,890
Iyon marahil ang akma.

131
00:06:24,890 --> 00:06:28,940
>> Ngayon kung gusto naming ilagay ang isa pang elemento
papunta sa stack, sabihin nating nais naming itulak 33,

132
00:06:28,940 --> 00:06:33,190
well ngayon lang kami na kumuha ng 33
at ilagay ito sa numero ng lokasyon array

133
00:06:33,190 --> 00:06:37,580
1, at pagkatapos ay baguhin ang tuktok ng aming
stack na array lokasyon bilang dalawang.

134
00:06:37,580 --> 00:06:40,650
Kaya kung ang mga susunod na panahon na gusto naming
itulak ang isang elemento papunta sa stack,

135
00:06:40,650 --> 00:06:43,087
makikita ito ay ilagay sa array lokasyon 2.

136
00:06:43,087 --> 00:06:44,420
At gawin na isa pang beses ipaalam.

137
00:06:44,420 --> 00:06:45,753
Susubukan naming itulak 19 off ng stack.

138
00:06:45,753 --> 00:06:48,940
Susubukan naming ilagay 19 sa array lokasyon 2
at baguhin ang tuktok ng aming stack

139
00:06:48,940 --> 00:06:51,220
na array lokasyon 3
kaya kung ang mga susunod na oras namin

140
00:06:51,220 --> 00:06:54,780
kailangan upang gumawa ng push hindi namin handa na upang patakbuhin.

141
00:06:54,780 --> 00:06:56,980
>> OK, kaya na pagtulak sa maikling sabi.

142
00:06:56,980 --> 00:06:57,830
Ano ang tungkol sa pop?

143
00:06:57,830 --> 00:07:00,240
Kaya pop ay ang uri ng
kamukhang-mukha sa panunulak.

144
00:07:00,240 --> 00:07:02,720
Ito ay kung paano namin tanggalin ang data mula sa stack.

145
00:07:02,720 --> 00:07:04,610
At sa pangkalahatan pangangailangan pop
upang gawin ang mga sumusunod.

146
00:07:04,610 --> 00:07:07,600
Kailangan nito upang tanggapin ang isang pointer sa
stack, muli sa pangkalahatang kaso.

147
00:07:07,600 --> 00:07:10,480
Sa ilang iba pang mga kaso maaari ka
Aking ipinahayag ang mga stack globally,

148
00:07:10,480 --> 00:07:13,910
sa kaso na hindi mo na kailangan upang pumasa ito
sa dahil ito ay mayroon ng access sa mga ito

149
00:07:13,910 --> 00:07:15,541
bilang isang global variable.

150
00:07:15,541 --> 00:07:17,040
Ngunit pagkatapos ay kung ano pa ang dapat nating gawin?

151
00:07:17,040 --> 00:07:21,000
Well kami ay incrementing
sa itaas ng stack sa push,

152
00:07:21,000 --> 00:07:24,050
kaya marahil kami ay pagpunta sa gusto
sa pagbawas sa itaas ng stack

153
00:07:24,050 --> 00:07:25,009
sa pop, i-right?

154
00:07:25,009 --> 00:07:26,800
At pagkatapos ng kurso
din namin ay pagpunta sa nais

155
00:07:26,800 --> 00:07:29,240
upang ibalik ang halaga na alisin namin.

156
00:07:29,240 --> 00:07:32,125
Kung kami ay nagdadagdag ng mga elemento, gusto naming
upang makakuha ng mga elemento out sa susunod,

157
00:07:32,125 --> 00:07:34,000
kami ay marahil talagang
nais na iimbak ang mga ito kaya namin

158
00:07:34,000 --> 00:07:36,490
huwag tanggalin na lamang ang mga ito mula sa
stack at pagkatapos ay wala sa kanila.

159
00:07:36,490 --> 00:07:38,500
Sa pangkalahatan, kung hindi kami
pagtulak at pop dito

160
00:07:38,500 --> 00:07:41,250
gusto naming upang i-imbak ang
impormasyon sa isang makahulugang paraan

161
00:07:41,250 --> 00:07:43,250
at upang hindi ito gumawa ng
kahulugan upang itapon lamang ito.

162
00:07:43,250 --> 00:07:46,380
Kaya ang function na ito ay dapat na
marahil nagbabalik ng halaga sa amin.

163
00:07:46,380 --> 00:07:51,040
>> Kaya ito ay kung ano ang isang deklarasyon para sa pop
maaaring magmukhang doon sa itaas na kaliwang.

164
00:07:51,040 --> 00:07:53,870
Function na babalik na ito
data ng halaga type.

165
00:07:53,870 --> 00:07:56,320
Muli nakaya naming gamit
integer sa buong lugar.

166
00:07:56,320 --> 00:08:01,916
At ito ay tumatanggap ng isang pointer sa isang stack bilang
sarili nitong argument o nag-iisang parameter.

167
00:08:01,916 --> 00:08:03,040
Kaya kung ano ang pop pagpunta sa gawin?

168
00:08:03,040 --> 00:08:07,990
Ipagpalagay natin na nais nating ngayon
pop isang elemento off ng s.

169
00:08:07,990 --> 00:08:14,000
Kaya tandaan sinabi ko na stack ay huling
in, first out, LIFO istruktura ng data.

170
00:08:14,000 --> 00:08:17,855
Aling elemento ay pagpunta sa
ay aalisin mula sa stack?

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
Hulaan mo ba 19?

173
00:08:24,150 --> 00:08:25,290
Dahil gusto mo ay tama.

174
00:08:25,290 --> 00:08:28,836
19 ay ang huling elemento idinagdag namin sa
stack kapag kami pagtulak ay elemento sa,

175
00:08:28,836 --> 00:08:31,210
at kaya ito ay pagpunta sa unang
elemento na makakakuha ng tinanggal.

176
00:08:31,210 --> 00:08:34,780
Ito ay bilang kung sinabi namin 28, at
pagkatapos ay inilalagay namin 33 sa tuktok ng ito,

177
00:08:34,780 --> 00:08:36,659
at ilalagay namin ang 19 sa tuktok ng na.

178
00:08:36,659 --> 00:08:40,650
Ang tanging sangkap na maaari naming mag-alis ay 19.

179
00:08:40,650 --> 00:08:45,019
>> Ngayon sa diagram dito kung ano ang nagawa ko
ay isang uri ng mga tinanggal na 19 mula sa array.

180
00:08:45,019 --> 00:08:46,810
Iyan ay hindi tunay na
kung ano ang namin ang pagpunta sa gawin.

181
00:08:46,810 --> 00:08:48,934
Kami ay pagpunta sa uri
ng magpanggap na ito ay hindi doon.

182
00:08:48,934 --> 00:08:51,441
Ito ay pa rin doon sa
na lokasyon sa memorya,

183
00:08:51,441 --> 00:08:54,190
ngunit lamang namin ang pagpunta upang huwag pansinin ito
sa pamamagitan ng pagbabago sa tuktok ng aming stack

184
00:08:54,190 --> 00:08:56,080
mula sa pagiging 3 sa 2.

185
00:08:56,080 --> 00:08:58,720
Kaya kung kami ay sa ngayon itulak
isa pang elemento papunta sa stack,

186
00:08:58,720 --> 00:09:00,720
ito ay higit sa 19 magsulat.

187
00:09:00,720 --> 00:09:03,990
>> Ngunit hindi na pumunta sa pamamagitan ng problema ipaalam
ng pagtanggal ng 19 mula sa stack.

188
00:09:03,990 --> 00:09:05,830
Maaari lang namin magpanggap na ito ay hindi doon.

189
00:09:05,830 --> 00:09:11,107
Para sa mga layunin ng stack na ito ay wala na kung
palitan namin tuktok na 2 sa halip ng 3.

190
00:09:11,107 --> 00:09:12,690
Lahat ng karapatan, kaya na ay medyo magkano ito.

191
00:09:12,690 --> 00:09:15,080
Iyon lang ang kailangan nating gawin
mag-pop-off ang isang elemento.

192
00:09:15,080 --> 00:09:16,090
Gawin natin ito muli.

193
00:09:16,090 --> 00:09:18,610
Kaya nai-highlight ko ito sa red para
ipahiwatig ginagawa namin ng isa pang tawag.

194
00:09:18,610 --> 00:09:19,720
Kami ay pagpunta sa gawin ang parehong bagay.

195
00:09:19,720 --> 00:09:20,803
>> Kaya kung ano ang nangyayari sa mangyayari?

196
00:09:20,803 --> 00:09:23,670
Well, kami ay pagpunta upang mag-imbak
33 in x at kami ay pagpunta

197
00:09:23,670 --> 00:09:26,217
upang baguhin ang tuktok ng stack sa 1.

198
00:09:26,217 --> 00:09:29,050
Kaya na kung kami ay upang itulak ang isang ngayon
element sa stack na hindi namin

199
00:09:29,050 --> 00:09:31,610
pagpunta sa gawin sa ngayon,
kung ano ang nangyayari sa mangyayari

200
00:09:31,610 --> 00:09:36,367
ay namin ang pagpunta overwrite
array lokasyon number 1.

201
00:09:36,367 --> 00:09:38,950
Kaya na 33 na uri ng kaliwa
sa likod na nagpanggap lang namin

202
00:09:38,950 --> 00:09:44,390
ay hindi doon ngayon, lang kami
sa gumulpi ito at ilagay sa 40 doon sa halip.

203
00:09:44,390 --> 00:09:46,290
At pagkatapos ng kurso,
dahil gumawa kami ng isang push,

204
00:09:46,290 --> 00:09:48,780
kami ay pagpunta sa pagdami ang mga
tuktok ng stack mula 1 hanggang 2

205
00:09:48,780 --> 00:09:50,950
upang kung namin magdagdag ngayon
isa pang elemento idedetalye ito

206
00:09:50,950 --> 00:09:54,700
pumunta sa array lokasyon bilang dalawang.

207
00:09:54,700 --> 00:09:57,590
>> Ngayon na naka-link na listahan ay isa pang
paraan upang ipatupad ang mga stack.

208
00:09:57,590 --> 00:10:01,210
At kung ito kahulugan sa
dito mukhang pamilyar sa iyo screen,

209
00:10:01,210 --> 00:10:04,260
ito ay dahil ito ay mukhang halos
eksaktong pareho, sa katunayan,

210
00:10:04,260 --> 00:10:07,790
ito ay medyo marami ay eksaktong
parehong bilang isang isa-isa naka-link na listahan,

211
00:10:07,790 --> 00:10:11,990
kung isipin mo mula sa aming mga talakayan ng
isa-isa mga listahan ng link sa isa pang video.

212
00:10:11,990 --> 00:10:15,510
Ang tanging mga paghihigpit dito
ay para sa amin bilang mga programmer,

213
00:10:15,510 --> 00:10:17,900
hindi namin pinahihintulutan na
ipasok o tanggalin sapalaran

214
00:10:17,900 --> 00:10:20,620
mula sa isa-isa listahan ng mga link
kung saan maaari naming dati gawin.

215
00:10:20,620 --> 00:10:25,820
Maaari lamang kami ngayong ipasok at tanggalin ang mula sa
sa harap o sa itaas ng mga naka-link

216
00:10:25,820 --> 00:10:26,320
listahan.

217
00:10:26,320 --> 00:10:28,028
Iyan ay talagang lamang
pagkakaiba bagaman.

218
00:10:28,028 --> 00:10:29,700
Ito ay sa kabilang banda isang isa-isa naka-link na listahan.

219
00:10:29,700 --> 00:10:32,060
Ito ay lamang ang paghihigpit
pagpapalit sa ating sarili

220
00:10:32,060 --> 00:10:35,770
bilang programmer na
pagbabago ito sa isang stack.

221
00:10:35,770 --> 00:10:39,280
>> Ang rule dito ay ang palaging mapanatili ang isang
pointer sa ulo ng isang naka-link na listahan.

222
00:10:39,280 --> 00:10:41,520
Ito ay siyempre isang karaniwang
mahalagang tuntunin muna.

223
00:10:41,520 --> 00:10:44,260
Para isa-isa list na naka-link sa iyo pa rin
kailangan lamang ng isang pointer sa ulo

224
00:10:44,260 --> 00:10:46,160
upang magkaroon ng na
chain ma-refer

225
00:10:46,160 --> 00:10:48,596
sa bawat iba pang mga elemento
sa naka-link na listahan.

226
00:10:48,596 --> 00:10:50,470
Ngunit ito ay lalo
mahalaga sa isang stack.

227
00:10:50,470 --> 00:10:52,386
At kaya sa pangkalahatan ikaw
pagpunta sa aktwal na nais

228
00:10:52,386 --> 00:10:54,090
ang pointer upang maging isang global variable.

229
00:10:54,090 --> 00:10:56,574
Marahil ito ay pagpunta sa
magiging mas madali na paraan.

230
00:10:56,574 --> 00:10:58,240
Kaya ano ang mga analogs ng push at pop?

231
00:10:58,240 --> 00:10:58,740
Right.

232
00:10:58,740 --> 00:11:01,812
Kaya pagtulak muli ay pagdaragdag
isang bagong sangkap sa stack.

233
00:11:01,812 --> 00:11:03,770
Sa isang naka-link na listahan
ay nangangahulugan na kami ay pagpunta sa may

234
00:11:03,770 --> 00:11:07,770
upang lumikha ng isang bagong node na hindi namin
pagpunta upang idagdag sa listahan ng mga link,

235
00:11:07,770 --> 00:11:10,500
at pagkatapos ay sundin ang mga maingat na hakbang
na ibinalangkas namin dati

236
00:11:10,500 --> 00:11:16,050
sa isa-isa na naka-link na listahan upang idagdag ito sa
ang mga kadena na walang paglabag sa kadena

237
00:11:16,050 --> 00:11:18,900
at pagkawala o orphaning anumang
elemento ng naka-link na listahan.

238
00:11:18,900 --> 00:11:21,820
At na talaga kung ano na ang
maliit na patak ng text doon nagbubuod.

239
00:11:21,820 --> 00:11:23,740
At ang isang pagtingin hayaan
sa ito bilang isang diagram.

240
00:11:23,740 --> 00:11:24,823
>> Kaya narito ang aming listahan ng mga link.

241
00:11:24,823 --> 00:11:26,620
Ito Kasabay naglalaman ng apat na mga sangkap.

242
00:11:26,620 --> 00:11:30,420
At higit na ganap narito ang aming
stack na naglalaman ng apat na mga sangkap.

243
00:11:30,420 --> 00:11:36,030
At sabihin natin na nais natin ngayon upang
itulak ang isang bagong item na ito papunta sa stack.

244
00:11:36,030 --> 00:11:39,792
At gusto namin na itulak ang isang bagong
item na ang halaga ng data ay 12.

245
00:11:39,792 --> 00:11:41,000
Well kung ano ang gagawin natin?

246
00:11:41,000 --> 00:11:43,420
Well unang kami ay pagpunta sa
malloc espasyo, magilas

247
00:11:43,420 --> 00:11:45,411
maglaan ng espasyo para sa isang bagong node.

248
00:11:45,411 --> 00:11:48,160
At siyempre kaagad pagkatapos
gumawa kami ng isang tawag sa malloc kami ay palaging

249
00:11:48,160 --> 00:11:52,989
siguraduhin na suriin para sa null,
dahil kung nakuha namin ang null likod

250
00:11:52,989 --> 00:11:54,280
nagkaroon ng ilang mga uri ng problema.

251
00:11:54,280 --> 00:11:57,570
Hindi namin nais na dereference na null
pointer o ikaw ay magdusa ng isang seg fault.

252
00:11:57,570 --> 00:11:58,510
Iyan ay hindi mabuti.

253
00:11:58,510 --> 00:11:59,760
Kaya mo malloced kami ng node.

254
00:11:59,760 --> 00:12:01,260
Kami ipalagay na nagkaroon kami tagumpay dito.

255
00:12:01,260 --> 00:12:06,090
Kami ay pagpunta sa ilagay ang 12 sa
larangan data ng na node.

256
00:12:06,090 --> 00:12:11,570
Ngayon mo isipin kung alin sa aming mga payo
gumagalaw susunod kaya hindi namin basagin ang kadena?

257
00:12:11,570 --> 00:12:15,100
Kami ay may isang pares ng mga pagpipilian dito ngunit
ang isa lamang na ay magiging ligtas

258
00:12:15,100 --> 00:12:19,330
ay upang itakda ang mga balita susunod na pointer sa
point sa lumang ulo ng listahan

259
00:12:19,330 --> 00:12:21,360
o kung ano ay malapit ang
lumang ulo ng listahan.

260
00:12:21,360 --> 00:12:23,610
At ngayon na ang lahat ng aming
elemento ay chained magkasama,

261
00:12:23,610 --> 00:12:27,370
maaari naming ilipat lamang list upang ituro
sa parehong lugar na ang mga bagong ginagawa.

262
00:12:27,370 --> 00:12:33,550
At kami ay ngayong epektibong itinulak ng
bagong sangkap papunta sa harap ng stack.

263
00:12:33,550 --> 00:12:36,420
>> Upang pop namin lamang ang nais na
tanggalin na ang unang elemento.

264
00:12:36,420 --> 00:12:38,150
At kaya kung ano talaga
kami ay may sa gawin dito,

265
00:12:38,150 --> 00:12:40,050
well kami ay upang mahanap ang pangalawang elemento.

266
00:12:40,050 --> 00:12:43,540
Sa kalaunan na ang magiging bagong
tumuloy matapos naming tanggalin ang una.

267
00:12:43,540 --> 00:12:47,300
Kaya kailangan lang namin upang simulan mula sa
sa simula, ilipat ang isa forward.

268
00:12:47,300 --> 00:12:50,340
Kapag namin nakuha ng isang hold sa isa
forward ng kung saan kami ay kasalukuyang

269
00:12:50,340 --> 00:12:53,850
ay maaari naming tanggalin ang unang isa ligtas na
at pagkatapos ay maaari naming ilipat lamang ang ulo

270
00:12:53,850 --> 00:12:57,150
upang tumuro sa kung ano ang
ikalawang termino at pagkatapos ay ngayon

271
00:12:57,150 --> 00:12:59,170
ay ang unang matapos na
node ay tinanggal na.

272
00:12:59,170 --> 00:13:01,160
>> Kaya muli, pagkuha ng isang pagtingin
sa ito bilang isang diagram namin

273
00:13:01,160 --> 00:13:05,022
nais na ngayon pop isang
element off ng mga ito stack.

274
00:13:05,022 --> 00:13:05,730
Kaya kung ano ang gagawin namin?

275
00:13:05,730 --> 00:13:08,188
Well unang kami ay pagpunta upang lumikha ng
isang bagong pointer na pupuntahan

276
00:13:08,188 --> 00:13:10,940
upang ituro sa parehong lugar bilang pinuno.

277
00:13:10,940 --> 00:13:13,790
Kami ay pagpunta sa ilipat ito sa isang posisyon
forward sa pamamagitan ng pagsasabi trav equals

278
00:13:13,790 --> 00:13:17,510
trav susunod na halimbawa, kung saan
Gusto isulong ang isa trav pointer

279
00:13:17,510 --> 00:13:19,324
posisyon ng pasulong.

280
00:13:19,324 --> 00:13:21,240
Ngayon na mayroon ka namin ng isang
hawakan ang unang elemento

281
00:13:21,240 --> 00:13:24,573
sa pamamagitan ng pointer na tinatawag na listahan, at ang
pangalawang elemento sa pamamagitan ng isang pointer na tinatawag na

282
00:13:24,573 --> 00:13:28,692
trav, maaari naming ligtas na tanggalin ang
unang elemento mula sa stack

283
00:13:28,692 --> 00:13:30,650
nang hindi nawawala ang mga natitirang
ng chain dahil tayo

284
00:13:30,650 --> 00:13:32,358
magkaroon ng isang paraan upang sumangguni
sa pangalawang elemento

285
00:13:32,358 --> 00:13:34,780
ipasa sa pamamagitan ng paraan ng
tinatawag trav pointer.

286
00:13:34,780 --> 00:13:37,100
>> Kaya ngayon maaari naming magbakante na node.

287
00:13:37,100 --> 00:13:38,404
Maaari naming magbakante listahan.

288
00:13:38,404 --> 00:13:41,320
At pagkatapos ang lahat ng kailangan naming gawin ngayon ay
ilipat ang listahan upang point sa parehong lugar

289
00:13:41,320 --> 00:13:44,482
na trav ang ginagawa, at hindi namin uri ng likod
kung saan kami nagsimula bago namin itinulak 12

290
00:13:44,482 --> 00:13:45,690
on sa unang lugar, right.

291
00:13:45,690 --> 00:13:46,940
Ito ay eksakto kung saan namin.

292
00:13:46,940 --> 00:13:48,840
Kami ay nagkaroon ng ito stack ng apat na elemento.

293
00:13:48,840 --> 00:13:49,690
Nagdagdag kami ng isang ikalima.

294
00:13:49,690 --> 00:13:51,910
Itinulak namin ang ikalimang
element sa, at pagkatapos namin

295
00:13:51,910 --> 00:13:55,980
pop na pinaka-kamakailan
dagdag na sangkap back off.

296
00:13:55,980 --> 00:13:58,816
>> Iyan ay talagang medyo marami
lahat ng may sa stack.

297
00:13:58,816 --> 00:14:00,190
Maaari mong ipatupad ang mga ito bilang mga array.

298
00:14:00,190 --> 00:14:01,815
Maaari mong ipatupad ang mga ito bilang mga listahan ng link.

299
00:14:01,815 --> 00:14:04,810
May, siyempre, iba pang
mga paraan upang ipatupad ang mga ito pati na rin.

300
00:14:04,810 --> 00:14:09,060
Talaga ang dahilan gusto naming gamitin
stack ay upang mapanatili ang data sa paraan

301
00:14:09,060 --> 00:14:12,090
na ang pinaka-kamakailang idinagdag
sangkap ay ang unang bagay na hindi namin

302
00:14:12,090 --> 00:14:14,980
pagpunta sa nais na makabalik.

303
00:14:14,980 --> 00:14:17,900
Ako Doug Lloyd, ito ay cs50.

304
00:14:17,900 --> 00:14:19,926