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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Tudo bem,
por isso, este ponto você está

3
00:00:05,990 --> 00:00:09,020
provavelmente bastante familiar
com matrizes e listas ligadas

4
00:00:09,020 --> 00:00:10,950
que é a dois primário
estruturas de dados que nós

5
00:00:10,950 --> 00:00:16,810
falou sobre por manter conjuntos de
dados de tipos de dados semelhantes organizado.

6
00:00:16,810 --> 00:00:19,080
>> Agora nós estamos indo falar
sobre um casal de variações

7
00:00:19,080 --> 00:00:20,330
em matrizes e listas ligadas.

8
00:00:20,330 --> 00:00:22,362
Neste vídeo nós vamos
para falar sobre pilhas.

9
00:00:22,362 --> 00:00:25,320
Especificamente vamos falar
sobre uma estrutura de dados denominada pilha.

10
00:00:25,320 --> 00:00:28,510
Lembre-se de discussões prévias
sobre ponteiros e memória,

11
00:00:28,510 --> 00:00:32,060
que a pilha também o é
nomear para um segmento de memória

12
00:00:32,060 --> 00:00:34,980
onde estaticamente declarado
memória memory-- que você

13
00:00:34,980 --> 00:00:38,730
nome, variáveis ​​que você nome, et
quadros cetera e função que também

14
00:00:38,730 --> 00:00:41,000
existem quadros de pilha de chamadas.

15
00:00:41,000 --> 00:00:45,421
Portanto, esta é uma estrutura de dados pilha
não um segmento de pilha de memória.

16
00:00:45,421 --> 00:00:45,920
ESTÁ BEM.

17
00:00:45,920 --> 00:00:46,890
>> Mas o que é uma pilha?

18
00:00:46,890 --> 00:00:49,220
Por isso, é praticamente apenas um
tipo especial de estrutura

19
00:00:49,220 --> 00:00:51,190
que mantém os dados de uma forma organizada.

20
00:00:51,190 --> 00:00:53,760
E há dois muito
maneiras comuns para implementar

21
00:00:53,760 --> 00:00:57,380
pilhas usando duas estruturas de dados
que já está familiarizado com,

22
00:00:57,380 --> 00:01:00,340
matrizes e listas ligadas.

23
00:01:00,340 --> 00:01:04,430
O que faz uma pilha especial é o
maneira em que podemos colocar informações

24
00:01:04,430 --> 00:01:08,200
na pilha, ea maneira que nós
remover a informação a partir da pilha.

25
00:01:08,200 --> 00:01:11,600
Em particular com as pilhas
a regra é apenas o mais

26
00:01:11,600 --> 00:01:15,830
recentemente elemento adicionado pode ser removido.

27
00:01:15,830 --> 00:01:17,660
>> Então, pense nisso como se fosse uma pilha.

28
00:01:17,660 --> 00:01:21,170
Nós estamos acumulando informações
em cima de si,

29
00:01:21,170 --> 00:01:24,271
e apenas a coisa no topo
da pilha pode ser removida.

30
00:01:24,271 --> 00:01:27,020
Não podemos remover a coisa por baixo
porque tudo o resto seria

31
00:01:27,020 --> 00:01:28,020
colapso e cair.

32
00:01:28,020 --> 00:01:32,580
Então, nós realmente estamos construindo uma pilha que
então, temos que remover pedaço por pedaço.

33
00:01:32,580 --> 00:01:36,590
Devido a isso, geralmente se referem
para uma pilha LIFO como uma estrutura,

34
00:01:36,590 --> 00:01:38,940
último a entrar, primeiro a sair.

35
00:01:38,940 --> 00:01:42,290
LIFO, último a entrar, primeiro a sair.

36
00:01:42,290 --> 00:01:45,635
>> Assim, devido a esta restrição
como a informação pode ser adicionada aos

37
00:01:45,635 --> 00:01:49,080
e removido a partir de uma pilha, não há realmente
apenas duas coisas que podemos fazer com uma pilha.

38
00:01:49,080 --> 00:01:52,010
Podemos empurrar, que é a
termo que usamos para adicionar

39
00:01:52,010 --> 00:01:55,130
um novo elemento ao topo do
pilha, a pilha ou se não existir

