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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Bine,
astfel de acest punct ești

3
00:00:05,990 --> 00:00:09,020
probabil destul de familiar
cu tablouri si liste legate

4
00:00:09,020 --> 00:00:10,950
care este de două primar
structuri de date care le-am

5
00:00:10,950 --> 00:00:16,810
a vorbit despre pentru păstrarea seturi de
date de tipuri de date similare organizate.

6
00:00:16,810 --> 00:00:19,080
>> Acum vom vorbi
despre un cuplu de variații

7
00:00:19,080 --> 00:00:20,330
pe tablouri si liste legate.

8
00:00:20,330 --> 00:00:22,362
În acest film vom
pentru a vorbi despre stive.

9
00:00:22,362 --> 00:00:25,320
Mai exact vom vorbi
despre o structură de date numită stivă.

10
00:00:25,320 --> 00:00:28,510
Reamintim de la discuțiile anterioare
despre indicii și memorie,

11
00:00:28,510 --> 00:00:32,060
că stiva este, de asemenea,
nume pentru un segment de memorie

12
00:00:32,060 --> 00:00:34,980
în cazul în care a declarat static
memorie memory-- pe care le

13
00:00:34,980 --> 00:00:38,730
nume, variabile pe care le nume, et
cetera și funcția de cadre pe care le, de asemenea,

14
00:00:38,730 --> 00:00:41,000
există cadre stiva de apel.

15
00:00:41,000 --> 00:00:45,421
Deci, aceasta este o structură de date stiva
nu un segment de memorie stivă.

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

17
00:00:45,920 --> 00:00:46,890
>> Dar ceea ce este o stivă?

18
00:00:46,890 --> 00:00:49,220
Deci e destul de mult doar un
tip special de structura

19
00:00:49,220 --> 00:00:51,190
care menține datele într-un mod organizat.

20
00:00:51,190 --> 00:00:53,760
Și nu există două foarte
metode comune de punere în aplicare

21
00:00:53,760 --> 00:00:57,380
stive folosind două structuri de date
că suntem deja familiarizați cu,

22
00:00:57,380 --> 00:01:00,340
tablouri si liste legate.

23
00:01:00,340 --> 00:01:04,430
Ce face o deosebită stivă este
mod în care am pus informații

24
00:01:04,430 --> 00:01:08,200
în stiva, și modul în care
elimina informațiile din stivă.

25
00:01:08,200 --> 00:01:11,600
În special cu stive
regula este doar cel mai

26
00:01:11,600 --> 00:01:15,830
recent element în plus pot fi eliminate.

27
00:01:15,830 --> 00:01:17,660
>> Deci, cred că despre ea ca daca este o stivă.

28
00:01:17,660 --> 00:01:21,170
Suntem piling informații
pe partea de sus de el însuși,

29
00:01:21,170 --> 00:01:24,271
și numai lucrul la partea de sus
a gramada pot fi eliminate.

30
00:01:24,271 --> 00:01:27,020
Nu putem elimina lucru sub
pentru că orice altceva ar fi

31
00:01:27,020 --> 00:01:28,020
colaps și cădea peste.

32
00:01:28,020 --> 00:01:32,580
Deci, suntem cu adevărat construim o stivă care
trebuie apoi să eliminați bucata cu bucata.

33
00:01:32,580 --> 00:01:36,590
Din acest motiv ne-am referi în mod obișnuit
la un stack ca o structură LIFO,

34
00:01:36,590 --> 00:01:38,940
ultimul intrat, primul ieșit.

35
00:01:38,940 --> 00:01:42,290
LIFO, ultimul intrat, primul ieșit.

36
00:01:42,290 --> 00:01:45,635
>> Deci, din cauza acestei restricții privind
modul în care informațiile pot fi adăugate la

37
00:01:45,635 --> 00:01:49,080
și scoase dintr-o stivă, nu există cu adevărat
doar două lucruri pe care le putem face cu un stack.

38
00:01:49,080 --> 00:01:52,010
Putem împinge, care este
termen care le folosim pentru adăugarea

39
00:01:52,010 --> 00:01:55,130
un nou element la capătul superior al acesteia
stivă, sau în cazul în care stiva nu există

40
00:01:55,130 --> 00:01:58,550
si suntem o crearea de la zero,
creând teancul în primul rând

