DOUG LLOYD: Très bien, donc par ce point vous êtes probablement assez familier avec les tableaux et les listes chaînées qui est les deux primaire structures de données que nous avons parlé pour garder ensembles de des données de types de données similaires organisé. Maintenant, nous allons parler sur un couple de variations sur des tableaux et listes liées. Dans cette vidéo, nous allons pour parler de piles. Plus précisément, nous allons parler sur une structure de données appelée une pile. Rappel des discussions précédentes et des pointeurs sur la mémoire, que la pile est également le nommer pour un segment de mémoire où statiquement déclarée memory-- mémoire que vous nommer, les variables que vous nommez, et cetera et de fonction des cadres que nous avons aussi cadres de pile d'appel existent. Donc, ceci est une structure de données en pile pas un segment de pile de mémoire. D'ACCORD. 

Mais qu'est-ce qu'une pile? Donc, il est à peu près juste un type spécial de la structure qui maintient les données d'une manière organisée. Et il ya deux très des moyens communs à mettre en œuvre empilements utilisant deux structures de données que nous sommes déjà familiers avec, les tableaux et les listes chaînées. Ce qui rend une spéciale de la pile est le façon dont nous mettons l'information dans la pile, et la façon dont nous supprimer des informations de la pile. En particulier avec des piles la règle est que le plus récemment élément supplémentaire peut être retirée. 

Alors, pensez à ce sujet que si elle est une pile. Nous empiler informations au-dessus de lui-même, et seulement la chose au sommet de la pile peut être retiré. Nous ne pouvons pas retirer la chose sous parce que tout le reste effondrer et tomber. Alors, vraiment, nous construisons une pile il nous faut alors retirer morceau par morceau. Parce que de ce que nous appelons communément pour une pile comme une structure LIFO, dernier entré, premier sorti. LIFO, dernier entré, premier sorti. 

Donc à cause de cette restriction sur façon dont l'information peut être ajouté à et retiré d'une pile, il n'y a vraiment seulement deux choses que nous pouvons faire avec une pile. Nous pouvons pousser, qui est la terme que nous utilisons pour ajouter un nouvel élément à la partie supérieure de la pile, ou si existe pas la pile et nous créons à partir de zéro, la création de la pile en premier lieu serait pousser. Et puis pop, qui est le genre de CS terme que nous utilisons pour enlever le plus récemment l'élément rapporté de sommet de la pile. 

Donc, nous allons examiner à la fois implémentations, basée à la fois tableau et la liste de liens fondés. Et nous allons commencer avec tableau de base. Alors, voici l'idée de base de ce la structure de données de matrice à base de pile ressemblerait. Nous avons une définition dactylographiée ici. A l'intérieur de ce que nous avons deux membres ou les champs de la structure. Nous avons un tableau. Et encore, je suis en utilisant le arbitraire valeur de type de données. 

Donc, cela pourrait être n'importe quel type de données, int char ou d'autres données tapez vous avez précédemment créé. Donc, nous avons une gamme de capacité de taille. Capacité étant une livre défini constant, peut-être quelque part ailleurs dans notre fichier. Donc, déjà remarqué avec ce particulier la mise en œuvre nous EXpLoRATIoN nous comme ce fut généralement le cas des tableaux, que nous ne pouvons pas redimensionner dynamiquement, où il ya un certain nombre d'éléments maximum nous pouvons mettre dans notre pile. Dans ce cas, il est des éléments de capacité. 

Nous conservons également le sommet de la pile. Quel élément est le plus récemment ajoutés à la pile? Et si nous gardons une trace de ce que en haut d'une variable appelée. Et tout cela est enveloppé tous ensemble dans un nouveau type de données appelée une pile. Et une fois que nous sommes créés ce nouveau type de données nous pouvons traiter comme tout autre type de données. Nous pouvons déclarer pile s, tout comme nous pourrions faire int x, y ou char. Et quand nous disons empilons s, bien ce qui se passe est nous obtenons un ensemble de mémoire mis de côté pour nous. 

Dans ce cas, la capacité de Je suis apparemment décidé est 10 parce que je ai un seule variable du type de pile qui contient deux champs rappellent. Un tableau, dans ce cas va être un tableau d'entiers comme est le cas dans la plupart de mes exemples. Et une autre variable entière capable de stocker le haut, le plus récemment ajouté élément de la pile. Donc, une seule pile de ce que nous vient d'être défini ressemble à ceci. Il est une boîte contenant un tableau de ce que 10 sera entiers dans cette affaire et une autre variable entière y en vert pour indiquer le haut de la pile. 