40
00:01:55,130 --> 00:01:58,550
e estamos a criar a partir do zero,
criar a pilha em primeiro lugar

41
00:01:58,550 --> 00:02:00,110
seria empurrar.

42
00:02:00,110 --> 00:02:04,990
E em seguida, pop, que é o tipo de CS
termo que usamos para remover o mais recentemente

43
00:02:04,990 --> 00:02:08,330
elemento adicionado a partir do topo da pilha.

44
00:02:08,330 --> 00:02:11,130
>> Então, vamos olhar para os dois
implementações, com base tanto matriz

45
00:02:11,130 --> 00:02:13,120
e lista ligada baseado.

46
00:02:13,120 --> 00:02:14,870
E nós estamos indo para
começar com matriz baseada.

47
00:02:14,870 --> 00:02:19,990
Então aqui está a idéia básica do que
a estrutura de dados pilha matriz baseada

48
00:02:19,990 --> 00:02:21,140
seria semelhante.

49
00:02:21,140 --> 00:02:23,740
Nós temos uma definição digitado aqui.

50
00:02:23,740 --> 00:02:27,790
Dentro de que temos dois membros
ou campos da estrutura.

51
00:02:27,790 --> 00:02:29,880
Nós temos uma matriz.

52
00:02:29,880 --> 00:02:32,400
E mais uma vez eu estou usando o
valor tipo de dados arbitrário.

53
00:02:32,400 --> 00:02:35,180
>> Portanto, este pode ser qualquer tipo de dados,
int char ou alguns outros dados

54
00:02:35,180 --> 00:02:37,080
o tipo que você criou anteriormente.

55
00:02:37,080 --> 00:02:39,861
Portanto, temos um conjunto de capacidade tamanho.

56
00:02:39,861 --> 00:02:44,010
Capacidade sendo uma libra constante definida,
talvez em outro lugar em nosso arquivo.

57
00:02:44,010 --> 00:02:47,550
Então, observe já com este particular
implementação estamos delimitadora

58
00:02:47,550 --> 00:02:49,800
nos como era tipicamente
o caso com matrizes,

59
00:02:49,800 --> 00:02:53,170
que não pode redimensionar dinamicamente,
onde há um certo número

60
00:02:53,170 --> 00:02:55,450
de elementos que máximo
podemos colocar em nossa pilha.

61
00:02:55,450 --> 00:02:57,930
Neste caso, é elementos de capacidade.

62
00:02:57,930 --> 00:03:00,310
>> Nós também manter o controle de
o topo da pilha.

63
00:03:00,310 --> 00:03:04,350
O elemento é o mais
recentemente adicionado à pilha?

64
00:03:04,350 --> 00:03:07,470
E, assim, manter o controle de que
em uma variável chamada superior.

65
00:03:07,470 --> 00:03:11,692
E tudo isso fica embrulhado em conjunto
para um novo tipo de dados chamado uma pilha.

66
00:03:11,692 --> 00:03:13,400
E uma vez que são criados
este novo tipo de dados

67
00:03:13,400 --> 00:03:15,410
podemos tratá-la como
qualquer outro tipo de dados.

68
00:03:15,410 --> 00:03:20,970
Podemos declarar pilha s, assim como
nós poderíamos fazer int x, y ou carvão.

69
00:03:20,970 --> 00:03:22,990
E quando dizemos empilhar
s, bem o que acontece

70
00:03:22,990 --> 00:03:26,420
é que obter um conjunto de
memória reservada para nós.

71
00:03:26,420 --> 00:03:28,770
>> Neste caso capacidade
Eu aparentemente decidiu

72
00:03:28,770 --> 00:03:33,470
10 é porque eu tenho um
única variável do tipo de pilha

73
00:03:33,470 --> 00:03:35,320
que contém dois campos recordar.

74
00:03:35,320 --> 00:03:38,330
Uma matriz, neste caso vai
para ser uma matriz de números inteiros

75
00:03:38,330 --> 00:03:40,440
como é o caso na maioria das minhas exemplos.

76
00:03:40,440 --> 00:03:43,996
E outra variável inteira
capaz de armazenar o topo,

77
00:03:43,996 --> 00:03:45,870
o adicionado mais recentemente
para o elemento de pilha.

