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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Très bien,
donc par ce point vous êtes

3
00:00:05,990 --> 00:00:09,020
probablement assez familier
avec les tableaux et les listes chaînées

4
00:00:09,020 --> 00:00:10,950
qui est les deux primaire
structures de données que nous avons

5
00:00:10,950 --> 00:00:16,810
parlé pour garder ensembles de
des données de types de données similaires organisé.

6
00:00:16,810 --> 00:00:19,080
>> Maintenant, nous allons parler
sur un couple de variations

7
00:00:19,080 --> 00:00:20,330
sur des tableaux et listes liées.

8
00:00:20,330 --> 00:00:22,362
Dans cette vidéo, nous allons
pour parler de piles.

9
00:00:22,362 --> 00:00:25,320
Plus précisément, nous allons parler
sur une structure de données appelée une pile.

10
00:00:25,320 --> 00:00:28,510
Rappel des discussions précédentes
et des pointeurs sur la mémoire,

11
00:00:28,510 --> 00:00:32,060
que la pile est également le
nommer pour un segment de mémoire

12
00:00:32,060 --> 00:00:34,980
où statiquement déclarée
memory-- mémoire que vous

13
00:00:34,980 --> 00:00:38,730
nommer, les variables que vous nommez, et
cetera et de fonction des cadres que nous avons aussi

14
00:00:38,730 --> 00:00:41,000
cadres de pile d'appel existent.

15
00:00:41,000 --> 00:00:45,421
Donc, ceci est une structure de données en pile
pas un segment de pile de mémoire.

16
00:00:45,421 --> 00:00:45,920
D'ACCORD.

17
00:00:45,920 --> 00:00:46,890
>> Mais qu'est-ce qu'une pile?

18
00:00:46,890 --> 00:00:49,220
Donc, il est à peu près juste un
type spécial de la structure

19
00:00:49,220 --> 00:00:51,190
qui maintient les données d'une manière organisée.

20
00:00:51,190 --> 00:00:53,760
Et il ya deux très
des moyens communs à mettre en œuvre

21
00:00:53,760 --> 00:00:57,380
empilements utilisant deux structures de données
que nous sommes déjà familiers avec,

22
00:00:57,380 --> 00:01:00,340
les tableaux et les listes chaînées.

23
00:01:00,340 --> 00:01:04,430
Ce qui rend une spéciale de la pile est le
façon dont nous mettons l'information

24
00:01:04,430 --> 00:01:08,200
dans la pile, et la façon dont nous
supprimer des informations de la pile.

25
00:01:08,200 --> 00:01:11,600
En particulier avec des piles
la règle est que le plus

26
00:01:11,600 --> 00:01:15,830
récemment élément supplémentaire peut être retirée.

27
00:01:15,830 --> 00:01:17,660
>> Alors, pensez à ce sujet que si elle est une pile.

28
00:01:17,660 --> 00:01:21,170
Nous empiler informations
au-dessus de lui-même,

29
00:01:21,170 --> 00:01:24,271
et seulement la chose au sommet
de la pile peut être retiré.

30
00:01:24,271 --> 00:01:27,020
Nous ne pouvons pas retirer la chose sous
parce que tout le reste

31
00:01:27,020 --> 00:01:28,020
effondrer et tomber.

32
00:01:28,020 --> 00:01:32,580
Alors, vraiment, nous construisons une pile
il nous faut alors retirer morceau par morceau.

33
00:01:32,580 --> 00:01:36,590
Parce que de ce que nous appelons communément
pour une pile comme une structure LIFO,

34
00:01:36,590 --> 00:01:38,940
dernier entré, premier sorti.

35
00:01:38,940 --> 00:01:42,290
LIFO, dernier entré, premier sorti.

36
00:01:42,290 --> 00:01:45,635
>> Donc à cause de cette restriction sur
façon dont l'information peut être ajouté à

37
00:01:45,635 --> 00:01:49,080
et retiré d'une pile, il n'y a vraiment
seulement deux choses que nous pouvons faire avec une pile.

38
00:01:49,080 --> 00:01:52,010
Nous pouvons pousser, qui est la
terme que nous utilisons pour ajouter

39
00:01:52,010 --> 00:01:55,130
un nouvel élément à la partie supérieure de la
pile, ou si existe pas la pile

40
00:01:55,130 --> 00:01:58,550
et nous créons à partir de zéro,
la création de la pile en premier lieu