Pour définir le haut de la pile, nous disons simplement s.top. Voilà comment nous accédons à un champ d'un rappel de la structure. s.top est égal à 0 efficacement ce que cela à notre pile. Encore une fois, nous avons deux opérations que nous pouvons effectuer maintenant. Nous pouvons pousser et nous pouvons pop. Commençons par poussoir. Encore une fois, poussant est l'ajout d'un nouveau élément en haut de la pile. 

Alors, que devons-nous faire dans cette matrice de mise en œuvre sur la base? Eh bien, en général fonction Push va avoir besoin d'accepter une pointeur vers la pile. Maintenant, prenez une seconde pour y penser. Pourquoi voudrions-nous à accepter un pointeur sur la pile? Rappel de vidéos précédentes sur la portée des variables et des pointeurs, ce qui arriverait si nous venons d'envoyer pile, s plutôt comme un paramètre? Quel serait réellement passé là-bas? Rappelez-vous que nous créons une copie quand nous passons à une fonction à moins que nous utilisons des pointeurs. Et si cette fonction pousser besoins à accepter un pointeur de la pile de sorte que nous sommes en train de changer la pile nous avons l'intention de changer. 

L'autre chose poussoir veut probablement accepter est un élément de données d'une valeur de type. Dans ce cas, à nouveau, un nombre entier qui nous allons ajouter à la haut de la pile. Donc, nous avons nos deux paramètres. Qu'allons-nous à maintenant faire à l'intérieur de la poussée? Eh bien, tout simplement, nous allons juste ajouter cet élément au sommet de la pile puis changer l'endroit où le haut de la pile est, que l'art dot valeur supérieure. Voilà donc ce que une fonction déclaration de poussoir pourrait ressembler dans un basée sur la baie de mise en œuvre. 

Encore une fois cette est pas une règle dure et rapide que vous pouviez changer cela et avoir elle varie de différentes façons. Peut-être s est déclaré globalement. Et si vous ne même pas besoin pour passer, il est comme un paramètre. Ceci est encore juste un cas général pour pousser. Et il ya différents les moyens de la mettre en œuvre. Mais dans ce cas, notre poussoir va prendre deux arguments, un pointeur vers une pile et un élément de données de valeur de type, nombre entier dans ce cas. 

Donc, nous avons déclaré s, nous ledit s.top est égal à 0. Maintenant, nous allons pousser le Numéro 28 sur la pile. Eh bien, qu'est-ce que cela signifie? Bien actuellement la sommet de la pile est 0. Et donc ce qui est essentiellement qui va se passer est nous allons nous en tenir le nombre 28 dans l'emplacement de tableau 0. Assez simple, droite, que a été le meilleur et maintenant nous sommes bon pour aller. Et puis, nous avons besoin de changer ce que le haut de la pile sera. Alors que la prochaine fois nous poussons un élément, nous allons stocker dans Lieu de tableau, probablement pas 0. Nous ne voulons pas écraser ce que nous venons de mettre là. Et donc nous allons simplement déplacer l'extrémité supérieure à 1. Cela fait sans doute logique. 

Maintenant, si nous voulons mettre un autre élément sur la pile, disons que nous voulons pousser 33, Eh bien maintenant, nous allons juste prendre 33 et le mettre au tableau numéro d'emplacement 1, puis modifiez le haut de notre empiler être éventail emplacement numéro deux. Donc, si la prochaine fois que nous voulons pousser un élément sur la pile, il va être mis en réseau localité 2. Et nous allons faire ce que une fois de plus. Nous allons pousser 19 hors des piles. Nous allons mettre 19 dans le tableau localité 2 et changer le sommet de notre pile pour être l'emplacement du tableau 3 Donc, si nous la prochaine fois besoin de faire un effort, nous sommes bon pour aller. 

OK, alors que ça poussant en un mot. Qu'en est-il éclater? Donc popping est le genre de contrepartie de pousser. Il est comment nous enlevons les données de la pile. Et dans les besoins généraux de la pop faire ce qui suit. Il doit accepter un pointeur sur la empiler, à nouveau dans le cas général. Dans certains autres cas, vous pourriez ont déclaré la pile à l'échelle mondiale, dans ce cas vous ne devez pas passer car il en a déjà accès à ce en tant que variable globale. Mais alors quoi d'autre avons-nous besoin de le faire? Eh bien, nous étions incrémentation le haut de la pile en push, donc nous allons probablement vouloir pour décrémenter le sommet de la pile pop, non? Et puis bien sûr Nous allons aussi vouloir pour renvoyer la valeur que nous retirons. Si nous ajoutons des éléments, nous voulons pour obtenir des éléments hors plus tard, nous avons probablement fait envie de les stocker afin que nous ne vous contentez pas de les supprimer à partir de la empiler et puis ne rien faire avec eux. En général, si nous sommes pousser et popping ici nous voulons stocker cette informations d'une manière significative et il ne fait pas sens de simplement le jeter. Donc, cette fonction devrait probablement retourner une valeur pour nous. 