41
00:01:58,550 --> 00:02:00,110
ar fi împingere.

42
00:02:00,110 --> 00:02:04,990
Și apoi pop, asta e un fel de CS
termen care le folosim pentru a elimina cele mai recent

43
00:02:04,990 --> 00:02:08,330
adăugat elementul din vârful stivei.

44
00:02:08,330 --> 00:02:11,130
>> Așa că am de gând să se uite la ambele
implementari, pe ambele matrice

45
00:02:11,130 --> 00:02:13,120
și lista de legat pe bază de.

46
00:02:13,120 --> 00:02:14,870
Și am de gând să
începe cu matrice pe bază de.

47
00:02:14,870 --> 00:02:19,990
Deci, aici e ideea de bază a ceea ce
structura de date set de rețele pe bază de

48
00:02:19,990 --> 00:02:21,140
ar arăta.

49
00:02:21,140 --> 00:02:23,740
Avem o definiție tastat aici.

50
00:02:23,740 --> 00:02:27,790
In interiorul că avem doi membri
sau câmpuri ale structurii.

51
00:02:27,790 --> 00:02:29,880
Avem o serie.

52
00:02:29,880 --> 00:02:32,400
Și din nou Sunt folosind
arbitrară valoare tip de date.

53
00:02:32,400 --> 00:02:35,180
>> Deci, acest lucru ar putea fi orice tip de date,
Int char sau un alt date

54
00:02:35,180 --> 00:02:37,080
tip ați creat anterior.

55
00:02:37,080 --> 00:02:39,861
Deci, avem o serie de capacitate dimensiune.

56
00:02:39,861 --> 00:02:44,010
Capacitate fiind o lira definit constant,
probabil în altă parte în dosarul nostru.

57
00:02:44,010 --> 00:02:47,550
Deci observați deja cu aceasta special
implementare suntem limitrofe

58
00:02:47,550 --> 00:02:49,800
noi înșine ca de obicei, a fost
în cazul tablouri,

59
00:02:49,800 --> 00:02:53,170
care nu putem redimensiona dinamic,
în cazul în care există un anumit număr

60
00:02:53,170 --> 00:02:55,450
elementelor maximă care
putem pune în stivă nostru.

61
00:02:55,450 --> 00:02:57,930
În acest caz, este elemente de capacitate.

62
00:02:57,930 --> 00:03:00,310
>> De asemenea, ține evidența
partea de sus a stivei.

63
00:03:00,310 --> 00:03:04,350
Care element este cel mai
recent adăugate la stiva?

64
00:03:04,350 --> 00:03:07,470
Și așa ne-am urmări care
într-o variabilă numită top.

65
00:03:07,470 --> 00:03:11,692
Și toate acestea se înfășurat împreună
într-un nou tip de date numit un stack.

66
00:03:11,692 --> 00:03:13,400
Și odată ce suntem creat
acest nou tip de date

67
00:03:13,400 --> 00:03:15,410
putem trata ca
orice alt tip de date.

68
00:03:15,410 --> 00:03:20,970
Putem declara stivă s, la fel ca
am putea face int x, sau y char.

69
00:03:20,970 --> 00:03:22,990
Și când spunem stivă
s, și ceea ce se întâmplă

70
00:03:22,990 --> 00:03:26,420
este ne un set de
memorie rezervat pentru noi.

71
00:03:26,420 --> 00:03:28,770
>> În acest caz, capacitatea de
M-am decis, aparent

72
00:03:28,770 --> 00:03:33,470
este de 10 pentru că am o
variabil unic de tip stivă

73
00:03:33,470 --> 00:03:35,320
care conține două câmpuri amintesc.

74
00:03:35,320 --> 00:03:38,330
O matrice, în acest caz se întâmplă
să fie o serie de numere întregi

75
00:03:38,330 --> 00:03:40,440
așa cum este cazul în majoritatea exemplele mele.

76
00:03:40,440 --> 00:03:43,996
Și o altă variabilă întreg
capabil să stocheze partea de sus,

77
00:03:43,996 --> 00:03:45,870
cel mai recent adăugat
element stiva.

78
00:03:45,870 --> 00:03:50,290
Deci, unul singur teanc de ceea ce am
doar arata ca acest lucru definit.

