• 数据结构之——栈的操作讲解与功能实现

    目录

    一.栈

    A.栈的概念及结构

    2.内存中栈区

    B.栈的实现

            1.实现方式：

            2.栈的数据结构

            3.栈的初始化 

    4.栈的销毁释放

    5.栈数据的插入

    6.空间检查

    7.栈数据的删除——即出栈

    8.访问栈区某个数据的函数

    9.栈空间的长度函数

    函数整体测试：

    整体代码：

    一.栈

    A.栈的概念及结构

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

             栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则，也可以叫后进先出。

             压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

             出栈：栈的删除操作叫做出栈。出数据也在栈顶。

     

    注：这只是栈空间中数据大概的一个出入顺序，下图为详细的栈区增删。 

      

     

     

    2.内存中栈区

            内存中的栈区空间是相当有限的，原因是内存大多空间都给了堆区，堆区是动态开辟的，空间分配的利用上比堆区要高很多，所以我们实现的大多程序都是动态开辟类型的。

            栈区空间在内存是自顶向下开辟的：

           正因为栈内存空间有限，那么在进行函数递归的时候，若是递归次数过多，会把栈空间放满从而系统会崩溃，崩溃的原因就是栈溢出（stack overflow)  例：

    1. int f(int n) {
    2. 	return n == 1 ? 1 : f(n - 1) + f(n - 2);
    3. }
    4. int main() {
    5. 	printf("%d\n", f(10000));
    6.  
    7. 	return 0;
    8. }

    测试结果： 

     

    B.栈的实现

            1.实现方式：

            栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小，而且CPU在数组上的高速缓存命中率比在链表上更高。所以下面我对于栈的实现方式是以顺序表为主体的。

            对于顺序表的讲解和操作实现我已经写了一篇博客，地址在这：            数据结构——线性表之顺序表的基本操作讲解  大家想深入了解数据结构顺序表的实现可以看一看。

            2.栈的数据结构

    静态版：一般不用，空间固定，不灵活。

    1. //静态不常用
    2. typedef int STDataType;
    3. #define N 100
    4. struct Stack {
    5. 	STDataType a[N];
    6. 	int top;
    7. };

    动态版：比静态版的空间利用效率更高。

    1. //动态
    2. typedef int  STDataType;    //重定义int类型为栈类型的
    3. typedef struct Stack {
    4. 	STDataType* a;	//栈型指针——指向堆区空间的
    5. 	int top;	//栈现有的个数
    6. 	int capacity;	//栈区的容量
    7. }ST;    //将栈的结构体类型名改为ST，简化

            3.栈的初始化 

    1. void StackInit(ST* ps)
    2. {
    3. 	assert(ps);    //断言——判断实参传过来的指针是否为空
    4. 	ps->a = NULL;    //先暂时让栈的指针指向NULL
    5. 	ps->top = ps->capacity = 0;
    6. }

     

    4.栈的销毁释放

    1. void StackDestroy(ST* ps)
    2. {
    3. 	assert(ps);    
    4. 	free(ps->a);    //free掉动态开辟的空间
    5. 	ps->a = NULL;   //free掉空间后，这块堆区空间还在，只是还给了操作系统，而且栈的指针a还保存
    6.                     //这块空间的地址，a成为了野指针，很危险，需要置为空
    7. 	ps->capacity = ps->top = 0;    //将容量和存储个数设为0

    5.栈数据的插入

    1. void StackPush(ST* ps, STDataType x)
    2. {
    3. 	assert(ps);
    4. 	// 扩容
    5. 	if (ps->top == ps->capacity)
    6. 	{
    7.         //扩容一般扩2倍
    8. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    9.  
    10. 		STDataType* tmp = (STDataType*)realloc(ps->a, newCapacity*sizeof(STDataType));
    11.         
    12.         //判断是否开辟成功，若开辟失败则报错
    13. 		if (tmp == NULL)
    14. 		{
    15. 			perror("realloc fail");
    16. 			exit(-1);
    17. 		}
    18.  
    19.         //表示开辟失败
    20. 		ps->a = tmp;
    21. 		ps->capacity = newCapacity;
    22. 	}
    23.     
    24.     //入栈，即在栈中存入要存的数据
    25. 	ps->a[ps->top] = x;
    26. 	ps->top++;    //栈空间的数据个数+1
    27. }

            注：栈的结构成员top表示栈中数据存储的个数，栈区为空时，Top指针指向栈底，因为顺序表是以数组为核心实现的，所以Top也就是数组的下标了。每存储一个数据Top都指向这个数据的下一个数据开始位置。

     

    6.空间检查

            在栈区空间的数据删除时，需要进行链表空间的判断，若栈空间为空，则不允许再删除了，所以要实现一个函数去检查。

    注：VS中的C文件里，并不支持bool类型，所以需要在.c文件开头加入#include库函数。

    1. bool StackEmpty(ST* ps)
    2. {
    3. 	assert(ps);
    4. 	return ps->top == 0;
    5. }

    7.栈数据的删除——即出栈

    1. void StackPop(ST* ps)
    2. {
    3. 	assert(ps);
    4.     
    5.     //判断栈区空间是否为空，若为空，则报错，不为空，则存储个数-1
    6. 	assert(!StackEmpty(ps));
    7. 	
    8. 	--ps->top;
    9. }

    栈的操作实现使用顺序表的原因：删除数据方式极为简单方便！

    8.访问栈区某个数据的函数

    1. STDataType StackTop(ST* ps)
    2. {
    3. 	assert(ps);
    4. 	assert(!StackEmpty(ps));
    5. 	
    6. 	return ps->a[ps->top - 1];
    7. }

            刚才讲到了栈结构的成员变量top是从数组下标0开始访问的，访问到的数据，所得下标top要减一。

           访问该数据时， 函数返回的是Top指向的上一个数据的数值。

            top-1原因：数据1，2，3，4，5入栈后，如下图 ：

              当要访问数据4时，需要数据5出栈，才能访问到4，而top是下标，数据5对应的数组下标为4( top)，那么下标3 ( top-1）的位置就是数据4，所以return ps->a[ps->top-1] ; 数据4即可被访问到。

     

    9.栈空间的长度函数

    1. int StackSize(ST* ps)
    2. {
    3. 	assert(ps);
    4.  
    5. 	return ps->top;
    6. }

    函数整体测试：

    整体代码：

    Test.c:

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"Stack.h"
    3.  
    4. void TestStack() {
    5. 	ST st;
    6. 	StackInit(&st);
    7. 	StackPush(&st, 1);
    8. 	StackPush(&st, 2);
    9. 	StackPush(&st, 3);
    10. 	printf("%d\n", StackTop(&st));
    11.  
    12. 	StackPop(&st);
    13. 	printf("%d\n", StackTop(&st));
    14. 	StackPop(&st);
    15.  
    16. 	StackPush(&st, 4);
    17. 	StackPush(&st, 5);
    18.  
    19. 	while (!StackEmpty(&st))
    20. 	{
    21. 		printf("%d ", StackTop(&st));
    22. 		StackPop(&st);
    23. 	}
    24. 	printf("\n");
    25. }
    26.  
    27. //int f(int n) {
    28. //	return n == 1 ? 1 : f(n - 1) + f(n - 2);
    29. //}
    30. int main() {
    31. 	//printf("%d\n", f(10000));
    32. 	TestStack();
    33. 	return 0;
    34. }

    Stack.c文件：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"Stack.h"
    3. //初始化
    4. void StackInit(ST* ps) {
    5. 	assert(ps);
    6. 	ps->a = NULL;
    7. 	ps->top = ps->capacity = 0;
    8. }
    9.  
    10. //入栈
    11. void StackPush(ST* ps, STDataType x) {
    12. 	assert(ps);
    13. 	if (ps->top == ps->capacity) {
    14. 		//创建临时变量，若top==capacity说明两种情况
    15. 		//情况1：栈表刚开始，容量和数据个数都为0，先开个4字节的容量
    16. 		//情况2：说明栈的存储个数达到容量上限，需要扩容了
    17. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    18. 		//上面这个语句设置了情况二所说的扩容倍数大小为2倍
    19. 		//扩容
    20. 		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
    21. 		if (tmp == NULL) {
    22. 			perror("realloc fail");
    23. 			exit(-1);
    24. 		}
    25. 		ps->a = tmp;
    26. 		ps->capacity = newcapacity;
    27.  
    28. 	}
    29. 	//将数据入栈
    30. 	ps->a[ps->top] = x;
    31. 	//个数+1
    32. 	ps->top++;
    33. }
    34.  
    35. //出栈
    36. void StackPop(ST* ps) {
    37. 	assert(ps);
    38. 	assert(!StackEmpty(ps));
    39. 	ps->top--;
    40. }
    41.  
    42. //暴力检查
    43. bool StackEmpty(ST* ps) {
    44. 	assert(ps);
    45. 	return ps->top == 0;
    46. }
    47. //计算栈表长度
    48. int StackSize(ST* ps) {
    49. 	assert(ps);
    50. 	return ps->top;
    51. }
    52.  
    53. //访问栈中某个数据
    54. STDataType StackTop(ST* ps) {
    55. 	assert(ps);
    56. 	assert(!StackEmpty(ps));
    57. 	return ps->a[ps->top - 1];
    58. }

    Stack.h文件：

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. //静态不常用
    8. //typedef int STDataType;
    9. //#define N 100
    10. //struct Stack {
    11. //	STDataType a[N];
    12. //	int top;
    13. //};
    14.  
    15. //动态
    16. typedef int  STDataType;
    17. typedef struct Stack {
    18. 	STDataType* a;	//栈型指针——指向堆区空间的
    19. 	int top;	//栈现有的个数
    20. 	int capacity;	//栈区的容量
    21. }ST;
    22.  
    23. void StackInit(ST* ps);
    24. void StackDestory(ST* ps);
    25. void StackPush(ST* ps);
    26. void StackPop(ST* ps);
    27.  
    28. bool StackEmpty(ST* ps);
    29. int StackSize(ST* ps);
    30. STDataType StackTop(ST* ps);

    结论：数据结构建议不要直接访问数据，一定要通过函数接口访问（低耦合，高内聚）！！！

  • 相关阅读:
    高速电路设计----第三章
    NLP-Beginner：自然语言处理入门练习----task 2基于机器学习的文本分类
    AI大模型-流式处理 (以百度接口为例)
    setPreviewCallbackWithBuffer的出帧效率会变低
    光伏发电站远程监控组网解决方案
    【菜鸟教程】 C++学习笔记
    五十一、csrf跨站请求伪造和auth认证模块
    LeetCode 1277. 统计全为 1 的正方形子矩阵【动态规划】1613
    UT804数据秒数据提取
    【字符串】数组中的字符串匹配
  • 原文地址：https://blog.csdn.net/weixin_69283129/article/details/126596066