Partage de technologie

Pile de structure de données

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Titre

Salut ! Bonjour les amis ! Apprenons ensemble la structure des données de la pile ! Êtes-vous prêt ? Je vais commencer !

1. Pile

1.1 Concepts de base de la pile

Pile : une liste linéaire spéciale qui autorise uniquement les opérations d'insertion et de suppression à une extrémité fixe. L'extrémité qui entre dans les opérations d'insertion et de suppression de données est appelée le haut de la pile et l'autre extrémité est appelée le bas de la pile.Les éléments de données de la pile sont conformesLIFO (Dernier entré, premier sorti). On peut l'imaginer comme manger des brochettes de mouton,Mettez-le d'abordLes morceaux de mouton sont pressésbas，le dernierLes morceaux de mouton sont dedansAu sommetde.

Pousser la pile : L'opération d'insertion de la pile est appelée push/push/push.Insérer des données du haut de la pile。

Pop : L'opération de suppression de la pile est appelée popping.Les données sortantes sont également en haut de la pile。

1.2 Implémentation de la pile

La pile peut généralement être implémentée en utilisant un tableau pour implémenter la pile ou en utilisant une liste chaînée pour implémenter la pile, selon la meilleure utilisation, relativement parlant.structure du tableauLa mise en œuvre de la pile est plus simple et plus efficace.

Car dans la mise en œuvre de l'interface d'ajout, de suppression, de modification et de requête de la table de séquence précédente (table de séquence de structure de données) Il est très pratique pour nous d'utiliser la structure du tableau pour insérer et supprimer à partir de la fin, donc dans l'implémentation de la pile, nous définissons la fin du tableau comme le haut de la pile et la tête comme le bas de la pile.

2. Implémentation de l'interface de pile

La pile, comme la liste de séquences, peut être conçue comme une pile statique de longueur fixe ou une pile à croissance dynamique.Parce que la pile de longueur fixe a de grandes limites et n'est pas pratique en pratique, nous implémentons principalement le supportPile à croissance dynamique。

Comme pour l'implémentation précédente de l'interface liste de séquences/liste chaînée, nous créons d'abord un fichier d'en-tête "Stack.h" et deux fichiers sources "Stack.c" et "Test.c".

Pile.hDéfinition de la pile, référence du fichier d'en-tête et déclaration de la fonction d'interface
Pile.cImplémentation des fonctions d'interface
Test.cTestez chaque fonction

Montrons d'abord le code complet de "Stack.h", n'oubliez pas de citer "Stack.h" dans les 2 fichiers sources

  1. #pragma once				//防止头文件被二次引用
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5.  
  6. typedef int ElemType;		//如果要修改存储的数据类型可直接在此修改
  7. typedef struct Stack {
  8. 	ElemType* arr;			//动态数组
  9. 	int top;				//栈顶
  10. 	int capacity;			//容量
  11. }Stack;
  12.  
  13.  
  14. void StackInit(Stack* ps);//初始化栈
  15.  
  16. void StackPush(Stack* ps, ElemType x);//入栈
  17.  
  18. void StackPop(Stack* ps);//出栈
  19.  
  20. ElemType StackTop(Stack* ps);//获取栈顶元素
  21.  
  22. int StackSize(Stack* ps);//获取栈中有效元素的个数
  23.  
  24. int StackEmpty(Stack* ps);//检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  25.  
  26. void StackDestroy(Stack* ps);//销毁栈

Parmi eux, la signification de « top » est déterminée par la valeur initiale, qui sera expliquée en détail ci-dessous. Ensuite, nous commençons à implémenter l'interface.

(1) Pile d'initialisation
  1. //初始化栈
  2. void StackInit(Stack* ps) {
  3. 	assert(ps);		//断言,防止传入空指针
  4. 	ps->arr = NULL; //初始化数组,置空
  5. 	ps->capacity = 0;//top指向栈顶元素的下一个位置
  6. 	ps->top = 0;	 //初始化容量
  7. }

Pour faciliter la compréhension, nous comprenons approximativement top dans la structure comme l'indice du tableau.Si nous initialisons top à 0 lors de l'initialisation de la pile, il n'y a aucune donnée dans la pile et top pointe vers la position suivante des données supérieures sur la pile.

Si nous initialisons top à -1, top pointera vers l'emplacement des premières données sur la pile. Il est préférable pour nous de l'initialiser à 0 ici car il est pratique d'ajouter des éléments et de supprimer des éléments.

(2) Poussez dans la pile
  1. //入栈
  2. void StackPush(Stack* ps, ElemType x) {
  3. 	//扩容
  4. 	if (ps->capacity == ps->top) //容量已满,需要扩容
  5. 	{
  6. 		//如果容量为0,则扩容到4; 否则扩大2倍
  7. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
  8. 		//创建一个临时指针变量来存储新空间地址,防止开辟失败
  9. 		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
  10. 		if (temp == NULL) //防止开辟失败出现空指针
  11. 		{
  12. 			perror("realloc fail!n");
  13. 			exit(1);
  14. 		}
  15. 		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
  16. 		ps->capacity = newCapacity;//空间容量更新
  17. 	}
  18. 	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
  19. 	ps->top++;//位置更新
  20. }