79
00:03:50,290 --> 00:03:53,190
Este o cutie care conține
o serie de 10 ceea ce

80
00:03:53,190 --> 00:03:57,280
va fi numere întregi în acest caz și
altă variabilă integer acolo în verde

81
00:03:57,280 --> 00:04:00,010
pentru a indica vârful stivei.

82
00:04:00,010 --> 00:04:02,600
>> Pentru a seta superior al acesteia
stivă spunem doar s.top.

83
00:04:02,600 --> 00:04:04,890
Așa am acces la o
câmp de rechemare structură.

84
00:04:04,890 --> 00:04:10,460
s.top este egal cu 0 în mod eficient
face acest lucru pentru a stiva noastră.

85
00:04:10,460 --> 00:04:12,960
Deci, din nou, avem două operațiuni
pe care le pot efectua acum.

86
00:04:12,960 --> 00:04:14,270
Putem împinge și putem pop.

87
00:04:14,270 --> 00:04:15,635
Să începem cu apăsare.

88
00:04:15,635 --> 00:04:18,260
Din nou, împingând este adăugarea unui nou
Element de sus a stivei.

89
00:04:18,260 --> 00:04:21,460
>> Deci, ceea ce avem nevoie pentru a face în
această matrice de punere în aplicare pe baza?

90
00:04:21,460 --> 00:04:23,210
Ei bine, în general,
Funcția se va împinge

91
00:04:23,210 --> 00:04:26,160
a trebuie să accepte o
pointer la stiva.

92
00:04:26,160 --> 00:04:28,610
Acum, ia un al doilea și cred despre el.

93
00:04:28,610 --> 00:04:32,840
De ce am vrea să acceptăm
un pointer la stiva?

94
00:04:32,840 --> 00:04:36,830
Reamintim de la clipuri video anterioare referitoare la
Domeniul de aplicare și indicii variabilă,

95
00:04:36,830 --> 00:04:42,350
ce s-ar întâmpla dacă ne-am trimis
stack, e mai degrabă în ca parametru?

96
00:04:42,350 --> 00:04:45,770
Ce ar fi de fapt a trecut acolo?

97
00:04:45,770 --> 00:04:49,430
Amintiți-vă vom crea o copie
când l-am trece la o funcție

98
00:04:49,430 --> 00:04:51,160
daca nu vom folosi indicii.

99
00:04:51,160 --> 00:04:55,380
Și astfel această funcție împinge nevoilor
să accepte un pointer la stiva

100
00:04:55,380 --> 00:04:59,160
astfel încât suntem de fapt în schimbare
stiva intenționăm să se schimbe.

101
00:04:59,160 --> 00:05:03,060
>> Un alt lucru împinge probabil vrea să
accepta este un element de date a valorii tip.

102
00:05:03,060 --> 00:05:06,970
In acest caz, din nou, un număr întreg care
vom adăuga la partea de sus a stivei.

103
00:05:06,970 --> 00:05:08,680
Deci avem doi parametri noastre.

104
00:05:08,680 --> 00:05:11,310
Ce vom
acum face în interiorul împinge?

105
00:05:11,310 --> 00:05:14,860
Ei bine, pur și simplu, ne doar de gând să adăugați
că elementul în partea de sus a stivei

106
00:05:14,860 --> 00:05:22,860
și apoi modificați în cazul în care partea de sus a
stiva este că e dot valoare de top.

107
00:05:22,860 --> 00:05:25,639
Deci, asta este ceea ce o funcție
declarație de apăsare

108
00:05:25,639 --> 00:05:27,680
s-ar putea arata ca intr-un
-matrice pe bază de punere în aplicare.

109
00:05:27,680 --> 00:05:30,967
>> Din nou, aceasta nu este o regula tare si rapid
care le-ar putea schimba acest lucru și au

110
00:05:30,967 --> 00:05:32,050
aceasta variază în moduri diferite.

111
00:05:32,050 --> 00:05:33,840
Poate că s este declarat la nivel global.

112
00:05:33,840 --> 00:05:36,180
Și astfel încât să nu nevoie, chiar
pentru a trece este ca un parametru.

113
00:05:36,180 --> 00:05:39,125
Aceasta este din nou doar o
caz general pentru apăsare.

114
00:05:39,125 --> 00:05:41,000
Și acolo sunt diferite
moduri de a pune în aplicare.

