devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

栈的基本操作（出栈、入栈、销毁..._栈(创建,销毁,入,出)

作者：weixin_40725706 | 2024-05-29 08:35:02

赞

踩

栈(创建,销毁,入,出)

系列文章目录

单链表（自用-CSDN博客

数据结构_线性表_顺序表（C语言实现+超详细逐步解析-CSDN博客

数据结构_线性表_双向链表（C语言实现+基本操作-CSDN博客

目录

一、栈基本概念、结构、图示

二、栈的基本操作

1、初始化

 代码：

创建栈

初始化栈

2、入栈

3、出栈

4、栈顶元素

5、栈中有效元素个数

6、检测栈是否为空

7、销毁栈

三、汇总

一、栈基本概念、结构、图示

栈的逻辑结构：

可以类比一个“羽毛球筒”，最先进入的羽毛球，必须等待，其他球取出，才能出来。

​

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。（如图所示：）

​

栈的物理结构：

可以用数组实现，也可以用链表实现。

二、栈的基本操作

1、初始化

 数组的结构实现更优一些。因为数组在尾插的代价比较小。

创建栈的结构体，包括栈的基本信息，数组，栈顶，栈的容量。

​

 代码：

创建栈

  1. typedef struct Stack {
  2. 	SDataType* st;//动态开辟
  3. 	int top;//栈顶
  4. 	int capacity;//容量
  5. }ST;
初始化栈

！！！注意

top 的取值，

第一种，top  = 0，则栈顶元素在 top - 1 的位置

第二种，top  = -1，则栈顶元素在 top  的位置。

在本文中，top 取值为 0

​

​

  1. // 初始化栈
  2. void StackInit(ST* s) {
  3. 	assert(s);
  4. 	// 栈 s 不能为空
  5. 	//assert的作用是现计算表达式 test，如果其值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行。
  6.  
  7. 	s->st = NULL;
  8. 	s->top = s->capacity = 0;
  9. }

2、入栈

注意事项：

1、栈满、栈空时，都需要对栈的空间进行扩容，使用realloc函数。

        空间开辟的规则，一般遵循，一开始开辟四个单位。

        后面扩容时，扩增为原来的2倍。

2、动态开辟问题

检查是否开辟成功。

使用完毕后，也必须使用free函数，释放掉。避免内存泄漏。

  1. // 入栈
  2. void StackPush(ST* s, SDataType data) {
  3. 	assert(s);
  4.  
  5. 	int newcapacity;//新容量
  6.  
  7. 	//栈满  栈空 条件判断
  8. 	//则需要开辟新空间，
  9. 	//栈空开辟 4个
  10. 	//栈满  开辟原先的 2倍
  11. 	if (s->capacity == s->top) {
  12.  
  13. 		//栈空
  14. 		if (s->capacity == 0) {
  15. 			newcapacity = 4;
  16. 		}
  17. 		else newcapacity = s->capacity * 2;		//栈满
  18.  
  19. 		SDataType* temp = (SDataType*)realloc(s->st,sizeof(SDataType) * newcapacity);
  20. 		//扩容
  21.  
  22. 		//检查是否扩容成功
  23. 		if (temp == NULL) {
  24. 			perror("malloc failed");
  25. 			exit(-1);
  26. 		}
  27. 		s->st = temp;
  28. 		s->capacity = newcapacity;
  29. 	}
  30.  
  31. 	s->st[s->top] = data;
  32. 	s->top++;
  33. }

3、出栈

  1. // 出栈
  2. void StackPop(ST* s,SDataType* data) {
  3. 	assert(s);
  4.  
  5. 	if (s->top == 0) {
  6. 		printf("栈空");
  7. 	}
  8. 	data = s->st[s->top - 1];
  9. 	s->top--;
  10. }

4、栈顶元素

栈顶元素在 top - 1 的位置

  1. // 获取栈顶元素
  2. SDataType StackTop(ST* s) {
  3. 	assert(s);
  4.  
  5. 	assert(s->top > 0);//栈不为空
  6.  
  7. 	return s->st[s->top - 1];
  8. }