78
00:03:45,870 --> 00:03:50,290
Assim, uma única pilha do que nós
só olha como esta definido.

79
00:03:50,290 --> 00:03:53,190
É uma caixa contendo
uma matriz de 10 o que

80
00:03:53,190 --> 00:03:57,280
serão inteiros, neste caso, e
outra variável inteira lá em verde

81
00:03:57,280 --> 00:04:00,010
para indicar a parte superior da pilha.

82
00:04:00,010 --> 00:04:02,600
>> Para definir a parte superior da
pilha nós apenas dizer s.top.

83
00:04:02,600 --> 00:04:04,890
Isso é como nós acessar um
campo de um recall estrutura.

84
00:04:04,890 --> 00:04:10,460
s.top é igual a 0 efectivamente
faz isso para a pilha.

85
00:04:10,460 --> 00:04:12,960
Então, novamente, temos duas operações
que pode realizar-se agora.

86
00:04:12,960 --> 00:04:14,270
Nós podemos empurrar e podemos pop.

87
00:04:14,270 --> 00:04:15,635
Vamos começar com empurrão.

88
00:04:15,635 --> 00:04:18,260
Mais uma vez, empurrando é a adição de um novo
elemento para o topo da pilha.

89
00:04:18,260 --> 00:04:21,460
>> Então, o que precisamos fazer em
essa matriz implementação baseada?

90
00:04:21,460 --> 00:04:23,210
Bem, em geral, a
função push vai

91
00:04:23,210 --> 00:04:26,160
a necessidade de aceitar um
ponteiro para a pilha.

92
00:04:26,160 --> 00:04:28,610
Agora pegue um segundo e pensar sobre isso.

93
00:04:28,610 --> 00:04:32,840
Por que iríamos querer a aceitar
um ponteiro para a pilha?

94
00:04:32,840 --> 00:04:36,830
Lembre-se de vídeos anteriores sobre
escopo de variáveis ​​e ponteiros,

95
00:04:36,830 --> 00:04:42,350
o que aconteceria se nós apenas enviado
pilha, s, em vez de como um parâmetro?

96
00:04:42,350 --> 00:04:45,770
O que seria realmente passou lá dentro?

97
00:04:45,770 --> 00:04:49,430
Lembre-se que estamos criando uma cópia
quando passá-lo para uma função

98
00:04:49,430 --> 00:04:51,160
a não ser que usar ponteiros.

99
00:04:51,160 --> 00:04:55,380
E assim esta função empurrar necessidades
para aceitar um ponteiro para a pilha

100
00:04:55,380 --> 00:04:59,160
de modo que nós estamos realmente mudando
a pilha pretendemos mudar.

101
00:04:59,160 --> 00:05:03,060
>> A outra coisa impulso provavelmente quer
aceitar é um elemento de dados de valor tipo.

102
00:05:03,060 --> 00:05:06,970
Neste caso, de novo, um número inteiro que
nós estamos indo para adicionar ao topo da pilha.

103
00:05:06,970 --> 00:05:08,680
Então, nós temos nossos dois parâmetros.

104
00:05:08,680 --> 00:05:11,310
O que é que vamos
agora fazer dentro de impulso?

105
00:05:11,310 --> 00:05:14,860
Bem, simplesmente, nós apenas estamos indo para adicionar
que o elemento de topo da pilha

106
00:05:14,860 --> 00:05:22,860
e, em seguida, alterar o local onde o topo
a pilha é, isso é ponto alto valor.

107
00:05:22,860 --> 00:05:25,639
Então é isso que uma função
declaração para push

108
00:05:25,639 --> 00:05:27,680
pode parecer em um
baseada em array implementação.

109
00:05:27,680 --> 00:05:30,967
>> Novamente, isto não é uma regra dura e rápida
que você pode mudar isso e ter

110
00:05:30,967 --> 00:05:32,050
que variam de formas diferentes.

111
00:05:32,050 --> 00:05:33,840
Talvez s é declarado globalmente.

112
00:05:33,840 --> 00:05:36,180
E para que você não precisa mesmo
para passá-lo é como um parâmetro.

113
00:05:36,180 --> 00:05:39,125
Esta é apenas uma outra vez
caso geral para push.