115
00:05:41,000 --> 00:05:42,810
Dar în acest caz nostru
împinge va avea

116
00:05:42,810 --> 00:05:48,540
două argumente, un pointer la o stivă și
un element de date din valoarea de tip, întreg

117
00:05:48,540 --> 00:05:49,840
în acest caz.

118
00:05:49,840 --> 00:05:52,100
>> Deci, ne-am declarat s, am
a declarat s.top este egal cu 0.

119
00:05:52,100 --> 00:05:55,969
Acum, haideți să împingeți
Numărul 28 pe stiva.

120
00:05:55,969 --> 00:05:57,010
Ei bine, ce înseamnă asta?

121
00:05:57,010 --> 00:05:59,600
Ei bine, în prezent
partea de sus a stivei este 0.

122
00:05:59,600 --> 00:06:01,350
Și așa mai departe ceea ce este practic
se va întâmpla este

123
00:06:01,350 --> 00:06:05,820
vom lipi numărul
28 în matrice Localizare 0.

124
00:06:05,820 --> 00:06:09,540
Destul de simplu, chiar, că
a fost în partea de sus, iar acum suntem bine să plec.

125
00:06:09,540 --> 00:06:12,910
Și atunci avem nevoie pentru a schimba ceea ce
partea de sus a stivei va fi.

126
00:06:12,910 --> 00:06:15,130
Astfel încât data viitoare
am împinge un element în,

127
00:06:15,130 --> 00:06:18,017
vom stoca în
Locație matrice, probabil, nu 0.

128
00:06:18,017 --> 00:06:20,100
Noi nu vrem să suprascrieți
ceea ce ne-am pus acolo.

129
00:06:20,100 --> 00:06:23,510
Și așa vom muta doar în partea de sus a 1.

130
00:06:23,510 --> 00:06:24,890
Asta face, probabil, sens.

131
00:06:24,890 --> 00:06:28,940
>> Acum, dacă vrem să pună un alt element
pe stiva, spune că vrea să împingă 33,

132
00:06:28,940 --> 00:06:33,190
Ei bine, acum noi suntem doar de gând să ia 33
și a pus la matrice număr de locație

133
00:06:33,190 --> 00:06:37,580
1, și apoi modificați în partea de sus a noastră
stiva să fie matrice locație numărul doi.

134
00:06:37,580 --> 00:06:40,650
Deci, în cazul în care data viitoare vrem să
împinge un element pe stivă,

135
00:06:40,650 --> 00:06:43,087
Va fi pus în matrice locație 2.

136
00:06:43,087 --> 00:06:44,420
Și să faci asta o dată.

137
00:06:44,420 --> 00:06:45,753
Vom împinge 19 pe a stivelor.

138
00:06:45,753 --> 00:06:48,940
Vom pune 19 în matrice locație 2
și de a schimba partea de sus a stivei noastre

139
00:06:48,940 --> 00:06:51,220
să fie matrice locație 3
astfel încât în ​​cazul în care următoarea dată când am

140
00:06:51,220 --> 00:06:54,780
nevoie pentru a face un impuls suntem bine să plec.

141
00:06:54,780 --> 00:06:56,980
>> OK, așa că e împinge într-o coajă de nucă.

142
00:06:56,980 --> 00:06:57,830
Ce zici de popping?

143
00:06:57,830 --> 00:07:00,240
Deci popping este un fel de
omologul de împingere.

144
00:07:00,240 --> 00:07:02,720
E cum am elimina datele de pe stivă.

145
00:07:02,720 --> 00:07:04,610
Și în nevoile pop generale
să facă următoarele.

146
00:07:04,610 --> 00:07:07,600
Acesta trebuie să accepte un pointer la
stivă, din nou, în cazul general.

147
00:07:07,600 --> 00:07:10,480
Într-un alt caz s-ar putea
au declarat stiva la nivel global,

148
00:07:10,480 --> 00:07:13,910
caz în care nu aveți nevoie să-l treacă
în deoarece are deja acces la aceasta

149
00:07:13,910 --> 00:07:15,541
ca o variabilă globală.

150
00:07:15,541 --> 00:07:17,040
Dar atunci ce altceva mai trebuie să facem?