5、栈中有效元素个数

  1. // 获取栈中有效元素个数
  2. int StackSize(ST* s) {
  3. 	assert(s);
  4. 	
  5. 	return s->top ;
  6. }

6、检测栈是否为空

  1. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  2. bool StackEmpty(ST* s) {
  3. 	assert(s);
  4.  
  5. 	if (s->top == 0) {
  6. 		return 1;
  7. 	}
  8. 	else return 0;
  9. }

7、销毁栈

  1. // 销毁栈
  2. void StackDestroy(ST* s) {
  3. 	assert(s);
  4.  
  5. 	free(s->st);
  6.  
  7. 	s->st = NULL;
  8. 	s->top = s->capacity = 0;
  9.  
  10. }

三、汇总

本篇文章就到此结束啦！

以下就是全篇汇总啦~

  1. #include"Stack.h"
  2.  
  3. // 初始化栈
  4. void StackInit(ST* s) {
  5. 	assert(s);
  6. 	// 栈 s 不能为空
  7. 	//assert的作用是现计算表达式 test，如果其值为假（即为0），那么它先向stderr打印一条出错信息，然后通过调用 abort 来终止程序运行。
  8.  
  9. 	s->st = NULL;
  10. 	s->top = s->capacity = 0;
  11. }
  12.  
  13. // 入栈
  14. void StackPush(ST* s, SDataType data) {
  15. 	assert(s);
  16.  
  17. 	int newcapacity;//新容量
  18.  
  19. 	//栈满  栈空 条件判断
  20. 	//则需要开辟新空间，
  21. 	//栈空开辟 4个
  22. 	//栈满  开辟原先的 2倍
  23. 	if (s->capacity == s->top) {
  24.  
  25. 		//栈空
  26. 		if (s->capacity == 0) {
  27. 			newcapacity = 4;
  28. 		}
  29. 		else newcapacity = s->capacity * 2;		//栈满
  30.  
  31. 		SDataType* temp = (SDataType*)realloc(s->st,sizeof(SDataType) * newcapacity);
  32. 		//扩容
  33.  
  34. 		//检查是否扩容成功
  35. 		if (temp == NULL) {
  36. 			perror("malloc failed");
  37. 			exit(-1);
  38. 		}
  39. 		s->st = temp;
  40. 		s->capacity = newcapacity;
  41. 	}
  42.  
  43. 	s->st[s->top] = data;
  44. 	s->top++;
  45. }
  46.  
  47. // 出栈
  48. void StackPop(ST* s,SDataType* data) {
  49. 	assert(s);
  50.  
  51. 	if (s->top == 0) {
  52. 		printf("栈空");
  53. 	}
  54. 	data = s->st[s->top - 1];
  55. 	s->top--;
  56. }
  57.  
  58. // 获取栈顶元素
  59. SDataType StackTop(ST* s) {
  60. 	assert(s);
  61.  
  62. 	assert(s->top > 0);//栈不为空
  63.  
  64. 	return s->st[s->top - 1];
  65. }
  66.  
  67. // 获取栈中有效元素个数
  68. int StackSize(ST* s) {
  69. 	assert(s);
  70. 	
  71. 	/*因为top是指向栈顶元素的最后一个位置
  72. 	假设元素为：1，2，3，4，5，那么top肯定是指向5的后一个位置
  73. 	又因为top是从0开始累加的，所以此时top肯定为5，刚好就是元素个数
  74. 	*/
  75.  
  76. 	return s->top ;
  77. }
  78.  
  79. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
  80. bool StackEmpty(ST* s) {
  81. 	assert(s);
  82.  
  83. 	if (s->top == 0) {
  84. 		return 1;
  85. 	}
  86. 	else return 0;
  87. }
  88.  
  89. // 销毁栈
  90. void StackDestroy(ST* s) {
  91. 	assert(s);
  92.  
  93. 	free(s->st);
  94.  
  95. 	s->st = NULL;
  96. 	s->top = s->capacity = 0;
  97.  
  98. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/641368
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号