114
00:05:39,125 --> 00:05:41,000
E há diferentes
maneiras de implementá-lo.

115
00:05:41,000 --> 00:05:42,810
Mas, neste caso, o nosso
empurrão vai levar

116
00:05:42,810 --> 00:05:48,540
dois argumentos, um ponteiro para uma pilha e
um elemento de dados de valor tipo, número inteiro

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

118
00:05:49,840 --> 00:05:52,100
>> Por isso, declarou s, nós
disse s.top é igual a 0.

119
00:05:52,100 --> 00:05:55,969
Agora vamos empurrar o
número 28 na pilha.

120
00:05:55,969 --> 00:05:57,010
Bem, o que isso significa?

121
00:05:57,010 --> 00:05:59,600
Bem atualmente o
parte superior da pilha é 0.

122
00:05:59,600 --> 00:06:01,350
E então o que é basicamente
vai acontecer é

123
00:06:01,350 --> 00:06:05,820
nós estamos indo para furar o número
28 em array local 0.

124
00:06:05,820 --> 00:06:09,540
Bastante simples, certo, que
foi a top e agora nós somos bons de ir.

125
00:06:09,540 --> 00:06:12,910
E então temos de mudar o que
o topo da pilha será.

126
00:06:12,910 --> 00:06:15,130
De modo que a próxima vez
que empurra um elemento,

127
00:06:15,130 --> 00:06:18,017
nós estamos indo para armazená-lo em
localização matriz, provavelmente não 0.

128
00:06:18,017 --> 00:06:20,100
Nós não queremos substituir
o que acabamos de colocar lá.

129
00:06:20,100 --> 00:06:23,510
E por isso vamos mover a parte superior para 1.

130
00:06:23,510 --> 00:06:24,890
Isso provavelmente faz sentido.

131
00:06:24,890 --> 00:06:28,940
>> Agora, se queremos colocar outro elemento
na pilha, dizer que nós queremos empurrar 33,

132
00:06:28,940 --> 00:06:33,190
bem, agora nós estamos apenas vai levar 33
e colocá-lo em número de localização matriz

133
00:06:33,190 --> 00:06:37,580
1, e, em seguida, alterar o topo da nossa
empilhar para ser matriz número local dois.

134
00:06:37,580 --> 00:06:40,650
Então, se a próxima vez que quiser
empurrar um elemento na pilha,

135
00:06:40,650 --> 00:06:43,087
ele vai ser colocado no local da matriz 2.

136
00:06:43,087 --> 00:06:44,420
E vamos fazer isso mais uma vez.

137
00:06:44,420 --> 00:06:45,753
Vamos empurrar 19 fora das pilhas.

138
00:06:45,753 --> 00:06:48,940
Nós vamos colocar 19 em localização matriz 2
e altere o topo da nossa pilha

139
00:06:48,940 --> 00:06:51,220
para ser localização matriz 3
por isso, se a próxima vez nós

140
00:06:51,220 --> 00:06:54,780
precisa fazer um esforço que está pronto para ir.

141
00:06:54,780 --> 00:06:56,980
>> OK, de modo que levando em poucas palavras.

142
00:06:56,980 --> 00:06:57,830
O que sobre o estalo?

143
00:06:57,830 --> 00:07:00,240
Então popping é o tipo de
contrapartida para empurrar.

144
00:07:00,240 --> 00:07:02,720
É assim que remover os dados da pilha.

145
00:07:02,720 --> 00:07:04,610
E em necessidades pop gerais
para fazer o seguinte.

146
00:07:04,610 --> 00:07:07,600
É necessário aceitar um ponteiro para o
Pilha, de novo, no caso geral.

147
00:07:07,600 --> 00:07:10,480
Em algum outro caso, você pode
ter declarado a pilha globalmente,

148
00:07:10,480 --> 00:07:13,910
caso em que você não precisa passá-lo
no sistema porque ele já tem acesso a ele

149
00:07:13,910 --> 00:07:15,541
como uma variável global.

150
00:07:15,541 --> 00:07:17,040
Mas então o que mais fazer o que precisamos fazer?

151
00:07:17,040 --> 00:07:21,000
Bem, fomos incrementando
o topo da pilha no impulso,

152
00:07:21,000 --> 00:07:24,050
assim que nós estamos provavelmente vai querer
para diminuir o topo da pilha

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

154
00:07:25,009 --> 00:07:26,800
E depois, claro
nós estamos também vai querer

155
00:07:26,800 --> 00:07:29,240
para retornar o valor que nós remover.

156
00:07:29,240 --> 00:07:32,125
Se estamos adicionando elementos, queremos
para obter elementos para fora mais tarde,

157
00:07:32,125 --> 00:07:34,000
nós provavelmente verdade
deseja armazená-los por isso,

158
00:07:34,000 --> 00:07:36,490
não apenas excluí-los do
empilhar e depois não fazer nada com eles.

159
00:07:36,490 --> 00:07:38,500
Geralmente, se nós somos
empurrando e estalando aqui

160
00:07:38,500 --> 00:07:41,250
queremos armazenar este
informações de uma forma significativa

161
00:07:41,250 --> 00:07:43,250
e por isso não faz
sentido apenas descartá-lo.

162
00:07:43,250 --> 00:07:46,380
Assim, esta função deve
provavelmente retornar um valor para nós.

163
00:07:46,380 --> 00:07:51,040
>> Então é isso que uma declaração de pop
pode parecer que há na parte superior esquerda.

164
00:07:51,040 --> 00:07:53,870
Esta função retorna
dados de valor tipo.

165
00:07:53,870 --> 00:07:56,320
Mais uma vez nós estivemos usando
inteiros todo.

166
00:07:56,320 --> 00:08:01,916
E aceita um ponteiro para uma pilha como
seu único argumento ou parâmetro único.

167
00:08:01,916 --> 00:08:03,040
Então, o que é pop vai fazer?

168
00:08:03,040 --> 00:08:07,990
Vamos dizer que nós queremos agora
pop um elemento fora de s.

169
00:08:07,990 --> 00:08:14,000
Então lembre-se, eu disse que pilhas são passado
in, first out, estruturas de dados LIFO.

170
00:08:14,000 --> 00:08:17,855
Qual elemento está indo
ser removido da pilha?

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

172
00:08:21,780 --> 00:08:24,150
Será que você adivinha 19?

173
00:08:24,150 --> 00:08:25,290
Porque você estaria certo.

174
00:08:25,290 --> 00:08:28,836
19 foi o último elemento que adicionado ao
empilhar quando estávamos empurrando elementos em,

175
00:08:28,836 --> 00:08:31,210
e por isso vai para o primeiro
elemento que é removido.

176
00:08:31,210 --> 00:08:34,780
É como se disséssemos 28, e
então vamos colocar 33 em cima dela,

177
00:08:34,780 --> 00:08:36,659
e nós colocamos 19 em cima disso.

178
00:08:36,659 --> 00:08:40,650
O único elemento que podemos tirar é de 19.

179
00:08:40,650 --> 00:08:45,019
>> Agora no diagrama aqui o que eu fiz
é uma espécie de deletada 19 a partir da matriz.

180
00:08:45,019 --> 00:08:46,810
Isso não é verdade,
o que vamos fazer.

181
00:08:46,810 --> 00:08:48,934
Nós apenas estamos indo para tipo
de fingir que não está lá.

182
00:08:48,934 --> 00:08:51,441
Ele ainda está lá em
que a localização de memória,

183
00:08:51,441 --> 00:08:54,190
mas nós apenas estamos indo para ignorá-lo
alterando o topo da pilha nosso

184
00:08:54,190 --> 00:08:56,080
sendo de 3 para 2.

185
00:08:56,080 --> 00:08:58,720
Então, se nós estávamos a empurrar agora
outro elemento na pilha,

186
00:08:58,720 --> 00:09:00,720
que iria sobre escrever 19.

187
00:09:00,720 --> 00:09:03,990
>> Mas não vamos passar pela dificuldade
exclusão de 19 a partir da pilha.

188
00:09:03,990 --> 00:09:05,830
Nós podemos apenas fingir que não está lá.

189
00:09:05,830 --> 00:09:11,107
Para fins da pilha é ido se
mudarmos a top para ser 2 em vez de 3.

190
00:09:11,107 --> 00:09:12,690
Tudo bem, então isso foi muito bonito isso.