151
00:07:17,040 --> 00:07:21,000
Ei bine, am fost incrementarea
partea de sus a stivei în împingere,

152
00:07:21,000 --> 00:07:24,050
așa că, probabil, de gând să doriți
la decrement partea de sus a stivei

153
00:07:24,050 --> 00:07:25,009
în pop, nu?

154
00:07:25,009 --> 00:07:26,800
Și apoi, desigur,
ne, de asemenea, de gând să doriți

155
00:07:26,800 --> 00:07:29,240
pentru a reveni la valoarea pe care le elimina.

156
00:07:29,240 --> 00:07:32,125
Dacă suntem adăugarea de elemente, ne-o dorim
pentru a obține elemente din mai târziu,

157
00:07:32,125 --> 00:07:34,000
noi, probabil, de fapt,
doriți să le stocați așa că am

158
00:07:34,000 --> 00:07:36,490
Nu-i doar șterge din
stiva și apoi nu fac nimic cu ele.

159
00:07:36,490 --> 00:07:38,500
În general, dacă suntem
împingere și popping aici

160
00:07:38,500 --> 00:07:41,250
vrem pentru a stoca acest
informații într-un mod semnificativ

161
00:07:41,250 --> 00:07:43,250
și deci nu face
sens doar aruncați.

162
00:07:43,250 --> 00:07:46,380
Deci, această funcție ar trebui să
probabil a reveni o valoare pentru noi.

163
00:07:46,380 --> 00:07:51,040
>> Deci, asta este ceea ce o declarație pentru pop
s-ar putea arata ca acolo, la partea din stânga sus.

164
00:07:51,040 --> 00:07:53,870
Această funcție returnează
Date de valoare de tip.

165
00:07:53,870 --> 00:07:56,320
Din nou, am fost folosind
întregi de-a lungul.

166
00:07:56,320 --> 00:08:01,916
Și acceptă un pointer la o stivă ca
argumentul său unic sau parametru unic.

167
00:08:01,916 --> 00:08:03,040
Deci, ce este pop de gând să faci?

168
00:08:03,040 --> 00:08:07,990
Să presupunem că vrem să acum
pop un element de pe s.

169
00:08:07,990 --> 00:08:14,000
Deci, amintiți-vă am spus că sunt ultima stive
în, primul ieșit, structuri de date LIFO.

170
00:08:14,000 --> 00:08:17,855
Care element este de gând să
fi eliminate din stivă?

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

172
00:08:21,780 --> 00:08:24,150
Ai ghicit 19?

173
00:08:24,150 --> 00:08:25,290
Pentru că ai avea dreptate.

174
00:08:25,290 --> 00:08:28,836
19 a fost ultimul element am adaugat la
stiva atunci când am fost împingerea elemente pe,

175
00:08:28,836 --> 00:08:31,210
Și așa va primul
element care se îndepărtează.

176
00:08:31,210 --> 00:08:34,780
E ca și cum am spus 28, și
apoi am pus 33 pe partea de sus a acesteia,

177
00:08:34,780 --> 00:08:36,659
si am pus 19 pe deasupra.

178
00:08:36,659 --> 00:08:40,650
Singurul element putem scoate este de 19.

179
00:08:40,650 --> 00:08:45,019
>> Acum, în diagrama aici ceea ce am făcut
este un fel de șters 19 de matrice.

180
00:08:45,019 --> 00:08:46,810
Asta nu e de fapt
ceea ce am de gând să faci.

181
00:08:46,810 --> 00:08:48,934
Vom merge la fel doar
de pretinde că nu este acolo.

182
00:08:48,934 --> 00:08:51,441
E încă acolo, în
că locație de memorie,

183
00:08:51,441 --> 00:08:54,190
dar noi suntem doar de gând să-l ignore
prin schimbarea de sus a stivei noastre

184
00:08:54,190 --> 00:08:56,080
de a fi 3 la 2.

185
00:08:56,080 --> 00:08:58,720
Deci, dacă ar fi să împinge acum
un alt element pe stiva,

186
00:08:58,720 --> 00:09:00,720
ar scrie peste 19.

187
00:09:00,720 --> 00:09:03,990
>> Dar să nu treacă prin probleme
de ștergerea 19 din stivă.

188
00:09:03,990 --> 00:09:05,830
Putem pretinde pur și simplu nu este acolo.