Parce qu'il y a une différence entre la pile et la table de séquence, nous ne pouvons pas parcourir et imprimer directement. Par conséquent, si nous voulons imprimer les éléments de la pile, nous devons utiliser la fonction StackEmpty et la fonction StackPop, qui seront discutées plus tard. .

(3) Sortez
  1. //出栈
  2. void StackPop(Stack* ps) {
  3. 	assert(ps);			//断言,防止传入空指针
  4. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  5. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  6. }
(4) Obtenez l'élément supérieur de la pile
  1. //获取栈顶元素
  2. ElemType StackTop(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	assert(ps->top);		//断言,防止栈为空
  5. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  6. }
(5) Obtenez le nombre d'éléments valides dans la pile
  1. //获取栈中有效元素的个数
  2. int StackSize(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top;			//top即为有效元素的个数
  5. }
(6) Vérifiez si la pile est vide
  1. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  2. int StackEmpty(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	return ps->top == 0;	//如果top==0, 说明栈为空
  5. }

C'est pourquoi StackEmpty dans l'assertion précédente doit être ajoutéopérateur de négation logiqueLa raison en est que si la pile est vide, StackEmpty renvoie true et la négation de false peut prouver qu'il y a des éléments dans la pile.

(7) Détruisez la pile
  1. //销毁栈
  2. void StackDestroy(Stack* ps) {
  3. 	assert(ps);				//断言,防止传入空指针
  4. 	if (ps->arr)			//如果动态数组有效
  5. 	{
  6. 		free(ps->arr);		//释放arr
  7. 		ps->arr = NULL;		//将arr置空
  8. 	}
  9. 	ps->capacity = 0;		//数组的容量为0
  10. 	ps->top = 0;			//数组的栈顶top为0
  11.  
  12. }

Une fois toutes les interfaces terminées, testons le code dans Test.c :

Testons-le encore :

Aucun problème. Félicitations pour avoir terminé l'implémentation de l'interface de pile ! Voici le code complet du fichier "Stack.c" :

  1. #include"Stack.h"
  2.  
  3. //初始化栈
  4. void StackInit(Stack* ps) {
  5. 	assert(ps);		//断言,防止传入空指针
  6. 	ps->arr = NULL; //初始化数组,置空
  7. 	ps->capacity = 0;//top指向栈顶元素的下一个位置
  8. 	ps->top = 0;	 //初始化容量
  9. }
  10.  
  11. //入栈
  12. void StackPush(Stack* ps, ElemType x) {
  13. 	//扩容
  14. 	if (ps->capacity == ps->top) //容量已满,需要扩容
  15. 	{
  16. 		//如果容量为0,则扩容到4; 否则扩大2倍
  17. 		int newCapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
  18. 		//创建一个临时指针变量来存储新空间地址,防止开辟失败
  19. 		ElemType* temp = realloc(ps->arr, newCapacity * sizeof(ElemType));
  20. 		if (temp == NULL) //防止开辟失败出现空指针
  21. 		{
  22. 			perror("realloc fail!n");
  23. 			exit(1);
  24. 		}
  25. 		ps->arr = temp;	  //将临时指针变量中存放的新空间地址赋给arr
  26. 		ps->capacity = newCapacity;//空间容量更新
  27. 	}
  28. 	ps->arr[ps->top] = x;//将数据存放进栈顶元素的下一个位置
  29. 	ps->top++;//位置更新
  30. }
  31.  
  32. //出栈
  33. void StackPop(Stack* ps) {
  34. 	assert(ps);			//断言,防止传入空指针
  35. 	assert(ps->top);	//断言,防止栈中没有元素,却还在执行删除
  36. 	ps->top--;			//top指针往前挪动一位(相当于这个位置被覆盖了)
  37. }
  38.  
  39. //获取栈顶元素
  40. ElemType StackTop(Stack* ps) {
  41. 	assert(ps);				//断言,防止传入空指针
  42. 	assert(ps->top);		//断言,防止栈为空
  43. 	return ps->arr[ps->top - 1];//top-1为栈顶元素的位置,返回其值
  44. }
  45.  
  46. //获取栈中有效元素的个数
  47. int StackSize(Stack* ps) {
  48. 	assert(ps);				//断言,防止传入空指针
  49. 	return ps->top;			//top即为有效元素的个数
  50. }
  51.  
  52. //检测栈是否为空,如果为空返回非零结果,如果不为空返回0
  53. int StackEmpty(Stack* ps) {
  54. 	assert(ps);				//断言,防止传入空指针
  55. 	return ps->top == 0;	//如果top==0, 说明栈为空
  56. }
  57.  
  58. //销毁栈
  59. void StackDestroy(Stack* ps) {
  60. 	assert(ps);				//断言,防止传入空指针
  61. 	if (ps->arr)			//如果动态数组有效
  62. 	{
  63. 		free(ps->arr);		//释放arr
  64. 		ps->arr = NULL;		//将arr置空
  65. 	}
  66. 	ps->capacity = 0;		//数组的容量为0
  67. 	ps->top = 0;			//数组的栈顶top为0
  68.  
  69. }