41
00:01:58,550 --> 00:02:00,110
serait pousser.

42
00:02:00,110 --> 00:02:04,990
Et puis pop, qui est le genre de CS
terme que nous utilisons pour enlever le plus récemment

43
00:02:04,990 --> 00:02:08,330
l'élément rapporté de sommet de la pile.

44
00:02:08,330 --> 00:02:11,130
>> Donc, nous allons examiner à la fois
implémentations, basée à la fois tableau

45
00:02:11,130 --> 00:02:13,120
et la liste de liens fondés.

46
00:02:13,120 --> 00:02:14,870
Et nous allons
commencer avec tableau de base.

47
00:02:14,870 --> 00:02:19,990
Alors, voici l'idée de base de ce
la structure de données de matrice à base de pile

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

49
00:02:21,140 --> 00:02:23,740
Nous avons une définition dactylographiée ici.

50
00:02:23,740 --> 00:02:27,790
A l'intérieur de ce que nous avons deux membres
ou les champs de la structure.

51
00:02:27,790 --> 00:02:29,880
Nous avons un tableau.

52
00:02:29,880 --> 00:02:32,400
Et encore, je suis en utilisant le
arbitraire valeur de type de données.

53
00:02:32,400 --> 00:02:35,180
>> Donc, cela pourrait être n'importe quel type de données,
int char ou d'autres données

54
00:02:35,180 --> 00:02:37,080
tapez vous avez précédemment créé.

55
00:02:37,080 --> 00:02:39,861
Donc, nous avons une gamme de capacité de taille.

56
00:02:39,861 --> 00:02:44,010
Capacité étant une livre défini constant,
peut-être quelque part ailleurs dans notre fichier.

57
00:02:44,010 --> 00:02:47,550
Donc, déjà remarqué avec ce particulier
la mise en œuvre nous EXpLoRATIoN

58
00:02:47,550 --> 00:02:49,800
nous comme ce fut généralement
le cas des tableaux,

59
00:02:49,800 --> 00:02:53,170
que nous ne pouvons pas redimensionner dynamiquement,
où il ya un certain nombre

60
00:02:53,170 --> 00:02:55,450
d'éléments maximum
nous pouvons mettre dans notre pile.

61
00:02:55,450 --> 00:02:57,930
Dans ce cas, il est des éléments de capacité.

62
00:02:57,930 --> 00:03:00,310
>> Nous conservons également
le sommet de la pile.

63
00:03:00,310 --> 00:03:04,350
Quel élément est le plus
récemment ajoutés à la pile?

64
00:03:04,350 --> 00:03:07,470
Et si nous gardons une trace de ce que
en haut d'une variable appelée.

65
00:03:07,470 --> 00:03:11,692
Et tout cela est enveloppé tous ensemble
dans un nouveau type de données appelée une pile.

66
00:03:11,692 --> 00:03:13,400
Et une fois que nous sommes créés
ce nouveau type de données

67
00:03:13,400 --> 00:03:15,410
nous pouvons traiter comme
tout autre type de données.

68
00:03:15,410 --> 00:03:20,970
Nous pouvons déclarer pile s, tout comme
nous pourrions faire int x, y ou char.

69
00:03:20,970 --> 00:03:22,990
Et quand nous disons empilons
s, bien ce qui se passe

70
00:03:22,990 --> 00:03:26,420
est nous obtenons un ensemble de
mémoire mis de côté pour nous.

71
00:03:26,420 --> 00:03:28,770
>> Dans ce cas, la capacité de
Je suis apparemment décidé

72
00:03:28,770 --> 00:03:33,470
est 10 parce que je ai un
seule variable du type de pile

73
00:03:33,470 --> 00:03:35,320
qui contient deux champs rappellent.

74
00:03:35,320 --> 00:03:38,330
Un tableau, dans ce cas va
être un tableau d'entiers

75
00:03:38,330 --> 00:03:40,440
comme est le cas dans la plupart de mes exemples.

76
00:03:40,440 --> 00:03:43,996
Et une autre variable entière
capable de stocker le haut,

77
00:03:43,996 --> 00:03:45,870
le plus récemment ajouté
élément de la pile.

78
00:03:45,870 --> 00:03:50,290
Donc, une seule pile de ce que nous
vient d'être défini ressemble à ceci.