189
00:09:05,830 --> 00:09:11,107
În scopul stivei a dispărut dacă
am schimba partea de sus să fie 2 în loc de 3.

190
00:09:11,107 --> 00:09:12,690
Bine, astfel că a fost destul de mult.

191
00:09:12,690 --> 00:09:15,080
Asta e tot ce trebuie să facem
să pop un element off.

192
00:09:15,080 --> 00:09:16,090
Să o facem din nou.

193
00:09:16,090 --> 00:09:18,610
Deci l-am evidențiat în roșu aici pentru a
indica facem un alt apel.

194
00:09:18,610 --> 00:09:19,720
Vom face același lucru.

195
00:09:19,720 --> 00:09:20,803
>> Deci, ce se va întâmpla?

196
00:09:20,803 --> 00:09:23,670
Ei bine, vom stoca
33 în X și vom

197
00:09:23,670 --> 00:09:26,217
pentru a schimba vârful stivei la 1.

198
00:09:26,217 --> 00:09:29,050
Așa că, dacă am acum pentru a împinge un
elementul în stivă care suntem

199
00:09:29,050 --> 00:09:31,610
de gând să faci acum,
ce se va întâmpla

200
00:09:31,610 --> 00:09:36,367
este vom suprascriere
matrice locație numărul 1.

201
00:09:36,367 --> 00:09:38,950
Astfel încât 33, care a fost un fel de lăsat
în spatele că ne-am prefăcut

202
00:09:38,950 --> 00:09:44,390
nu este acolo mai, noi suntem doar de gând
să-l lovească și a pus acolo în loc de 40.

203
00:09:44,390 --> 00:09:46,290
Și apoi, desigur,
Din moment ce am făcut un push,

204
00:09:46,290 --> 00:09:48,780
vom incrementa
partea de sus a stivei la 1 la 2

205
00:09:48,780 --> 00:09:50,950
astfel încât, dacă vom adăuga acum
Un alt element Va

206
00:09:50,950 --> 00:09:54,700
du-te în matrice locație numărul doi.

207
00:09:54,700 --> 00:09:57,590
>> Acum liste legate sunt un alt
mod de a pune în aplicare stive.

208
00:09:57,590 --> 00:10:01,210
Și dacă această definiție cu privire la
Ecranul aici pare familiar pentru tine,

209
00:10:01,210 --> 00:10:04,260
este pentru că se pare aproape
exact aceeași, în fapt,

210
00:10:04,260 --> 00:10:07,790
aceasta destul de mult este exact
La fel ca o listă individual legate,

211
00:10:07,790 --> 00:10:11,990
dacă vă amintiți de la discuția noastră de
legate individual liste într-un alt film.

212
00:10:11,990 --> 00:10:15,510
Singura restricție aici
este pentru noi ca programatori,

213
00:10:15,510 --> 00:10:17,900
nu avem voie să
inserați sau ștergeți aleatoriu

214
00:10:17,900 --> 00:10:20,620
din lista individual legat
care am putea face anterior.

215
00:10:20,620 --> 00:10:25,820
Putem introduce doar acum și șterge de la
partea din față sau în partea de sus a strâns legat

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

217
00:10:26,320 --> 00:10:28,028
Asta e de fapt singurul
diferență, totuși.

218
00:10:28,028 --> 00:10:29,700
Aceasta este de altfel o listă individual legat.

219
00:10:29,700 --> 00:10:32,060
E doar restricția
înlocuirea pe noi înșine

220
00:10:32,060 --> 00:10:35,770
ca programatori care
schimba-l într-o stivă.

221
00:10:35,770 --> 00:10:39,280
>> Regula de aici este de a menține întotdeauna o
pointer la cap de o listă legată.

222
00:10:39,280 --> 00:10:41,520
Aceasta este, desigur, o, în general,
regulă importantă în primul rând.

223
00:10:41,520 --> 00:10:44,260
Pentru lista legate individual oricum
nevoie doar de un pointer la cap

224
00:10:44,260 --> 00:10:46,160
pentru a avea că
lanț putea să se refere

225
00:10:46,160 --> 00:10:48,596
pentru fiecare alt element
în lista legate.

226
00:10:48,596 --> 00:10:50,470
Dar e deosebit de
important, cu un stack.

227
00:10:50,470 --> 00:10:52,386
Și așa, în general, tu ești
O să vrea de fapt

228
00:10:52,386 --> 00:10:54,090
Acest indicator a fi o variabilă globală.

229
00:10:54,090 --> 00:10:56,574
Este, probabil, o să
fi chiar mai ușor așa.

230
00:10:56,574 --> 00:10:58,240
Deci, care sunt analogii de împingere și pop?

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

232
00:10:58,740 --> 00:11:01,812
Deci, împingând din nou este adăugarea
un nou element de stiva.

233
00:11:01,812 --> 00:11:03,770
Într-o listă legată care
înseamnă că vom avea

234
00:11:03,770 --> 00:11:07,770
pentru a crea un nou nod pe care suntem
merge pentru a adăuga în lista legate,

235
00:11:07,770 --> 00:11:10,500
și apoi urmați pașii atente
care le-am subliniat anterior

236
00:11:10,500 --> 00:11:16,050
în listele individual legate de adauga la
lanțul fără a rupe lanțul

237
00:11:16,050 --> 00:11:18,900
și pierderea sau orice orphaning
Elemente ale listei de legătura.

238
00:11:18,900 --> 00:11:21,820
Și asta e de fapt despre ce
puțin blob de text acolo rezumă.

239
00:11:21,820 --> 00:11:23,740
Și haideți să aruncăm o privire
la ea ca o diagramă.

240
00:11:23,740 --> 00:11:24,823
>> Deci, aici e lista noastră legată.

241
00:11:24,823 --> 00:11:26,620
Acesta conține concomitent patru elemente.

242
00:11:26,620 --> 00:11:30,420
Și mai perfect aici e noastră
stiva conține patru elemente.

243
00:11:30,420 --> 00:11:36,030
Și să spunem că vrem acum să
împinge un element nou pe acest stivă.

244
00:11:36,030 --> 00:11:39,792
Și vrem să împingă un nou
articol căror date valoare este de 12.

245
00:11:39,792 --> 00:11:41,000
Ei bine, ce vom face?

246
00:11:41,000 --> 00:11:43,420
Ei bine, în primul rând vom
spațiu malloc, dinamic

247
00:11:43,420 --> 00:11:45,411
aloca spațiu pentru un nou nod.

248
00:11:45,411 --> 00:11:48,160
Și, desigur, imediat după
facem un apel la noi malloc mereu

249
00:11:48,160 --> 00:11:52,989
asigurați-vă că pentru a verifica pentru nul,
pentru că dacă ne-am întors nul

250
00:11:52,989 --> 00:11:54,280
nu a fost un fel de probleme.

251
00:11:54,280 --> 00:11:57,570
Noi nu vrem să dereference că null
pointer sau vei suferi o defecțiune seg.

252
00:11:57,570 --> 00:11:58,510
Asta nu este bine.

253
00:11:58,510 --> 00:11:59,760
Deci ne-am malloced a nodului.

254
00:11:59,760 --> 00:12:01,260
Vom presupune că am avut succes aici.

255
00:12:01,260 --> 00:12:06,090
Vom pune în 12
câmpul de date de acel nod.

256
00:12:06,090 --> 00:12:11,570
Acum nu vă amintiți care a indicii noastre
se mută lângă asa ca nu rupe lantul?

257
00:12:11,570 --> 00:12:15,100
Avem o serie de opțiuni, dar aici
singurul care va fi în siguranță

258
00:12:15,100 --> 00:12:19,330
este de a stabili următoare de știri pointer la
punct la cap vechi listei

259
00:12:19,330 --> 00:12:21,360
sau ceea ce va fi în curând
șef veche a listei.

260
00:12:21,360 --> 00:12:23,610
Și acum că toate noastre
elemente sunt legate împreună,

261
00:12:23,610 --> 00:12:27,370
ne putem muta doar lista de la punctul
în același loc pe care noi nu.

262
00:12:27,370 --> 00:12:33,550
Și acum ne-am impins efectiv o
element nou pe partea din față a stivei.

263
00:12:33,550 --> 00:12:36,420
>> Pentru a ne pop vreau doar să
șterge că prim element.

264
00:12:36,420 --> 00:12:38,150
Și așa mai departe, practic ceea ce
trebuie să facem aici,