191
00:09:12,690 --> 00:09:15,080
Isso é tudo o que precisamos fazer
a pop um elemento fora.

192
00:09:15,080 --> 00:09:16,090
Vamos fazer de novo.

193
00:09:16,090 --> 00:09:18,610
Então, eu tenho realçado em vermelho aqui para
indicam que estamos a fazer outra chamada.

194
00:09:18,610 --> 00:09:19,720
Nós vamos fazer a mesma coisa.

195
00:09:19,720 --> 00:09:20,803
>> Então, o que vai acontecer?

196
00:09:20,803 --> 00:09:23,670
Bem, nós estamos indo para armazenar
33 em x e vamos

197
00:09:23,670 --> 00:09:26,217
para alterar o topo da pilha para 1.

198
00:09:26,217 --> 00:09:29,050
Assim que, se fôssemos agora a empurrar um
elemento na pilha que nós somos

199
00:09:29,050 --> 00:09:31,610
vai fazer agora,
o que vai acontecer

200
00:09:31,610 --> 00:09:36,367
é que vamos sobrescrever
matriz número de localização 1.

201
00:09:36,367 --> 00:09:38,950
Assim que 33 que era uma espécie de esquerda
atrás de que nós apenas fingiu

202
00:09:38,950 --> 00:09:44,390
não está mais lá, nós apenas estamos indo
a espancar-lo e colocar lá em vez de 40.

203
00:09:44,390 --> 00:09:46,290
E depois, claro,
desde que fizemos um empurrão,

204
00:09:46,290 --> 00:09:48,780
vamos incrementar o
topo da pilha a partir de 1 para 2

205
00:09:48,780 --> 00:09:50,950
de modo que se acrescentam-se agora
outro elemento que vai

206
00:09:50,950 --> 00:09:54,700
entrar em matriz número local dois.

207
00:09:54,700 --> 00:09:57,590
>> Agora listas ligadas são outro
forma de implementar pilhas.

208
00:09:57,590 --> 00:10:01,210
E, se esta definição no
tela aqui parece familiar para você,

209
00:10:01,210 --> 00:10:04,260
é porque parece quase
exactamente a mesma, na verdade,

210
00:10:04,260 --> 00:10:07,790
ele praticamente é exatamente o
mesmo como uma lista vinculada isoladamente,

211
00:10:07,790 --> 00:10:11,990
se você se lembra de nossa discussão sobre
listas individualmente ligados no outro vídeo.

212
00:10:11,990 --> 00:10:15,510
A única restrição aqui
é para nós como programadores,

213
00:10:15,510 --> 00:10:17,900
nós não estamos autorizados a
inserir ou excluir aleatoriamente

214
00:10:17,900 --> 00:10:20,620
da lista vinculada isoladamente
que anteriormente podiam fazer.

215
00:10:20,620 --> 00:10:25,820
Nós agora só pode inserir e excluir da
da frente ou a parte superior do ligada

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

217
00:10:26,320 --> 00:10:28,028
Isso é realmente a única
diferença embora.

218
00:10:28,028 --> 00:10:29,700
Esta é outra forma de uma lista vinculada isoladamente.

219
00:10:29,700 --> 00:10:32,060
É só a restrição
substituindo em nós mesmos

220
00:10:32,060 --> 00:10:35,770
como programadores que
muda-lo em uma pilha.

221
00:10:35,770 --> 00:10:39,280
>> A regra aqui é manter sempre uma
Ponteiro para a cabeça de uma lista ligada.

222
00:10:39,280 --> 00:10:41,520
Este é, naturalmente, um geral
regra importante em primeiro lugar.

223
00:10:41,520 --> 00:10:44,260
Para isoladamente lista ligada de qualquer maneira
só precisa de um ponteiro para a cabeça

224
00:10:44,260 --> 00:10:46,160
de modo a que têm
cadeia de ser capaz de encaminhá

225
00:10:46,160 --> 00:10:48,596
para todos os outros elementos
na lista vinculada.

226
00:10:48,596 --> 00:10:50,470
Mas é particularmente
importante com uma pilha.

227
00:10:50,470 --> 00:10:52,386
E de modo geral, você é
vai realmente querem

228
00:10:52,386 --> 00:10:54,090
este ponteiro para ser uma variável global.