79
00:03:50,290 --> 00:03:53,190
Il est une boîte contenant
un tableau de ce que 10

80
00:03:53,190 --> 00:03:57,280
sera entiers dans cette affaire et
une autre variable entière y en vert

81
00:03:57,280 --> 00:04:00,010
pour indiquer le haut de la pile.

82
00:04:00,010 --> 00:04:02,600
>> Pour définir le haut de la
pile, nous disons simplement s.top.

83
00:04:02,600 --> 00:04:04,890
Voilà comment nous accédons à un
champ d'un rappel de la structure.

84
00:04:04,890 --> 00:04:10,460
s.top est égal à 0 efficacement
ce que cela à notre pile.

85
00:04:10,460 --> 00:04:12,960
Encore une fois, nous avons deux opérations
que nous pouvons effectuer maintenant.

86
00:04:12,960 --> 00:04:14,270
Nous pouvons pousser et nous pouvons pop.

87
00:04:14,270 --> 00:04:15,635
Commençons par poussoir.

88
00:04:15,635 --> 00:04:18,260
Encore une fois, poussant est l'ajout d'un nouveau
élément en haut de la pile.

89
00:04:18,260 --> 00:04:21,460
>> Alors, que devons-nous faire dans
cette matrice de mise en œuvre sur la base?

90
00:04:21,460 --> 00:04:23,210
Eh bien, en général
fonction Push va

91
00:04:23,210 --> 00:04:26,160
avoir besoin d'accepter une
pointeur vers la pile.

92
00:04:26,160 --> 00:04:28,610
Maintenant, prenez une seconde pour y penser.

93
00:04:28,610 --> 00:04:32,840
Pourquoi voudrions-nous à accepter
un pointeur sur la pile?

94
00:04:32,840 --> 00:04:36,830
Rappel de vidéos précédentes sur
la portée des variables et des pointeurs,

95
00:04:36,830 --> 00:04:42,350
ce qui arriverait si nous venons d'envoyer
pile, s plutôt comme un paramètre?

96
00:04:42,350 --> 00:04:45,770
Quel serait réellement passé là-bas?

97
00:04:45,770 --> 00:04:49,430
Rappelez-vous que nous créons une copie
quand nous passons à une fonction

98
00:04:49,430 --> 00:04:51,160
à moins que nous utilisons des pointeurs.

99
00:04:51,160 --> 00:04:55,380
Et si cette fonction pousser besoins
à accepter un pointeur de la pile

100
00:04:55,380 --> 00:04:59,160
de sorte que nous sommes en train de changer
la pile nous avons l'intention de changer.

101
00:04:59,160 --> 00:05:03,060
>> L'autre chose poussoir veut probablement
accepter est un élément de données d'une valeur de type.

102
00:05:03,060 --> 00:05:06,970
Dans ce cas, à nouveau, un nombre entier qui
nous allons ajouter à la haut de la pile.

103
00:05:06,970 --> 00:05:08,680
Donc, nous avons nos deux paramètres.

104
00:05:08,680 --> 00:05:11,310
Qu'allons-nous à
maintenant faire à l'intérieur de la poussée?

105
00:05:11,310 --> 00:05:14,860
Eh bien, tout simplement, nous allons juste ajouter
cet élément au sommet de la pile

106
00:05:14,860 --> 00:05:22,860
puis changer l'endroit où le haut de
la pile est, que l'art dot valeur supérieure.

107
00:05:22,860 --> 00:05:25,639
Voilà donc ce que une fonction
déclaration de poussoir

108
00:05:25,639 --> 00:05:27,680
pourrait ressembler dans un
basée sur la baie de mise en œuvre.

109
00:05:27,680 --> 00:05:30,967
>> Encore une fois cette est pas une règle dure et rapide
que vous pouviez changer cela et avoir

110
00:05:30,967 --> 00:05:32,050
elle varie de différentes façons.

111
00:05:32,050 --> 00:05:33,840
Peut-être s est déclaré globalement.

112
00:05:33,840 --> 00:05:36,180
Et si vous ne même pas besoin
pour passer, il est comme un paramètre.

113
00:05:36,180 --> 00:05:39,125
Ceci est encore juste un
cas général pour pousser.

114
00:05:39,125 --> 00:05:41,000
Et il ya différents
les moyens de la mettre en œuvre.

115
00:05:41,000 --> 00:05:42,810
Mais dans ce cas, notre
poussoir va prendre