265
00:12:38,150 --> 00:12:40,050
bine trebuie să găsim al doilea element.

266
00:12:40,050 --> 00:12:43,540
În cele din urmă, care va deveni noul
cap după ce am șterge prima.

267
00:12:43,540 --> 00:12:47,300
Deci, avem nevoie doar pentru a începe de la
la început, a muta o înainte.

268
00:12:47,300 --> 00:12:50,340
După avem o așteptare pe o
înainte de unde am în prezent

269
00:12:50,340 --> 00:12:53,850
sunt putem șterge primul în condiții de siguranță
si apoi ne putem muta doar capul

270
00:12:53,850 --> 00:12:57,150
pentru a indica ceea ce a fost
al doilea mandat și apoi acum

271
00:12:57,150 --> 00:12:59,170
este primul după care
nod a fost șters.

272
00:12:59,170 --> 00:13:01,160
>> Deci, din nou, a lua o privire
ca pe o diagrama ne

273
00:13:01,160 --> 00:13:05,022
doriți să pop acum un
Element de pe acest stack.

274
00:13:05,022 --> 00:13:05,730
Deci, ce facem?

275
00:13:05,730 --> 00:13:08,188
Ei bine, vom mai întâi de gând să creeze
un nou indicator care va

276
00:13:08,188 --> 00:13:10,940
pentru a indica în același loc ca și cap.

277
00:13:10,940 --> 00:13:13,790
Vom muta o poziție
înainte de a spune egali trav

278
00:13:13,790 --> 00:13:17,510
trav următor, de exemplu, care
ar avansa cel trav pointer

279
00:13:17,510 --> 00:13:19,324
poziție înainte.

280
00:13:19,324 --> 00:13:21,240
Acum, că avem o
țineți pe primul element

281
00:13:21,240 --> 00:13:24,573
prin lista pointer numit, și
al doilea element prin intermediul unui pointer numit

282
00:13:24,573 --> 00:13:28,692
trav, putem șterge cu siguranță că
primul element de din stivă

283
00:13:28,692 --> 00:13:30,650
fără a pierde restul
lanțului deoarece ne

284
00:13:30,650 --> 00:13:32,358
au un mod de a se refere
la al doilea element

285
00:13:32,358 --> 00:13:34,780
transmite prin intermediul
pointer trav numit.

286
00:13:34,780 --> 00:13:37,100
>> Deci, acum putem elibera acel nod.

287
00:13:37,100 --> 00:13:38,404
Putem elibera lista.

288
00:13:38,404 --> 00:13:41,320
Și atunci tot ce trebuie să facem acum este
muta lista de la punctul în același loc

289
00:13:41,320 --> 00:13:44,482
că trav face, si noi suntem un fel de spate
în cazul în care am început înainte de 12 împins

290
00:13:44,482 --> 00:13:45,690
pe, în primul rând, chiar.

291
00:13:45,690 --> 00:13:46,940
Acest lucru este exact acolo unde am fost.

292
00:13:46,940 --> 00:13:48,840
Am avut această stivă de patru elemente.

293
00:13:48,840 --> 00:13:49,690
Am adăugat un al cincilea.

294
00:13:49,690 --> 00:13:51,910
Am împins o cincime
element de pe, și apoi ne-am

295
00:13:51,910 --> 00:13:55,980
mi-a venit ca cel mai recent
Element adăugat înapoi.

296
00:13:55,980 --> 00:13:58,816
>> Asta e într-adevăr destul de mult
tot ceea ce este de a stive.

297
00:13:58,816 --> 00:14:00,190
Puteți le pună în aplicare ca matrice.

298
00:14:00,190 --> 00:14:01,815
Puteți le pună în aplicare ca listele legate.

299
00:14:01,815 --> 00:14:04,810
Există, desigur, alte
modalități de a le pune în aplicare, de asemenea.

300
00:14:04,810 --> 00:14:09,060
Practic motivul pentru care am ar folosi
stive este de a menține datele în așa fel

301
00:14:09,060 --> 00:14:12,090
că cel mai recent adăugat
element este primul lucru pe care suntem

302
00:14:12,090 --> 00:14:14,980
O să vrea să mă întorc.

303
00:14:14,980 --> 00:14:17,900
Sunt Doug Lloyd, aceasta este CS50.

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