229
00:10:54,090 --> 00:10:56,574
Ele provavelmente vai
ser ainda mais fácil dessa maneira.

230
00:10:56,574 --> 00:10:58,240
Então, quais são os análogos de push e pop?

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

232
00:10:58,740 --> 00:11:01,812
Então, empurrando de novo é a adição de
um elemento novo para a pilha.

233
00:11:01,812 --> 00:11:03,770
Em uma lista vinculada que
significa que nós vamos ter

234
00:11:03,770 --> 00:11:07,770
para criar um novo nó que nós somos
vai adicionar na lista ligada,

235
00:11:07,770 --> 00:11:10,500
e, em seguida, siga os passos cuidadosos
que temos delineado anteriormente

236
00:11:10,500 --> 00:11:16,050
em listas individualmente ligados ao adicioná-lo à
a cadeia sem quebrar a cadeia

237
00:11:16,050 --> 00:11:18,900
e perder ou orfandade qualquer
elementos da lista ligada.

238
00:11:18,900 --> 00:11:21,820
E isso é basicamente o que isso
pouco blob de texto lá resume.

239
00:11:21,820 --> 00:11:23,740
E vamos dar uma olhada
para ele como um diagrama.

240
00:11:23,740 --> 00:11:24,823
>> Então aqui está a nossa lista ligada.

241
00:11:24,823 --> 00:11:26,620
Ele contém quatro elementos simultaneamente.

242
00:11:26,620 --> 00:11:30,420
E mais perfeitamente aqui está a nossa
empilhar contendo quatro elementos.

243
00:11:30,420 --> 00:11:36,030
E digamos que queremos agora
empurrar um novo item para esta pilha.

244
00:11:36,030 --> 00:11:39,792
E eu quero empurrar um novo
item cujo valor de dados é de 12.

245
00:11:39,792 --> 00:11:41,000
Bem, o que vamos fazer?

246
00:11:41,000 --> 00:11:43,420
Bem, primeiro vamos
espaço malloc, dinamicamente

247
00:11:43,420 --> 00:11:45,411
alocar espaço para um novo nó.

248
00:11:45,411 --> 00:11:48,160
E, claro, imediatamente após
fazemos uma chamada para malloc sempre

249
00:11:48,160 --> 00:11:52,989
certifique-se de verificar para null,
porque se nós ficássemos nula de volta

250
00:11:52,989 --> 00:11:54,280
houve algum tipo de problema.

251
00:11:54,280 --> 00:11:57,570
Nós não queremos excluir a referência que nulo
ponteiro ou você vai sofrer uma falha seg.

252
00:11:57,570 --> 00:11:58,510
Isso não é bom.

253
00:11:58,510 --> 00:11:59,760
Então, nós temos malloced do nó.

254
00:11:59,760 --> 00:12:01,260
Vamos assumir que tivemos sucesso aqui.

255
00:12:01,260 --> 00:12:06,090
Nós vamos colocar 12 em
o campo de dados desse nó.

256
00:12:06,090 --> 00:12:11,570
Agora você se lembra qual dos nossos ponteiros
move seguinte portanto, não quebrar a cadeia?

257
00:12:11,570 --> 00:12:15,100
Nós temos um par de opções aqui, mas
o único que vai ser seguro

258
00:12:15,100 --> 00:12:19,330
é definir notícia próximo ponteiro para
aponte para o antigo chefe da lista

259
00:12:19,330 --> 00:12:21,360
ou o que em breve será o
antigo cabeça da lista.

260
00:12:21,360 --> 00:12:23,610
E agora que todo o nosso
elementos são encadeados,

261
00:12:23,610 --> 00:12:27,370
podemos lista apenas mover para apontar
para o mesmo lugar que faz novo.

262
00:12:27,370 --> 00:12:33,550
E nós temos agora efetivamente empurrou um
novo elemento para a frente da pilha.

263
00:12:33,550 --> 00:12:36,420
>> Para pop nós só queremos
excluir esse primeiro elemento.

264
00:12:36,420 --> 00:12:38,150
E assim, basicamente o que
nós temos que fazer aqui,

265
00:12:38,150 --> 00:12:40,050
bem temos de encontrar o segundo elemento.