116
00:05:42,810 --> 00:05:48,540
deux arguments, un pointeur vers une pile et
un élément de données de valeur de type, nombre entier

117
00:05:48,540 --> 00:05:49,840
dans ce cas.

118
00:05:49,840 --> 00:05:52,100
>> Donc, nous avons déclaré s, nous
ledit s.top est égal à 0.

119
00:05:52,100 --> 00:05:55,969
Maintenant, nous allons pousser le
Numéro 28 sur la pile.

120
00:05:55,969 --> 00:05:57,010
Eh bien, qu'est-ce que cela signifie?

121
00:05:57,010 --> 00:05:59,600
Bien actuellement la
sommet de la pile est 0.

122
00:05:59,600 --> 00:06:01,350
Et donc ce qui est essentiellement
qui va se passer est

123
00:06:01,350 --> 00:06:05,820
nous allons nous en tenir le nombre
28 dans l'emplacement de tableau 0.

124
00:06:05,820 --> 00:06:09,540
Assez simple, droite, que
a été le meilleur et maintenant nous sommes bon pour aller.

125
00:06:09,540 --> 00:06:12,910
Et puis, nous avons besoin de changer ce que
le haut de la pile sera.

126
00:06:12,910 --> 00:06:15,130
Alors que la prochaine fois
nous poussons un élément,

127
00:06:15,130 --> 00:06:18,017
nous allons stocker dans
Lieu de tableau, probablement pas 0.

128
00:06:18,017 --> 00:06:20,100
Nous ne voulons pas écraser
ce que nous venons de mettre là.

129
00:06:20,100 --> 00:06:23,510
Et donc nous allons simplement déplacer l'extrémité supérieure à 1.

130
00:06:23,510 --> 00:06:24,890
Cela fait sans doute logique.

131
00:06:24,890 --> 00:06:28,940
>> Maintenant, si nous voulons mettre un autre élément
sur la pile, disons que nous voulons pousser 33,

132
00:06:28,940 --> 00:06:33,190
Eh bien maintenant, nous allons juste prendre 33
et le mettre au tableau numéro d'emplacement

133
00:06:33,190 --> 00:06:37,580
1, puis modifiez le haut de notre
empiler être éventail emplacement numéro deux.

134
00:06:37,580 --> 00:06:40,650
Donc, si la prochaine fois que nous voulons
pousser un élément sur la pile,

135
00:06:40,650 --> 00:06:43,087
il va être mis en réseau localité 2.

136
00:06:43,087 --> 00:06:44,420
Et nous allons faire ce que une fois de plus.

137
00:06:44,420 --> 00:06:45,753
Nous allons pousser 19 hors des piles.

138
00:06:45,753 --> 00:06:48,940
Nous allons mettre 19 dans le tableau localité 2
et changer le sommet de notre pile

139
00:06:48,940 --> 00:06:51,220
pour être l'emplacement du tableau 3
Donc, si nous la prochaine fois

140
00:06:51,220 --> 00:06:54,780
besoin de faire un effort, nous sommes bon pour aller.

141
00:06:54,780 --> 00:06:56,980
>> OK, alors que ça poussant en un mot.

142
00:06:56,980 --> 00:06:57,830
Qu'en est-il éclater?

143
00:06:57,830 --> 00:07:00,240
Donc popping est le genre de
contrepartie de pousser.

144
00:07:00,240 --> 00:07:02,720
Il est comment nous enlevons les données de la pile.

145
00:07:02,720 --> 00:07:04,610
Et dans les besoins généraux de la pop
faire ce qui suit.

146
00:07:04,610 --> 00:07:07,600
Il doit accepter un pointeur sur la
empiler, à nouveau dans le cas général.

147
00:07:07,600 --> 00:07:10,480
Dans certains autres cas, vous pourriez
ont déclaré la pile à l'échelle mondiale,

148
00:07:10,480 --> 00:07:13,910
dans ce cas vous ne devez pas passer
car il en a déjà accès à ce

149
00:07:13,910 --> 00:07:15,541
en tant que variable globale.

150
00:07:15,541 --> 00:07:17,040
Mais alors quoi d'autre avons-nous besoin de le faire?

151
00:07:17,040 --> 00:07:21,000
Eh bien, nous étions incrémentation
le haut de la pile en push,

152
00:07:21,000 --> 00:07:24,050
donc nous allons probablement vouloir
pour décrémenter le sommet de la pile

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

154
00:07:25,009 --> 00:07:26,800
Et puis bien sûr
Nous allons aussi vouloir

155
00:07:26,800 --> 00:07:29,240
pour renvoyer la valeur que nous retirons.

156
00:07:29,240 --> 00:07:32,125
Si nous ajoutons des éléments, nous voulons
pour obtenir des éléments hors plus tard,

157
00:07:32,125 --> 00:07:34,000
nous avons probablement fait
envie de les stocker afin que nous

158
00:07:34,000 --> 00:07:36,490
ne vous contentez pas de les supprimer à partir de la
empiler et puis ne rien faire avec eux.

159
00:07:36,490 --> 00:07:38,500
En général, si nous sommes
pousser et popping ici

160
00:07:38,500 --> 00:07:41,250
nous voulons stocker cette
informations d'une manière significative

161
00:07:41,250 --> 00:07:43,250
et il ne fait pas
sens de simplement le jeter.

162
00:07:43,250 --> 00:07:46,380
Donc, cette fonction devrait
probablement retourner une valeur pour nous.

163
00:07:46,380 --> 00:07:51,040
>> Voilà donc ce que une déclaration pour la pop
il pourrait ressembler en haut à gauche.

164
00:07:51,040 --> 00:07:53,870
Cette fonction renvoie
les données de valeur de type.

165
00:07:53,870 --> 00:07:56,320
Encore une fois nous avons été en utilisant
tout au long de nombres entiers.

166
00:07:56,320 --> 00:08:01,916
Et il accepte un pointeur vers une pile comme
son seul argument ou un paramètre unique.

167
00:08:01,916 --> 00:08:03,040
Alors, quelle est la pop va faire?

168
00:08:03,040 --> 00:08:07,990
Disons que nous voulons maintenant
pop un élément hors de l'art.

169
00:08:07,990 --> 00:08:14,000
Donc me souviens que je disais que les piles sont dernière
In, First Out, LIFO structures de données.

170
00:08:14,000 --> 00:08:17,855
Quel élément va
être présente dans la pile?

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

172
00:08:21,780 --> 00:08:24,150
Avez-vous deviné 19?

173
00:08:24,150 --> 00:08:25,290
Parce que vous avez raison.

174
00:08:25,290 --> 00:08:28,836
19 était le dernier élément, nous avons ajouté à la
empiler quand nous poussions éléments sur,

175
00:08:28,836 --> 00:08:31,210
et donc ça va à la première
élément qui sera éliminé.

176
00:08:31,210 --> 00:08:34,780
Il est comme si nous disions 28, et
puis nous avons mis 33 sur le dessus de celui-ci,

177
00:08:34,780 --> 00:08:36,659
et nous avons mis 19 sur le dessus de cela.

178
00:08:36,659 --> 00:08:40,650
Le seul élément que nous pouvons décoller est de 19.

179
00:08:40,650 --> 00:08:45,019
>> Maintenant, dans le diagramme ici ce que je l'ai fait
est une sorte de supprimer 19 à partir du tableau.

180
00:08:45,019 --> 00:08:46,810
Cela ne veut pas réellement
ce que nous allons faire.

181
00:08:46,810 --> 00:08:48,934
Nous allons juste genre
de prétendre qu'il n'y est pas.

182
00:08:48,934 --> 00:08:51,441
Il est toujours là dans
cet emplacement de mémoire,

183
00:08:51,441 --> 00:08:54,190
mais nous allons juste l'ignorer
en changeant la tête de notre pile

184
00:08:54,190 --> 00:08:56,080
étant de 3 à 2.

185
00:08:56,080 --> 00:08:58,720
Donc, si nous étions à pousser maintenant
un autre élément dans la pile,

186
00:08:58,720 --> 00:09:00,720
il serait plus écrire 19.

187
00:09:00,720 --> 00:09:03,990
>> Mais ne soyons pas passer par la peine
de supprimer 19 de la pile.

188
00:09:03,990 --> 00:09:05,830
Nous pouvons simplement prétendre qu'il n'y est pas.

189
00:09:05,830 --> 00:09:11,107
Aux fins de la pile, il est parti si
nous changeons le haut pour être 2 au lieu de 3.

190
00:09:11,107 --> 00:09:12,690
Tout droit, ce qui était à peu près tout.