Section d'exercices

1. Laquelle des affirmations suivantes concernant les piles est correcte ( )

A. La pile est une structure de données « premier entré, premier sorti »

B. La pile peut être implémentée à l'aide d'une liste chaînée ou d'une liste de séquences

C. La pile ne peut insérer des données qu'en bas de la pile

D. La pile ne peut pas supprimer les données

bonne réponse: B

Erreur A : La pile est une structure de données dernier entré, premier sorti et la file d'attente est premier entré, premier sorti.

B est correct : les listes de séquences et les listes chaînées peuvent être utilisées pour implémenter des piles, mais les listes de séquences sont généralement utilisées car la pile est considérée comme une version castrée de la liste de séquences. Seules les opérations d'insertion et de suppression de queue de la table de séquence le sont. Utilisé, et l'insertion de queue de la table de séquence est utilisée. La suppression de queue et la suppression de queue ne nécessitent pas d'éléments mobiles et sont très efficaces, elles sont donc généralement implémentées à l'aide de tables séquentielles.

Erreur C : la pile ne peut effectuer des opérations d'insertion et de suppression d'entrée qu'en haut de la pile

Erreur D : la pile comporte des opérations push et pop. Pop consiste à supprimer un élément de la pile.

2. La séquence push d'une pile est ABCDE et la séquence pop impossible est ( )

A. ABCDE

B.EDCBA

C.DCEBA

D.ECDBA

bonne réponse: D

Si E apparaît en premier, cela signifie que ABCDE a été poussé sur la pile. Une fois que E est sorti de la pile, l'élément supérieur de la pile est D. S'il est ressorti à nouveau, il devrait être D, pas C. .

Par conséquent, D doit être sélectionné

3. Par rapport à la pile séquentielle, les avantages évidents de la pile de chaînes sont ( )

A. L'opération d'insertion est plus pratique

B. L'opération de suppression est plus pratique

C. Aucune expansion n'est requise lors de l'insertion dans la pile

bonne réponse: C

Erreur A. S'il s'agit d'une pile liée, elle nécessite généralement des opérations d'insertion ou de suppression de tête, tandis qu'une pile séquentielle effectue généralement des opérations d'insertion et de suppression de queue. Le fonctionnement d'une liste chaînée est plus compliqué qu'une table séquentielle, c'est donc le cas. plus simple d'utiliser une structure séquentielle pour implémenter une pile.

B est faux, veuillez vous référer à A pour la raison.

C est correct. Lorsque la pile est implémentée dans une structure de chaîne, chaque poussée dans la pile équivaut à insérer un nœud dans l'en-tête de la liste chaînée.

4. Laquelle des affirmations suivantes concernant l'utilisation de piles pour implémenter des files d'attente est incorrecte ( )

R. L'utilisation de la simulation de pile pour implémenter une file d'attente peut utiliser deux piles, une pile simule l'entrée dans la file d'attente et une pile simule la sortie de la file d'attente.

B. Chaque fois que vous retirez la file d'attente, vous devez importer tous les éléments d'une pile dans une autre pile, puis les retirer.

C. Lors de l'entrée dans la file d'attente, stockez simplement les éléments directement dans la pile qui simule l'entrée dans la file d'attente.

D. La complexité temporelle de l'opération de file d'attente est O(1)

bonne réponse: B

Dans l'option B, une pile simule l'entrée dans la file d'attente et une pile simule le retrait de la file d'attente. Lors du retrait de la file d'attente, l'élément supérieur de la pile de retrait de la file d'attente simulée apparaît directement. Lorsque la pile est vide, tous les éléments de la pile de file d'attente simulée sont importés. . Les éléments doivent être importés à chaque fois, c'est donc une erreur.

Dans l'option A, les caractéristiques des piles et des files d'attente sont opposées. Une pile ne peut pas implémenter de file d'attente.

Dans l'option C, une pile simule l'entrée dans la file d'attente et une pile simule la sortie de la file d'attente. Lors de l'entrée dans la file d'attente, les éléments sont directement stockés dans la pile qui simule l'entrée dans la file d'attente.

Dans l'option D, mettre en file d'attente signifie mettre des éléments sur la pile, donc la complexité temporelle est O(1)

Fin

Aujourd'hui, nous avons découvert la structure des données d'une pile. N'est-ce pas beaucoup plus simple qu'une liste chaînée, j'espère que cet article sera utile à mes amis !!!

mendierAimez, mettez en favoris et suivez !!!

Merci à tous! ! !

Profil personnel

Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail