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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Va bene,
quindi da questo punto sei

3
00:00:05,990 --> 00:00:09,020
probabilmente abbastanza familiare
con array e liste concatenate

4
00:00:09,020 --> 00:00:10,950
che è due primario
strutture di dati che abbiamo

5
00:00:10,950 --> 00:00:16,810
parlato per mantenere gruppi di
dati di tipi di dati simili organizzata.

6
00:00:16,810 --> 00:00:19,080
>> Ora stiamo andando a parlare
di un paio di variazioni

7
00:00:19,080 --> 00:00:20,330
su array e liste concatenate.

8
00:00:20,330 --> 00:00:22,362
In questo video andremo
per parlare di stack.

9
00:00:22,362 --> 00:00:25,320
In particolare stiamo andando a parlare
una struttura dati detta pila.

10
00:00:25,320 --> 00:00:28,510
Richiamo da precedenti discussioni
su puntatori e la memoria,

11
00:00:28,510 --> 00:00:32,060
che la pila è anche la
il nome per un segmento della memoria

12
00:00:32,060 --> 00:00:34,980
dove staticamente dichiarato
memoria memory-- che

13
00:00:34,980 --> 00:00:38,730
nome, variabili che è il nome, et
cetera e funzionali strutture che abbiamo anche

14
00:00:38,730 --> 00:00:41,000
Esistono stack frame di chiamata.

15
00:00:41,000 --> 00:00:45,421
Quindi questa è una struttura di dati pila
Non un segmento di stack di memoria.

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

17
00:00:45,920 --> 00:00:46,890
>> Ma che cosa è una pila?

18
00:00:46,890 --> 00:00:49,220
Quindi è praticamente solo un
speciale tipo di struttura

19
00:00:49,220 --> 00:00:51,190
che mantiene i dati in modo organizzato.

20
00:00:51,190 --> 00:00:53,760
E ci sono due molto
modi comuni per implementare

21
00:00:53,760 --> 00:00:57,380
pile utilizzando due strutture dati
che siamo già familiarità con,

22
00:00:57,380 --> 00:01:00,340
array e liste concatenate.

23
00:01:00,340 --> 00:01:04,430
Che cosa rende una speciale pila è il
modo in cui abbiamo messo informazioni

24
00:01:04,430 --> 00:01:08,200
nella pila, e il modo in cui
rimuovere le informazioni dallo stack.

25
00:01:08,200 --> 00:01:11,600
In particolare con pile
la regola è solo il più

26
00:01:11,600 --> 00:01:15,830
recentemente elemento aggiunto può essere rimosso.

27
00:01:15,830 --> 00:01:17,660
>> Quindi pensare come se fosse una pila.

28
00:01:17,660 --> 00:01:21,170
Stiamo accumulando informazioni
su se stesso,

29
00:01:21,170 --> 00:01:24,271
e solo la cosa in alto
del palo può essere rimosso.

30
00:01:24,271 --> 00:01:27,020
Non possiamo rimuovere la cosa sotto
perché tutto il resto sarebbe

31
00:01:27,020 --> 00:01:28,020
collasso e cadere.

32
00:01:28,020 --> 00:01:32,580
Quindi stiamo davvero costruendo uno stack che
abbiamo poi rimuovere pezzo per pezzo.

33
00:01:32,580 --> 00:01:36,590
A causa di questo ci riferiamo comunemente
uno stack come struttura LIFO,

34
00:01:36,590 --> 00:01:38,940
last in, first out.

35
00:01:38,940 --> 00:01:42,290
LIFO, durano in, first out.

36
00:01:42,290 --> 00:01:45,635
>> Quindi, a causa di questa restrizione
come le informazioni possono essere aggiunto

37
00:01:45,635 --> 00:01:49,080
e rimosso da una pila, non c'è davvero
solo due cose che possiamo fare con uno stack.

38
00:01:49,080 --> 00:01:52,010
Siamo in grado di spingere, che è il
termine che usiamo per l'aggiunta

39
00:01:52,010 --> 00:01:55,130
un nuovo elemento all'inizio della
pila, o se la pila non esiste

40
00:01:55,130 --> 00:01:58,550
e stiamo creando da zero,
creando pila in primo luogo

41
00:01:58,550 --> 00:02:00,110
sarebbe spingere.