191
00:09:12,690 --> 00:09:15,080
Voilà tout ce que nous devons faire
à la pop un élément off.

192
00:09:15,080 --> 00:09:16,090
Faisons le encore.

193
00:09:16,090 --> 00:09:18,610
Donc, je l'ai souligné en rouge ici pour
indiquons que nous faisons un autre appel.

194
00:09:18,610 --> 00:09:19,720
Nous allons faire la même chose.

195
00:09:19,720 --> 00:09:20,803
>> Alors qu'est-ce qui va se passer?

196
00:09:20,803 --> 00:09:23,670
Eh bien, nous allons stocker
33 en x et nous allons

197
00:09:23,670 --> 00:09:26,217
pour changer le dessus de la pile à une.

198
00:09:26,217 --> 00:09:29,050
Alors que si nous devions maintenant pousser un
élément dans la pile qui nous sommes

199
00:09:29,050 --> 00:09:31,610
va faire maintenant,
ce qu'il va se passer

200
00:09:31,610 --> 00:09:36,367
est que nous allons écraser
tableau emplacement numéro 1.

201
00:09:36,367 --> 00:09:38,950
Alors que 33 qui a été laissé de tri
derrière que nous fait semblant

202
00:09:38,950 --> 00:09:44,390
n'y est plus, nous allons juste
à tabasser et de le mettre à la place il y 40.

203
00:09:44,390 --> 00:09:46,290
Et puis bien sûr,
depuis que nous avons fait une poussée,

204
00:09:46,290 --> 00:09:48,780
nous allons augmenter le
sommet de la pile 1-2

205
00:09:48,780 --> 00:09:50,950
de sorte que si nous ajoutons maintenant
un autre élément ça va

206
00:09:50,950 --> 00:09:54,700
aller dans un tableau emplacement numéro deux.

207
00:09:54,700 --> 00:09:57,590
>> Maintenant listes chaînées sont un autre
façon d'appliquer piles.

208
00:09:57,590 --> 00:10:01,210
Et si cette définition sur la
écran semble ici familier pour vous,

209
00:10:01,210 --> 00:10:04,260
il est parce qu'il ressemble presque
exactement la même, en fait,

210
00:10:04,260 --> 00:10:07,790
il est à peu près exactement le
même comme une liste chaînée,

211
00:10:07,790 --> 00:10:11,990
si vous vous souvenez de notre discussion
chaînée listes dans une autre vidéo.

212
00:10:11,990 --> 00:10:15,510
La seule restriction ici
est pour nous en tant que programmeurs,

213
00:10:15,510 --> 00:10:17,900
nous ne sommes pas autorisés à
insérer ou de supprimer de façon aléatoire

214
00:10:17,900 --> 00:10:20,620
de la liste chaînée
que nous pourrions le faire auparavant.

215
00:10:20,620 --> 00:10:25,820
Nous ne pouvons désormais insérer et supprimer de
l'avant ou le haut de l'lié

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

217
00:10:26,320 --> 00:10:28,028
Cela est vraiment la seule
différence cependant.

218
00:10:28,028 --> 00:10:29,700
Ceci est contraire une liste chaînée.

219
00:10:29,700 --> 00:10:32,060
Il est seulement la restriction
remplacement sur nous-mêmes

220
00:10:32,060 --> 00:10:35,770
comme les programmeurs qui
le change en une pile.

221
00:10:35,770 --> 00:10:39,280
>> La règle ici est de maintenir toujours un
pointeur vers la tête d'une liste chaînée.

222
00:10:39,280 --> 00:10:41,520
Ceci est bien sûr un général
règle importante en premier.

223
00:10:41,520 --> 00:10:44,260
Pour isolément liste liée de toute façon vous
seulement besoin d'un pointeur sur la tête

224
00:10:44,260 --> 00:10:46,160
afin d'obtenir que
chaîne pouvoir consulter

225
00:10:46,160 --> 00:10:48,596
à chaque autre élément
dans la liste chaînée.

226
00:10:48,596 --> 00:10:50,470
Mais il est particulièrement
importante avec une pile.

227
00:10:50,470 --> 00:10:52,386
Et si généralement vous êtes
allez vouloir réellement

228
00:10:52,386 --> 00:10:54,090
ce pointeur pour être une variable globale.

229
00:10:54,090 --> 00:10:56,574
Il va probablement
être encore plus facile de cette façon.