Voilà donc ce que une déclaration pour la pop il pourrait ressembler en haut à gauche. Cette fonction renvoie les données de valeur de type. Encore une fois nous avons été en utilisant tout au long de nombres entiers. Et il accepte un pointeur vers une pile comme son seul argument ou un paramètre unique. Alors, quelle est la pop va faire? Disons que nous voulons maintenant pop un élément hors de l'art. Donc me souviens que je disais que les piles sont dernière In, First Out, LIFO structures de données. Quel élément va être présente dans la pile? Avez-vous deviné 19? Parce que vous avez raison. 19 était le dernier élément, nous avons ajouté à la empiler quand nous poussions éléments sur, et donc ça va à la première élément qui sera éliminé. Il est comme si nous disions 28, et puis nous avons mis 33 sur le dessus de celui-ci, et nous avons mis 19 sur le dessus de cela. Le seul élément que nous pouvons décoller est de 19. 

Maintenant, dans le diagramme ici ce que je l'ai fait est une sorte de supprimer 19 à partir du tableau. Cela ne veut pas réellement ce que nous allons faire. Nous allons juste genre de prétendre qu'il n'y est pas. Il est toujours là dans cet emplacement de mémoire, mais nous allons juste l'ignorer en changeant la tête de notre pile étant de 3 à 2. Donc, si nous étions à pousser maintenant un autre élément dans la pile, il serait plus écrire 19. 

Mais ne soyons pas passer par la peine de supprimer 19 de la pile. Nous pouvons simplement prétendre qu'il n'y est pas. Aux fins de la pile, il est parti si nous changeons le haut pour être 2 au lieu de 3. Tout droit, ce qui était à peu près tout. Voilà tout ce que nous devons faire à la pop un élément off. Faisons le encore. Donc, je l'ai souligné en rouge ici pour indiquons que nous faisons un autre appel. Nous allons faire la même chose. 

Alors qu'est-ce qui va se passer? Eh bien, nous allons stocker 33 en x et nous allons pour changer le dessus de la pile à une. Alors que si nous devions maintenant pousser un élément dans la pile qui nous sommes va faire maintenant, ce qu'il va se passer est que nous allons écraser tableau emplacement numéro 1. Alors que 33 qui a été laissé de tri derrière que nous fait semblant n'y est plus, nous allons juste à tabasser et de le mettre à la place il y 40. Et puis bien sûr, depuis que nous avons fait une poussée, nous allons augmenter le sommet de la pile 1-2 de sorte que si nous ajoutons maintenant un autre élément ça va aller dans un tableau emplacement numéro deux. 

Maintenant listes chaînées sont un autre façon d'appliquer piles. Et si cette définition sur la écran semble ici familier pour vous, il est parce qu'il ressemble presque exactement la même, en fait, il est à peu près exactement le même comme une liste chaînée, si vous vous souvenez de notre discussion chaînée listes dans une autre vidéo. La seule restriction ici est pour nous en tant que programmeurs, nous ne sommes pas autorisés à insérer ou de supprimer de façon aléatoire de la liste chaînée que nous pourrions le faire auparavant. Nous ne pouvons désormais insérer et supprimer de l'avant ou le haut de l'lié liste. Cela est vraiment la seule différence cependant. Ceci est contraire une liste chaînée. Il est seulement la restriction remplacement sur nous-mêmes comme les programmeurs qui le change en une pile. 

La règle ici est de maintenir toujours un pointeur vers la tête d'une liste chaînée. Ceci est bien sûr un général règle importante en premier. Pour isolément liste liée de toute façon vous seulement besoin d'un pointeur sur la tête afin d'obtenir que chaîne pouvoir consulter à chaque autre élément dans la liste chaînée. Mais il est particulièrement importante avec une pile. Et si généralement vous êtes allez vouloir réellement ce pointeur pour être une variable globale. Il va probablement être encore plus facile de cette façon. Alors, quels sont les analogues de la poussée et de la pop? Droit. Donc, poussant à nouveau est d'ajouter un nouvel élément à la pile. Dans une liste liée qui signifie que nous allons devoir pour créer un nouveau nœud que nous sommes aller à ajouter dans la liste chaînée, puis suivez les étapes minutieuses que nous avons indiqué précédemment dans les listes simplement liés à l'ajouter à la chaîne sans rupture de la chaîne et de perdre toute ou orphelins éléments de la liste chaînée. Et qui est essentiellement ce que petite goutte de texte, il résume. Et nous allons jeter un coup d'oeil à elle comme un diagramme. 

Alors, voici notre liste chaînée. Il contient en même temps que quatre éléments. Et plus parfaitement voici notre pile contenant quatre éléments. Et disons que nous voulons maintenant pousser un nouvel élément sur cette pile. Et nous voulons pousser une nouvelle l'article dont les données valeur est 12. Eh bien, qu'allons-nous faire? Eh bien d'abord, nous allons espace de malloc, dynamiquement allouer de l'espace pour un nouveau noeud. Et bien sûr, immédiatement après nous faisons un appel à nous malloc toujours assurez-vous de vérifier null, parce que si nous sommes arrivés nulle retour il y avait une sorte de problème. Nous ne voulons pas de déréférencer que null pointeur ou vous allez souffrir d'un défaut de seg. Ce n'est pas bien. Nous avons donc malloced du noeud. Nous allons supposer que nous avons eu du succès ici. Nous allons mettre 12 dans le champ de données de ce noeud. Maintenant, vous rappelez-vous ce qui de nos pointeurs émeut prochaine afin de ne pas briser la chaîne? Nous avons un couple d'options ici, mais le seul qui va être sécuritaire est de mettre en nouvelles pointeur à côté de Point à l'ancien chef de la liste ou ce sera bientôt le vieille tête de la liste. Et maintenant que l'ensemble de notre éléments sont enchaînés, nous pouvons simplement déplacer la liste à signaler à la même place que la nouvelle fait. Et nous avons maintenant effectivement poussé un nouvel élément sur la face avant de la pile. 

Pour nous pop veux juste supprimer ce premier élément. Et donc en gros ce que nous avons à faire ici, Eh bien, nous devons trouver le deuxième élément. Finalement, qui deviendra la nouvelle tête après nous supprimons la première. Donc nous avons juste besoin de partir le début, déplacer l'un vers l'avant. Une fois que nous avons une emprise sur un avant de où nous actuellement sommes nous pouvons supprimer le premier en toute sécurité et alors nous pouvons simplement déplacer la tête pour pointer vers ce qui était le second mandat puis maintenant est le premier après que nœud a été supprimé. 

Donc encore une fois, de prendre un coup d'oeil cela comme un diagramme, nous vouloir pop maintenant élément hors de cette pile. Alors que faisons-nous? Eh bien, nous allons d'abord créer un nouveau pointeur qui se passe pour pointer vers le même endroit que la tête. Nous allons le déplacer d'une position l'avant en disant égaux trav trav suivant par exemple, qui faire avancer l'un trav pointeur position avant. Maintenant que nous avons une maintenir sur le premier élément via le pointeur appelé liste, et le deuxième élément via un pointeur appelé trav, nous pouvons supprimer en toute sécurité que premier élément de la pile sans perdre le reste de la chaîne parce que nous avoir un moyen de se référer au second élément transmettre par l'intermédiaire de la pointeur trav appelé. 

Alors maintenant, nous pouvons libérer ce nœud. Nous pouvons libérer liste. Et puis tout ce que nous devons faire maintenant est déplacer la liste à un point à la même place que trav fait, et nous sommes en quelque sorte de retour où nous avons commencé avant nous avons poussé 12 sur en premier lieu, à droite. Ceci est exactement là où nous étions. Nous avons eu cette quatre éléments pile. Nous avons ajouté un cinquième. Nous avons poussé un cinquième élément sur, et puis nous sauté que plus récemment élément ajouté reculer. 

Cela est vraiment assez bien tout ce qu'il ya à piles. Vous pouvez les mettre en oeuvre sous forme de tableaux. Vous pouvez les mettre en œuvre les listes chaînées. Il existe, bien sûr, d'autres les moyens de les mettre en œuvre aussi bien. Fondamentalement, la raison pour laquelle nous devrions utiliser empilements est de maintenir les données de telle manière que les plus récemment ajoutées élément est la première chose que nous sommes allez vouloir revenir. Je suis Doug Lloyd, cela est CS50.