42
00:02:00,110 --> 00:02:04,990
E poi pop, che è il genere di CS
termine che usiamo per rimuovere il più recente

43
00:02:04,990 --> 00:02:08,330
aggiunto elemento dalla sommità della pila.

44
00:02:08,330 --> 00:02:11,130
>> Quindi stiamo andando a guardare sia
implementazioni, basata sia di matrice

45
00:02:11,130 --> 00:02:13,120
e lista collegata based.

46
00:02:13,120 --> 00:02:14,870
E stiamo andando a
iniziare con matrice a base.

47
00:02:14,870 --> 00:02:19,990
Quindi, ecco l'idea di base di ciò che
la struttura di dati pila di allineamenti basato

48
00:02:19,990 --> 00:02:21,140
sarebbe simile.

49
00:02:21,140 --> 00:02:23,740
Abbiamo una definizione digitato qui.

50
00:02:23,740 --> 00:02:27,790
All'interno di che abbiamo due membri
o campi della struttura.

51
00:02:27,790 --> 00:02:29,880
Abbiamo un array.

52
00:02:29,880 --> 00:02:32,400
E di nuovo Sto utilizzando il
arbitrario valore di tipo di dati.

53
00:02:32,400 --> 00:02:35,180
>> Quindi questo potrebbe essere qualsiasi tipo di dati,
int char o altri dati

54
00:02:35,180 --> 00:02:37,080
digita creato in precedenza.

55
00:02:37,080 --> 00:02:39,861
Quindi abbiamo una vasta gamma di capacità di dimensioni.

56
00:02:39,861 --> 00:02:44,010
Capacità di essere un chilo definito costante,
forse da qualche altra parte nel nostro file.

57
00:02:44,010 --> 00:02:47,550
Così notare già con questo particolare
implementazione stiamo delimitazione

58
00:02:47,550 --> 00:02:49,800
noi stessi come era tipicamente
il caso con gli array,

59
00:02:49,800 --> 00:02:53,170
che non siamo in grado di ridimensionare in modo dinamico,
dove c'è un certo numero

60
00:02:53,170 --> 00:02:55,450
di elementi massima
siamo in grado di mettere nel nostro stack.

61
00:02:55,450 --> 00:02:57,930
In questo caso è elementi di capacità.

62
00:02:57,930 --> 00:03:00,310
>> Teniamo anche traccia di
la parte superiore della pila.

63
00:03:00,310 --> 00:03:04,350
Quale elemento è il più
recentemente aggiunto alla pila?

64
00:03:04,350 --> 00:03:07,470
E così teniamo traccia di quel
in una parte superiore variabile chiamata.

65
00:03:07,470 --> 00:03:11,692
E tutto questo viene avvolto insieme
in un nuovo tipo di dati denominato una pila.

66
00:03:11,692 --> 00:03:13,400
E una volta che siamo creati
questo nuovo tipo di dati

67
00:03:13,400 --> 00:03:15,410
siamo in grado di trattarlo come
qualsiasi altro tipo di dati.

68
00:03:15,410 --> 00:03:20,970
Possiamo dichiarare pila s, proprio come
potremmo fare int x, o char a.

69
00:03:20,970 --> 00:03:22,990
E quando diciamo impilare
s, ben cosa succede

70
00:03:22,990 --> 00:03:26,420
è si ottiene una serie di
memoria accantonato per noi.

71
00:03:26,420 --> 00:03:28,770
>> In questo caso la capacità
Ho deciso a quanto pare

72
00:03:28,770 --> 00:03:33,470
è 10 perché ho un
singola variabile di tipo pila

73
00:03:33,470 --> 00:03:35,320
che contiene due campi ricordano.

74
00:03:35,320 --> 00:03:38,330
Un array, in questo caso va
essere un array di interi

75
00:03:38,330 --> 00:03:40,440
come è il caso nella maggior parte dei miei esempi.

76
00:03:40,440 --> 00:03:43,996
E un'altra variabile intera
in grado di memorizzare l'alto,

77
00:03:43,996 --> 00:03:45,870
il più recentemente aggiunto
elemento allo stack.

78
00:03:45,870 --> 00:03:50,290
Così una sola pila di quello che abbiamo
appena definito simile a questa.

79
00:03:50,290 --> 00:03:53,190
Si tratta di una scatola contenente
una matrice di 10 Come