230
00:10:56,574 --> 00:10:58,240
Alors, quels sont les analogues de la poussée et de la pop?

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

232
00:10:58,740 --> 00:11:01,812
Donc, poussant à nouveau est d'ajouter
un nouvel élément à la pile.

233
00:11:01,812 --> 00:11:03,770
Dans une liste liée qui
signifie que nous allons devoir

234
00:11:03,770 --> 00:11:07,770
pour créer un nouveau nœud que nous sommes
aller à ajouter dans la liste chaînée,

235
00:11:07,770 --> 00:11:10,500
puis suivez les étapes minutieuses
que nous avons indiqué précédemment

236
00:11:10,500 --> 00:11:16,050
dans les listes simplement liés à l'ajouter à
la chaîne sans rupture de la chaîne

237
00:11:16,050 --> 00:11:18,900
et de perdre toute ou orphelins
éléments de la liste chaînée.

238
00:11:18,900 --> 00:11:21,820
Et qui est essentiellement ce que
petite goutte de texte, il résume.

239
00:11:21,820 --> 00:11:23,740
Et nous allons jeter un coup d'oeil
à elle comme un diagramme.

240
00:11:23,740 --> 00:11:24,823
>> Alors, voici notre liste chaînée.

241
00:11:24,823 --> 00:11:26,620
Il contient en même temps que quatre éléments.

242
00:11:26,620 --> 00:11:30,420
Et plus parfaitement voici notre
pile contenant quatre éléments.

243
00:11:30,420 --> 00:11:36,030
Et disons que nous voulons maintenant
pousser un nouvel élément sur cette pile.

244
00:11:36,030 --> 00:11:39,792
Et nous voulons pousser une nouvelle
l'article dont les données valeur est 12.

245
00:11:39,792 --> 00:11:41,000
Eh bien, qu'allons-nous faire?

246
00:11:41,000 --> 00:11:43,420
Eh bien d'abord, nous allons
espace de malloc, dynamiquement

247
00:11:43,420 --> 00:11:45,411
allouer de l'espace pour un nouveau noeud.

248
00:11:45,411 --> 00:11:48,160
Et bien sûr, immédiatement après
nous faisons un appel à nous malloc toujours

249
00:11:48,160 --> 00:11:52,989
assurez-vous de vérifier null,
parce que si nous sommes arrivés nulle retour

250
00:11:52,989 --> 00:11:54,280
il y avait une sorte de problème.

251
00:11:54,280 --> 00:11:57,570
Nous ne voulons pas de déréférencer que null
pointeur ou vous allez souffrir d'un défaut de seg.

252
00:11:57,570 --> 00:11:58,510
Ce n'est pas bien.

253
00:11:58,510 --> 00:11:59,760
Nous avons donc malloced du noeud.

254
00:11:59,760 --> 00:12:01,260
Nous allons supposer que nous avons eu du succès ici.

255
00:12:01,260 --> 00:12:06,090
Nous allons mettre 12 dans
le champ de données de ce noeud.

256
00:12:06,090 --> 00:12:11,570
Maintenant, vous rappelez-vous ce qui de nos pointeurs
émeut prochaine afin de ne pas briser la chaîne?

257
00:12:11,570 --> 00:12:15,100
Nous avons un couple d'options ici, mais
le seul qui va être sécuritaire

258
00:12:15,100 --> 00:12:19,330
est de mettre en nouvelles pointeur à côté de
Point à l'ancien chef de la liste

259
00:12:19,330 --> 00:12:21,360
ou ce sera bientôt le
vieille tête de la liste.

260
00:12:21,360 --> 00:12:23,610
Et maintenant que l'ensemble de notre
éléments sont enchaînés,

261
00:12:23,610 --> 00:12:27,370
nous pouvons simplement déplacer la liste à signaler
à la même place que la nouvelle fait.

262
00:12:27,370 --> 00:12:33,550
Et nous avons maintenant effectivement poussé un
nouvel élément sur la face avant de la pile.

263
00:12:33,550 --> 00:12:36,420
>> Pour nous pop veux juste
supprimer ce premier élément.

264
00:12:36,420 --> 00:12:38,150
Et donc en gros ce que
nous avons à faire ici,

265
00:12:38,150 --> 00:12:40,050
Eh bien, nous devons trouver le deuxième élément.

266
00:12:40,050 --> 00:12:43,540
Finalement, qui deviendra la nouvelle
tête après nous supprimons la première.