266
00:12:40,050 --> 00:12:43,540
Eventualmente, que se tornará o novo
cabeça depois de excluir o primeiro.

267
00:12:43,540 --> 00:12:47,300
Então, só precisamos começar a partir de
o início, mova um para a frente.

268
00:12:47,300 --> 00:12:50,340
Uma vez que temos um porão em um
para a frente de onde estamos atualmente

269
00:12:50,340 --> 00:12:53,850
somos nós pode excluir a primeira com segurança
e então podemos simplesmente mover a cabeça

270
00:12:53,850 --> 00:12:57,150
para apontar para o que era o
segundo mandato e, em seguida, agora

271
00:12:57,150 --> 00:12:59,170
é a primeira que depois
nó foi excluído.

272
00:12:59,170 --> 00:13:01,160
>> Então, novamente, dando uma olhada
para ele como um diagrama de nós

273
00:13:01,160 --> 00:13:05,022
quer agora um pop
elemento fora desta pilha.

274
00:13:05,022 --> 00:13:05,730
Então, o que fazemos?

275
00:13:05,730 --> 00:13:08,188
Bem, vamos primeiro a criar
um novo ponteiro que está acontecendo

276
00:13:08,188 --> 00:13:10,940
para apontar para o mesmo local como a cabeça.

277
00:13:10,940 --> 00:13:13,790
Nós estamos indo para movê-lo uma posição
para a frente dizendo iguais trav

278
00:13:13,790 --> 00:13:17,510
trav próxima, por exemplo, que
avançaria a um ponteiro trav

279
00:13:17,510 --> 00:13:19,324
posição para a frente.

280
00:13:19,324 --> 00:13:21,240
Agora que temos um
segurar o primeiro elemento

281
00:13:21,240 --> 00:13:24,573
através da lista ponteiro chamado, ea
segundo elemento por meio de um chamado ponteiro

282
00:13:24,573 --> 00:13:28,692
trav, podemos excluir com segurança que
primeiro elemento a partir da pilha

283
00:13:28,692 --> 00:13:30,650
sem perder o resto
da cadeia porque

284
00:13:30,650 --> 00:13:32,358
tem uma maneira de se referir
para o segundo elemento

285
00:13:32,358 --> 00:13:34,780
transmitir através do
ponteiro chamado trav.

286
00:13:34,780 --> 00:13:37,100
>> Então agora podemos liberar esse nó.

287
00:13:37,100 --> 00:13:38,404
Podemos libertar lista.

288
00:13:38,404 --> 00:13:41,320
E então tudo o que precisamos fazer agora é
lista mover para apontar para o mesmo lugar

289
00:13:41,320 --> 00:13:44,482
trav que faz, e nós somos tipo de volta
onde começamos antes que empurrou 12

290
00:13:44,482 --> 00:13:45,690
sobre, em primeiro lugar, à direita.

291
00:13:45,690 --> 00:13:46,940
Este é exatamente onde estávamos.

292
00:13:46,940 --> 00:13:48,840
Nós tivemos essa pilha de quatro elementos.

293
00:13:48,840 --> 00:13:49,690
Nós adicionamos um quinto.

294
00:13:49,690 --> 00:13:51,910
Nós empurramos um quinto
elemento, e então nós

295
00:13:51,910 --> 00:13:55,980
estalou que, mais recentemente,
elemento adicionado de volta ao largo.

296
00:13:55,980 --> 00:13:58,816
>> Isso é realmente muito bonito
tudo o que há para pilhas.

297
00:13:58,816 --> 00:14:00,190
Você pode implementá-las como matrizes.

298
00:14:00,190 --> 00:14:01,815
Você pode implementá-las como listas ligadas.

299
00:14:01,815 --> 00:14:04,810
Existem, naturalmente, outros
maneiras de implementá-las também.

300
00:14:04,810 --> 00:14:09,060
Basicamente, a razão nós usaríamos
pilhas é manter os dados, de tal maneira

301
00:14:09,060 --> 00:14:12,090
o que mais recentemente acrescentado
elemento é a primeira coisa que nós somos

302
00:14:12,090 --> 00:14:14,980
vai querer voltar.

303
00:14:14,980 --> 00:14:17,900
Eu sou Doug Lloyd, este é CS50.

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