80
00:03:53,190 --> 00:03:57,280
saranno numeri interi in questo caso e
un'altra variabile intera lì in verde

81
00:03:57,280 --> 00:04:00,010
per indicare la parte superiore della pila.

82
00:04:00,010 --> 00:04:02,600
>> Per impostare la parte superiore della
pila diciamo solo s.top.

83
00:04:02,600 --> 00:04:04,890
Ecco come si accede a
campo di una struttura di richiamo.

84
00:04:04,890 --> 00:04:10,460
s.top uguale a 0 in modo efficace
fa questo per il nostro stack.

85
00:04:10,460 --> 00:04:12,960
Così ancora una volta abbiamo due operazioni
che possiamo eseguire ora.

86
00:04:12,960 --> 00:04:14,270
Siamo in grado di spingere e possiamo pop.

87
00:04:14,270 --> 00:04:15,635
Cominciamo con spinta.

88
00:04:15,635 --> 00:04:18,260
Ancora una volta, spingendo è l'aggiunta di una nuova
elemento in cima alla pila.

89
00:04:18,260 --> 00:04:21,460
>> Così che cosa abbiamo bisogno di fare in
questo array implementazione basata?

90
00:04:21,460 --> 00:04:23,210
Bene in generale
funzione push sta andando

91
00:04:23,210 --> 00:04:26,160
per necessità di accettare un
puntatore alla pila.

92
00:04:26,160 --> 00:04:28,610
Ora prendere un secondo e pensarci.

93
00:04:28,610 --> 00:04:32,840
Perché vogliamo accettare
un puntatore alla pila?

94
00:04:32,840 --> 00:04:36,830
Ricordiamo dal video precedenti su
scope delle variabili e puntatori,

95
00:04:36,830 --> 00:04:42,350
cosa accadrebbe se abbiamo appena inviato
pila, s piuttosto come parametro?

96
00:04:42,350 --> 00:04:45,770
Che cosa sarebbe effettivamente essere passato lì dentro?

97
00:04:45,770 --> 00:04:49,430
Ricordate che stiamo creando una copia
quando si passa ad una funzione

98
00:04:49,430 --> 00:04:51,160
a meno che non usiamo i puntatori.

99
00:04:51,160 --> 00:04:55,380
E così questa funzione premere esigenze
accettare un puntatore alla pila

100
00:04:55,380 --> 00:04:59,160
così che realmente stiamo cambiando
lo stack abbiamo intenzione di cambiare.

101
00:04:59,160 --> 00:05:03,060
>> L'altra cosa spinta probabilmente vuole
accettare è un dato di valore tipo.

102
00:05:03,060 --> 00:05:06,970
In questo caso, ancora una volta, un numero intero che
stiamo andando a aggiungere alla cima della pila.

103
00:05:06,970 --> 00:05:08,680
Così abbiamo i nostri due parametri.

104
00:05:08,680 --> 00:05:11,310
Che cosa stiamo andando a
ora fare all'interno di spinta?

105
00:05:11,310 --> 00:05:14,860
Beh, semplicemente, stiamo solo andando ad aggiungere
tale elemento in cima alla pila

106
00:05:14,860 --> 00:05:22,860
e quindi cambiare dove la parte superiore
la pila è, che s puntino valore superiore.

107
00:05:22,860 --> 00:05:25,639
Quindi questo è quello che una funzione
dichiarazione di spinta

108
00:05:25,639 --> 00:05:27,680
potrebbe apparire come in un
matrice a base di implementazione.

109
00:05:27,680 --> 00:05:30,967
>> Anche in questo caso non è una regola ferrea
che si potrebbe cambiare questo e hanno

110
00:05:30,967 --> 00:05:32,050
essa vari in modi diversi.

111
00:05:32,050 --> 00:05:33,840
Forse s è dichiarato a livello globale.

112
00:05:33,840 --> 00:05:36,180
E così non è nemmeno necessario
passare è come parametro.

113
00:05:36,180 --> 00:05:39,125
Anche questo è solo un
caso generale per spingere.

114
00:05:39,125 --> 00:05:41,000
E ci sono diversi
i modi per attuarla.

115
00:05:41,000 --> 00:05:42,810
Ma in questo caso il nostro
spinta sta andando a prendere