267
00:12:43,540 --> 00:12:47,300
Donc nous avons juste besoin de partir
le début, déplacer l'un vers l'avant.

268
00:12:47,300 --> 00:12:50,340
Une fois que nous avons une emprise sur un
avant de où nous actuellement

269
00:12:50,340 --> 00:12:53,850
sommes nous pouvons supprimer le premier en toute sécurité
et alors nous pouvons simplement déplacer la tête

270
00:12:53,850 --> 00:12:57,150
pour pointer vers ce qui était le
second mandat puis maintenant

271
00:12:57,150 --> 00:12:59,170
est le premier après que
nœud a été supprimé.

272
00:12:59,170 --> 00:13:01,160
>> Donc encore une fois, de prendre un coup d'oeil
cela comme un diagramme, nous

273
00:13:01,160 --> 00:13:05,022
vouloir pop maintenant
élément hors de cette pile.

274
00:13:05,022 --> 00:13:05,730
Alors que faisons-nous?

275
00:13:05,730 --> 00:13:08,188
Eh bien, nous allons d'abord créer
un nouveau pointeur qui se passe

276
00:13:08,188 --> 00:13:10,940
pour pointer vers le même endroit que la tête.

277
00:13:10,940 --> 00:13:13,790
Nous allons le déplacer d'une position
l'avant en disant égaux trav

278
00:13:13,790 --> 00:13:17,510
trav suivant par exemple, qui
faire avancer l'un trav pointeur

279
00:13:17,510 --> 00:13:19,324
position avant.

280
00:13:19,324 --> 00:13:21,240
Maintenant que nous avons une
maintenir sur le premier élément

281
00:13:21,240 --> 00:13:24,573
via le pointeur appelé liste, et le
deuxième élément via un pointeur appelé

282
00:13:24,573 --> 00:13:28,692
trav, nous pouvons supprimer en toute sécurité que
premier élément de la pile

283
00:13:28,692 --> 00:13:30,650
sans perdre le reste
de la chaîne parce que nous

284
00:13:30,650 --> 00:13:32,358
avoir un moyen de se référer
au second élément

285
00:13:32,358 --> 00:13:34,780
transmettre par l'intermédiaire de la
pointeur trav appelé.

286
00:13:34,780 --> 00:13:37,100
>> Alors maintenant, nous pouvons libérer ce nœud.

287
00:13:37,100 --> 00:13:38,404
Nous pouvons libérer liste.

288
00:13:38,404 --> 00:13:41,320
Et puis tout ce que nous devons faire maintenant est
déplacer la liste à un point à la même place

289
00:13:41,320 --> 00:13:44,482
que trav fait, et nous sommes en quelque sorte de retour
où nous avons commencé avant nous avons poussé 12

290
00:13:44,482 --> 00:13:45,690
sur en premier lieu, à droite.

291
00:13:45,690 --> 00:13:46,940
Ceci est exactement là où nous étions.

292
00:13:46,940 --> 00:13:48,840
Nous avons eu cette quatre éléments pile.

293
00:13:48,840 --> 00:13:49,690
Nous avons ajouté un cinquième.

294
00:13:49,690 --> 00:13:51,910
Nous avons poussé un cinquième
élément sur, et puis nous

295
00:13:51,910 --> 00:13:55,980
sauté que plus récemment
élément ajouté reculer.

296
00:13:55,980 --> 00:13:58,816
>> Cela est vraiment assez bien
tout ce qu'il ya à piles.

297
00:13:58,816 --> 00:14:00,190
Vous pouvez les mettre en oeuvre sous forme de tableaux.

298
00:14:00,190 --> 00:14:01,815
Vous pouvez les mettre en œuvre les listes chaînées.

299
00:14:01,815 --> 00:14:04,810
Il existe, bien sûr, d'autres
les moyens de les mettre en œuvre aussi bien.

300
00:14:04,810 --> 00:14:09,060
Fondamentalement, la raison pour laquelle nous devrions utiliser
empilements est de maintenir les données de telle manière

301
00:14:09,060 --> 00:14:12,090
que les plus récemment ajoutées
élément est la première chose que nous sommes

302
00:14:12,090 --> 00:14:14,980
allez vouloir revenir.

303
00:14:14,980 --> 00:14:17,900
Je suis Doug Lloyd, cela est CS50.

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