116
00:05:42,810 --> 00:05:48,540
due argomenti, un puntatore ad una pila e
un dato di valore tipo, integer

117
00:05:48,540 --> 00:05:49,840
in questo caso.

118
00:05:49,840 --> 00:05:52,100
>> Così abbiamo dichiarato s, abbiamo
ha detto s.top è uguale a 0.

119
00:05:52,100 --> 00:05:55,969
Ora cerchiamo di spingere la
numero 28 nello stack.

120
00:05:55,969 --> 00:05:57,010
Beh, che cosa significa?

121
00:05:57,010 --> 00:05:59,600
Beh, attualmente il
cima alla pila è 0.

122
00:05:59,600 --> 00:06:01,350
E così ciò che è fondamentalmente
sta per accadere è

123
00:06:01,350 --> 00:06:05,820
stiamo andando a bastone il numero
28 in posizione di matrice 0.

124
00:06:05,820 --> 00:06:09,540
Piuttosto semplice, giusto, che
era la parte superiore e ora siamo pronti per partire.

125
00:06:09,540 --> 00:06:12,910
E poi abbiamo bisogno di cambiare ciò che
cima alla pila sarà.

126
00:06:12,910 --> 00:06:15,130
Così la prossima volta
spingiamo un elemento,

127
00:06:15,130 --> 00:06:18,017
abbiamo intenzione di conservarlo in
posizione matrice, probabilmente non 0.

128
00:06:18,017 --> 00:06:20,100
Non vogliamo sovrascrivere
quello che abbiamo appena messo lì.

129
00:06:20,100 --> 00:06:23,510
E così ci limiteremo a spostare la parte superiore a 1.

130
00:06:23,510 --> 00:06:24,890
Che rende probabilmente senso.

131
00:06:24,890 --> 00:06:28,940
>> Ora, se vogliamo mettere un altro elemento
nello stack, diciamo che vogliamo spingere 33,

132
00:06:28,940 --> 00:06:33,190
bene ora stiamo solo andando a prendere 33
e metterlo al numero posizione di matrice

133
00:06:33,190 --> 00:06:37,580
1, e quindi modificare la parte superiore della nostra
impilare essere matrice posizione numero due.

134
00:06:37,580 --> 00:06:40,650
Quindi, se la prossima volta che vogliamo
spingere un elemento nello stack,

135
00:06:40,650 --> 00:06:43,087
Sarà messo in ordine di posizione 2.

136
00:06:43,087 --> 00:06:44,420
E facciamolo più una volta.

137
00:06:44,420 --> 00:06:45,753
Ti spingere 19 al largo delle pile.

138
00:06:45,753 --> 00:06:48,940
Metteremo 19 in ordine di posizione 2
e modificare cima della nostra pila

139
00:06:48,940 --> 00:06:51,220
per essere luogo di matrice 3
quindi se la prossima volta che

140
00:06:51,220 --> 00:06:54,780
bisogno di fare una spinta che siamo a posto.

141
00:06:54,780 --> 00:06:56,980
>> OK, così che sta spingendo in poche parole.

142
00:06:56,980 --> 00:06:57,830
Che dire di popping?

143
00:06:57,830 --> 00:07:00,240
Così popping è il tipo di
controparte a spingere.

144
00:07:00,240 --> 00:07:02,720
E 'quanto togliamo i dati dallo stack.

145
00:07:02,720 --> 00:07:04,610
E nei bisogni pop generali
a fare quanto segue.

146
00:07:04,610 --> 00:07:07,600
Deve accettare un puntatore
pila, sempre nel caso generale.

147
00:07:07,600 --> 00:07:10,480
In qualche altro caso si potrebbe
hanno dichiarato lo stack a livello globale,

148
00:07:10,480 --> 00:07:13,910
nel qual caso non c'è bisogno di passare
in quanto ha già accesso ad essa

149
00:07:13,910 --> 00:07:15,541
come variabile globale.

150
00:07:15,541 --> 00:07:17,040
Ma allora che cosa altro abbiamo bisogno di fare?

151
00:07:17,040 --> 00:07:21,000
Bene siamo stati Incremento
la parte superiore della pila di spinta,

152
00:07:21,000 --> 00:07:24,050
quindi stiamo probabilmente andando a voler
decrementare cima alla pila

153
00:07:24,050 --> 00:07:25,009
pop, giusto?

154
00:07:25,009 --> 00:07:26,800
E poi, naturalmente,
stiamo anche andando a voler

155
00:07:26,800 --> 00:07:29,240
per restituire il valore di rimuovere.

156
00:07:29,240 --> 00:07:32,125
Se stiamo aggiungendo elementi, vogliamo
per ottenere elementi di uscire più tardi,

157
00:07:32,125 --> 00:07:34,000
probabilmente in realtà
desidera memorizzare loro, così abbiamo

158
00:07:34,000 --> 00:07:36,490
non solo eliminarli dal
impilare e poi non fare nulla con loro.

159
00:07:36,490 --> 00:07:38,500
Generalmente se siamo
spingendo e popping qui

160
00:07:38,500 --> 00:07:41,250
vogliamo conservare questo
informazioni in modo significativo

161
00:07:41,250 --> 00:07:43,250
e così non fa
senso di scartare proprio questo.

162
00:07:43,250 --> 00:07:46,380
Quindi, questa funzione dovrebbe
probabilmente restituire un valore per noi.

163
00:07:46,380 --> 00:07:51,040
>> Quindi questo è quello che una dichiarazione di schiocco
potrebbe apparire come lì in alto a sinistra.

164
00:07:51,040 --> 00:07:53,870
Questa funzione restituisce
Dati di valore di tipo.

165
00:07:53,870 --> 00:07:56,320
Ancora una volta siamo stati con
interi in tutto.

166
00:07:56,320 --> 00:08:01,916
E accetta un puntatore a una pila come
l'unico argomento o un parametro unico.

167
00:08:01,916 --> 00:08:03,040
Allora, cosa sta pop intenzione di fare?

168
00:08:03,040 --> 00:08:07,990
Diciamo che vogliamo ora
pop un elemento fuori di s.

169
00:08:07,990 --> 00:08:14,000
Così ricordo che ho detto che stack sono scorsa
in, first out, strutture dati LIFO.

170
00:08:14,000 --> 00:08:17,855
Quale elemento sta per
essere rimosso dalla pila?

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

172
00:08:21,780 --> 00:08:24,150
Hai fatto a indovinare 19?

173
00:08:24,150 --> 00:08:25,290
Perché avreste ragione.

174
00:08:25,290 --> 00:08:28,836
19 era l'ultimo elemento abbiamo aggiunto alla
impilare quando stavamo spingendo elementi su,

175
00:08:28,836 --> 00:08:31,210
e così sta andando alla prima
elemento che viene rimosso.

176
00:08:31,210 --> 00:08:34,780
E 'come se dicessimo 28, e
poi abbiamo messo 33 su di esso,

177
00:08:34,780 --> 00:08:36,659
e abbiamo messo 19 in cima a quello.

178
00:08:36,659 --> 00:08:40,650
L'unico elemento che possiamo decollare è 19.

179
00:08:40,650 --> 00:08:45,019
>> Ora, nello schema qui quello che ho fatto
è una sorta di cancellata 19 dalla matrice.

180
00:08:45,019 --> 00:08:46,810
Questo non è in realtà
quello che andremo a fare.

181
00:08:46,810 --> 00:08:48,934
Stiamo solo andando a tipo
di far finta che non c'è.

182
00:08:48,934 --> 00:08:51,441
E 'ancora lì a
quella posizione di memoria,

183
00:08:51,441 --> 00:08:54,190
ma stiamo solo andando a ignorarlo
cambiando all'inizio della nostra pila

184
00:08:54,190 --> 00:08:56,080
dall'essere 3 a 2.

185
00:08:56,080 --> 00:08:58,720
Quindi, se dovessimo ora spingere
un altro elemento nello stack,

186
00:08:58,720 --> 00:09:00,720
sarebbe sovrascrivere 19.

187
00:09:00,720 --> 00:09:03,990
>> Ma non passare attraverso la briga
di cancellazione 19 dalla pila.

188
00:09:03,990 --> 00:09:05,830
Possiamo solo far finta che non ci sia.

189
00:09:05,830 --> 00:09:11,107
Ai fini della pila è andato se
cambiamo la parte superiore per essere 2 invece di 3.

190
00:09:11,107 --> 00:09:12,690
Va bene, così che era praticamente.

191
00:09:12,690 --> 00:09:15,080
Questo è tutto quello che dobbiamo fare
al pop un elemento fuori.

192
00:09:15,080 --> 00:09:16,090
Facciamolo ancora.

193
00:09:16,090 --> 00:09:18,610
Così ho evidenziato in rosso qui a
indicano che stiamo facendo un'altra chiamata.

194
00:09:18,610 --> 00:09:19,720
Andiamo a fare la stessa cosa.

195
00:09:19,720 --> 00:09:20,803
>> Quindi cosa succederà?

196
00:09:20,803 --> 00:09:23,670
Beh, stiamo andando a memorizzare
33 in x e stiamo andando

197
00:09:23,670 --> 00:09:26,217
modificare la cima della pila a 1.

198
00:09:26,217 --> 00:09:29,050
In modo che se fossimo ora a spingere un
elemento nella pila che siamo

199
00:09:29,050 --> 00:09:31,610
andando a fare in questo momento,
cosa succederà

200
00:09:31,610 --> 00:09:36,367
è che andremo sovrascrittura
matrice numero di posizione 1.

201
00:09:36,367 --> 00:09:38,950
Così che il 33 che è stato una sorta di sinistra
dietro che abbiamo appena finto

202
00:09:38,950 --> 00:09:44,390
non c'è più, stiamo solo andando
per clobber e mettere 40 lì, invece.

203
00:09:44,390 --> 00:09:46,290
E poi, naturalmente,
da quando abbiamo fatto una spinta,

204
00:09:46,290 --> 00:09:48,780
stiamo andando a incrementare il
cima alla pila da 1 al 2

205
00:09:48,780 --> 00:09:50,950
in modo che se ora aggiungiamo
un altro elemento che sarà

206
00:09:50,950 --> 00:09:54,700
andare in array di posizione numero due.

207
00:09:54,700 --> 00:09:57,590
>> Ora liste collegate sono un altro
modo per implementare stack.

208
00:09:57,590 --> 00:10:01,210
E se questa definizione sulla
schermo qui sembra familiare a voi,

209
00:10:01,210 --> 00:10:04,260
è perché sembra quasi
esattamente lo stesso, infatti,

210
00:10:04,260 --> 00:10:07,790
è più o meno è esattamente il
stessa come una lista concatenata,

211
00:10:07,790 --> 00:10:11,990
se vi ricordate dalla nostra discussione di
singolarmente concatenata liste in un altro video.

212
00:10:11,990 --> 00:10:15,510
L'unica restrizione qui
è per noi come i programmatori,

213
00:10:15,510 --> 00:10:17,900
non siamo autorizzati a
inserire o eliminare in modo casuale

214
00:10:17,900 --> 00:10:20,620
dalla lista concatenata
che potremmo fare in precedenza.

215
00:10:20,620 --> 00:10:25,820
Siamo solo ora in grado di inserire ed eliminare da
la parte anteriore o la parte superiore della collegata

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

217
00:10:26,320 --> 00:10:28,028
Questo è davvero l'unico
differenza però.

218
00:10:28,028 --> 00:10:29,700
Questa è comunque una lista concatenata.

219
00:10:29,700 --> 00:10:32,060
E 'solo la restrizione
sostituzione su noi stessi

220
00:10:32,060 --> 00:10:35,770
come i programmatori che
cambia in una pila.

221
00:10:35,770 --> 00:10:39,280
>> La regola qui è quello di mantenere sempre un
puntatore alla testa di una lista collegata.

222
00:10:39,280 --> 00:10:41,520
Questo è ovviamente un genere
importante regola prima.

223
00:10:41,520 --> 00:10:44,260
Per concatenata lista in ogni caso si
solo bisogno di un puntatore alla testa

224
00:10:44,260 --> 00:10:46,160
per avere tale
catena di essere in grado di fare riferimento

225
00:10:46,160 --> 00:10:48,596
ad ogni altro elemento
nella lista collegata.

226
00:10:48,596 --> 00:10:50,470
Ma è particolarmente
importante con uno stack.

227
00:10:50,470 --> 00:10:52,386
E così generalmente sei
andando a realtà vuole

228
00:10:52,386 --> 00:10:54,090
questo puntatore ad una variabile globale.

229
00:10:54,090 --> 00:10:56,574
E 'probabilmente andando a
ancora più facile in questo modo.

230
00:10:56,574 --> 00:10:58,240
Ma quali sono gli analoghi di spinta e pop?

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

232
00:10:58,740 --> 00:11:01,812
Quindi spingere di nuovo è l'aggiunta di
un nuovo elemento allo stack.

233
00:11:01,812 --> 00:11:03,770
In una lista collegata che
significa che stiamo andando ad avere

234
00:11:03,770 --> 00:11:07,770
per creare un nuovo nodo che siamo
andando ad aggiungere alla lista linkata,

235
00:11:07,770 --> 00:11:10,500
e quindi seguire i passaggi accurati
che in precedenza abbiamo delineato

236
00:11:10,500 --> 00:11:16,050
nelle liste semplicemente concatenate per aggiungerlo
la catena senza rompere la catena

237
00:11:16,050 --> 00:11:18,900
e perdere o orfano qualsiasi
elementi della lista collegata.

238
00:11:18,900 --> 00:11:21,820
E questo è fondamentalmente ciò che
piccolo blob di testo ci riassume.

239
00:11:21,820 --> 00:11:23,740
E diamo uno sguardo
a come un diagramma.

240
00:11:23,740 --> 00:11:24,823
>> Quindi, ecco la nostra lista collegata.

241
00:11:24,823 --> 00:11:26,620
Esso contiene contemporaneamente quattro elementi.

242
00:11:26,620 --> 00:11:30,420
E più perfettamente ecco la nostra
impilare contenente quattro elementi.

243
00:11:30,420 --> 00:11:36,030
E diciamo ora vogliamo
spingere un nuovo elemento su questo stack.

244
00:11:36,030 --> 00:11:39,792
E vogliamo spingere una nuova
elemento il cui valore dei dati è di 12.

245
00:11:39,792 --> 00:11:41,000
Beh, quello che abbiamo intenzione di fare?

246
00:11:41,000 --> 00:11:43,420
Ben prima che andremo a
spazio malloc, dinamicamente

247
00:11:43,420 --> 00:11:45,411
allocare spazio per un nuovo nodo.

248
00:11:45,411 --> 00:11:48,160
E, naturalmente, subito dopo
facciamo una chiamata a malloc abbiamo sempre

249
00:11:48,160 --> 00:11:52,989
assicuratevi di controllare per nulla,
perché se abbiamo ottenuto nulla di nuovo

250
00:11:52,989 --> 00:11:54,280
c'era qualche tipo di problema.

251
00:11:54,280 --> 00:11:57,570
Noi non vogliamo che nulla dereference
puntatore o si subiranno un guasto seg.

252
00:11:57,570 --> 00:11:58,510
Questo non va bene.

253
00:11:58,510 --> 00:11:59,760
Così abbiamo malloced del nodo.

254
00:11:59,760 --> 00:12:01,260
Si suppone che abbiamo avuto successo qui.

255
00:12:01,260 --> 00:12:06,090
Stiamo andando a mettere in 12
il campo di dati di tale nodo.

256
00:12:06,090 --> 00:12:11,570
Ora ti ricordi quale dei nostri puntatori
muove prossimo in modo da non rompere la catena?

257
00:12:11,570 --> 00:12:15,100
Abbiamo un paio di opzioni qui, ma
l'unico che sta per essere sicuri

258
00:12:15,100 --> 00:12:19,330
è quello di impostare le notizie accanto puntatore
scegliere la vecchia testa della lista

259
00:12:19,330 --> 00:12:21,360
o quello che sarà presto il
vecchio capo della lista.

260
00:12:21,360 --> 00:12:23,610
E ora che tutti i nostri
elementi sono incatenati insieme,

261
00:12:23,610 --> 00:12:27,370
possiamo solo passare lista per puntare
nello stesso posto che fa nuova.

262
00:12:27,370 --> 00:12:33,550
Ed ora abbiamo effettivamente spinto un
nuovo elemento sulla parte anteriore della pila.

263
00:12:33,550 --> 00:12:36,420
>> Pop vogliamo solo
eliminare il primo elemento.

264
00:12:36,420 --> 00:12:38,150
E così in fondo ciò che
dobbiamo fare qui,

265
00:12:38,150 --> 00:12:40,050
bene dobbiamo trovare il secondo elemento.

266
00:12:40,050 --> 00:12:43,540
Alla fine che diventerà il nuovo
testa dopo cancelliamo il primo.

267
00:12:43,540 --> 00:12:47,300
Quindi abbiamo solo bisogno di partire da
All'inizio, spostare uno avanti.

268
00:12:47,300 --> 00:12:50,340
Una volta che abbiamo una stretta su un
avanti di dove siamo attualmente

269
00:12:50,340 --> 00:12:53,850
siamo possiamo eliminare il primo sicuro
e allora possiamo semplicemente spostare la testa

270
00:12:53,850 --> 00:12:57,150
per puntare a quello che era il
secondo mandato e quindi ora

271
00:12:57,150 --> 00:12:59,170
è il primo dopo che
nodo è stato eliminato.

272
00:12:59,170 --> 00:13:01,160
>> Quindi, di nuovo, dare un'occhiata
a come un diagramma noi

273
00:13:01,160 --> 00:13:05,022
vuole ora un pop
elemento off di questa pila.

274
00:13:05,022 --> 00:13:05,730
Allora cosa facciamo?

275
00:13:05,730 --> 00:13:08,188
Beh, stiamo andando a creare primo
un nuovo puntatore che sta succedendo

276
00:13:08,188 --> 00:13:10,940
per puntare allo stesso punto come la testa.

277
00:13:10,940 --> 00:13:13,790
Stiamo andando a spostare di una posizione
avanti dicendo pari trav

278
00:13:13,790 --> 00:13:17,510
trav prossimo ad esempio, che
avanzerebbe il puntatore trav uno

279
00:13:17,510 --> 00:13:19,324
posizione avanzata.

280
00:13:19,324 --> 00:13:21,240
Ora che abbiamo un
tenere sul primo elemento

281
00:13:21,240 --> 00:13:24,573
attraverso il puntatore chiamato lista, e il
secondo elemento tramite un puntatore chiamato

282
00:13:24,573 --> 00:13:28,692
trav, possiamo cancellare con sicurezza che
primo elemento dalla pila

283
00:13:28,692 --> 00:13:30,650
senza perdere il resto
della catena perché

284
00:13:30,650 --> 00:13:32,358
avere un modo per riferirsi
al secondo elemento

285
00:13:32,358 --> 00:13:34,780
trasmette attraverso la
puntatore chiamato trav.

286
00:13:34,780 --> 00:13:37,100
>> Così ora possiamo liberare quel nodo.

287
00:13:37,100 --> 00:13:38,404
Possiamo liberare lista.

288
00:13:38,404 --> 00:13:41,320
E poi tutto quello che dobbiamo fare ora è
passare lista per punto nello stesso posto

289
00:13:41,320 --> 00:13:44,482
che trav fa, e siamo sorta di schiena
dove siamo partiti prima abbiamo spinto 12

290
00:13:44,482 --> 00:13:45,690
sul in primo luogo, a destra.

291
00:13:45,690 --> 00:13:46,940
Questo è esattamente dove eravamo.

292
00:13:46,940 --> 00:13:48,840
Abbiamo avuto questo stack quattro elementi.

293
00:13:48,840 --> 00:13:49,690
Abbiamo aggiunto un quinto.

294
00:13:49,690 --> 00:13:51,910
Abbiamo spinto un quinto
elemento, e poi noi

295
00:13:51,910 --> 00:13:55,980
spuntato che la maggior parte di recente
elemento aggiunto indietro.

296
00:13:55,980 --> 00:13:58,816
>> Questo è davvero più o meno
tutto quello che c'è a pile.

297
00:13:58,816 --> 00:14:00,190
È possibile implementare come array.

298
00:14:00,190 --> 00:14:01,815
È possibile implementare come liste collegate.

299
00:14:01,815 --> 00:14:04,810
Ci sono, naturalmente, altri
le modalità di applicazione pure.

300
00:14:04,810 --> 00:14:09,060
Fondamentalmente la ragione useremmo
pile è quello di mantenere i dati in modo tale

301
00:14:09,060 --> 00:14:12,090
che il più recentemente aggiunto
elemento è la prima cosa che siamo

302
00:14:12,090 --> 00:14:14,980
andando a voler tornare.

303
00:14:14,980 --> 00:14:17,900
Sono Doug Lloyd, questo è CS50.

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