• 数据结构：6、栈

    一、栈的概念

    栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端
    称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
    压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
    出栈：栈的删除操作叫做出栈。出数据也在栈顶。

    如下图所示就是栈的进栈和出栈，全部代码附在文章末。

    二、栈的实现

    栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，所以这里就使用顺序表结构了。

     1、栈的初始化与销毁

    首先创建一个顺序表，因为栈的原理就是，后进先出，也就是相当于数组，最后一位一个个出去，而先进入的数据在数组的前面，所以就定义成顺序表.

    所以定义在初始化中，把容量和栈顶也就是capacity和top这两个变量，但是数组的表示一般都是指向下一位，例如：arr[0]就是第一位数据，所以top定义为0但是他指向的数据的下一位，销毁就是把存放数据的指针a释放，因为是连续的所以释放一次就行了，容量和栈顶赋值为0，代码如下。

    1. typedef int STDatetype;
    2.  
    3. typedef struct Stack
    4. {
    5. 	STDatetype* a;
    6. 	int top;
    7. 	int capacity;
    8. }ST;
    9.  
    10. void StackInit(ST* ps)
    11. {
    12. 	assert(ps);
    13. 	ps->a = NULL;
    14. 	ps->capacity = 0;
    15. 	ps->top = 0;
    16. }
    17.  
    18. void StackDestroy(ST* ps)
    19. {
    20. 	assert(ps);
    21. 	free(ps->a);
    22. 	ps->a = NULL;
    23. 	ps->capacity = ps->top = 0;
    24. }

    2、判断是否为空

    这个函数就是利用bool库函数的实现，当栈顶的数据top为0时就返回真，在外面使用也就是用个取反就可以了。

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

    3、进栈与出栈

    这个入栈的时候，需要先判定是否还有容量，也就是容量等于栈顶的时候就去申请空间，这里利用了三目运算符，当容量为0时赋值为4，不等于0直接乘上2，然利用realloc申请空间，然后把新的容量和地址分别赋给a和容量，realloc在地址为空时它相当于melloc这时可以运行测试下，测试代码和运行结果如下。

    这里是从1到6入栈，但是出栈是后一个个出，所以就是6 5 4 3 2 1，因为这里测试了下判断有用吗，也就是栈为空时不能删，会报错断言。

    1. // 入栈
    2. void StackPush(ST* ps, STDatetype data)
    3. {
    4. 	assert(ps);
    5. 	if (ps->capacity == ps->top)
    6. 	{
    7. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    8. 		ST* newnode = (ST*)realloc(ps->a, newcapacity * sizeof(STDatetype));
    9. 		if (newnode == NULL)
    10. 		{
    11. 			perror("recalloc fail");
    12. 			return;
    13. 		}
    14. 		ps->a = newnode;
    15. 		ps->capacity = newcapacity;
    16. 	}
    17. 	ps->a[ps->top] = data;
    18. 	ps->top++;
    19. }
    20.  
    21. // 出栈
    22. void StackPop(ST* ps)
    23. {
    24. 	assert(ps);
    25. 	assert(!StackEmpty(ps));
    26. 	ps->top--;
    27. }

    测试代码

    1. void TestStack1()
    2. {
    3. 	ST ST;
    4. 	int temp = 0;
    5. 	int size = 0;
    6. 	StackInit(&ST);
    7. 	StackPush(&ST, 1);
    8. 	StackPush(&ST, 2);
    9. 	StackPush(&ST, 3);
    10. 	StackPush(&ST, 4);
    11. 	StackPush(&ST, 5);
    12. 	StackPush(&ST, 6);
    13. 	temp=StackTop(&ST);
    14. 	StackPop(&ST);
    15. 	printf("%d ", temp);
    16. 	temp = StackTop(&ST);
    17. 	StackPop(&ST);
    18. 	printf("%d ", temp);
    19. 	temp = StackTop(&ST);
    20. 	StackPop(&ST);
    21. 	printf("%d ", temp);
    22. 	temp = StackTop(&ST);
    23. 	StackPop(&ST);
    24. 	printf("%d ", temp);
    25. 	temp = StackTop(&ST);
    26. 	StackPop(&ST);
    27. 	printf("%d ", temp);
    28. 	temp = StackTop(&ST);
    29. 	StackPop(&ST);
    30. 	printf("%d ", temp);
    31. 	temp = StackTop(&ST);
    32. 	StackPop(&ST);
    33. 	printf("%d ", temp);
    34. 	StackDestroy(&ST);
    35. }

     

    4、获取栈顶的元素与栈的元素个数

    差点忘了，上文中测试时，利用了这里才说的获取栈顶元素，因为获取一个删一个打印一下，这里就是获取元素的个数和获取栈顶元素，因为当数据为空时，有效元素个数为0，这里测试就是打印，然后当元素为空时，再去获取就会报错。

    1. // 获取栈顶元素
    2. STDatetype StackTop(ST* ps)
    3. {
    4. 	assert(ps);
    5. 	assert(!StackEmpty(ps));
    6. 	return ps->a[ps->top-1];
    7. }
    8.  
    9. // 获取栈中有效元素个数
    10. int StackSize(ST* ps)
    11. {
    12. 	assert(ps);
    13. 	assert(!StackEmpty(ps));
    14. 	return ps->top;
    15. }

    测试代码

    1. void TestStack2()
    2. {
    3. 	ST ST;
    4. 	int temp = 0;
    5. 	int size = 0;
    6. 	StackInit(&ST);
    7. 	StackPush(&ST, 1);
    8. 	StackPush(&ST, 2);
    9. 	StackPush(&ST, 3);
    10. 	StackPush(&ST, 4);
    11. 	StackPush(&ST, 5);
    12. 	StackPush(&ST, 6);
    13. 	size = StackSize(&ST);
    14. 	printf("\n%d\n", size);
    15. 	temp = StackTop(&ST);
    16. 	StackPop(&ST);
    17. 	printf("%d ", temp);
    18. 	temp = StackTop(&ST);
    19. 	StackPop(&ST);
    20. 	printf("%d ", temp);
    21. 	temp = StackTop(&ST);
    22. 	StackPop(&ST);
    23. 	printf("%d ", temp);
    24. 	size = StackSize(&ST);
    25. 	printf("\n%d\n", size);
    26. 	temp = StackTop(&ST);
    27. 	StackPop(&ST);
    28. 	printf("%d ", temp);
    29. 	temp = StackTop(&ST);
    30. 	StackPop(&ST);
    31. 	printf("%d ", temp);
    32. 	temp = StackTop(&ST);
    33. 	StackPop(&ST);
    34. 	printf("%d ", temp);
    35. 	size = StackSize(&ST);
    36. 	printf("\n%d\n", size);
    37. 	StackDestroy(&ST);
    38. }

     

    三、代码

    ST.h

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6.  
    7. typedef int STDatetype;
    8.  
    9. typedef struct Stack
    10. {
    11. 	STDatetype* a;
    12. 	int top;
    13. 	int capacity;
    14. }ST;
    15.  
    16. // 初始化栈
    17. void StackInit(ST* ps);
    18. // 入栈
    19. void StackPush(ST* ps, STDatetype data);
    20. // 出栈
    21. void StackPop(ST* ps);
    22. // 获取栈顶元素
    23. STDatetype StackTop(ST* ps);
    24. // 获取栈中有效元素个数
    25. int StackSize(ST* ps);
    26. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
    27. bool StackEmpty(ST* ps);
    28. // 销毁栈
    29. void StackDestroy(ST* ps);

    ST.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include "ST.h"
    4.  
    5. // 初始化栈
    6. void StackInit(ST* ps)
    7. {
    8. 	assert(ps);
    9. 	ps->a = NULL;
    10. 	ps->capacity = 0;
    11. 	ps->top = 0;
    12. }
    13.  
    14. // 入栈
    15. void StackPush(ST* ps, STDatetype data)
    16. {
    17. 	assert(ps);
    18. 	if (ps->capacity == ps->top)
    19. 	{
    20. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    21. 		ST* newnode = (ST*)realloc(ps->a, newcapacity * sizeof(STDatetype));
    22. 		if (newnode == NULL)
    23. 		{
    24. 			perror("recalloc fail");
    25. 			return;
    26. 		}
    27. 		ps->a = newnode;
    28. 		ps->capacity = newcapacity;
    29. 	}
    30. 	ps->a[ps->top] = data;
    31. 	ps->top++;
    32. }
    33.  
    34. // 出栈
    35. void StackPop(ST* ps)
    36. {
    37. 	assert(ps);
    38. 	assert(!StackEmpty(ps));
    39. 	ps->top--;
    40. }
    41.  
    42. // 获取栈顶元素
    43. STDatetype StackTop(ST* ps)
    44. {
    45. 	assert(ps);
    46. 	assert(!StackEmpty(ps));
    47. 	return ps->a[ps->top-1];
    48. }
    49.  
    50. // 获取栈中有效元素个数
    51. int StackSize(ST* ps)
    52. {
    53. 	assert(ps);
    54. 	assert(!StackEmpty(ps));
    55. 	return ps->top;
    56. }
    57.  
    58. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
    59. bool StackEmpty(ST* ps)
    60. {
    61. 	assert(ps);
    62. 	return ps->top == 0;
    63. }
    64.  
    65. // 销毁栈
    66. void StackDestroy(ST* ps)
    67. {
    68. 	assert(ps);
    69. 	free(ps->a);
    70. 	ps->a = NULL;
    71. 	ps->capacity = ps->top = 0;
    72. }

    test.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include "ST.h"
    4.  
    5. void TestStack1()
    6. {
    7. 	ST ST;
    8. 	int temp = 0;
    9. 	int size = 0;
    10. 	StackInit(&ST);
    11. 	StackPush(&ST, 1);
    12. 	StackPush(&ST, 2);
    13. 	StackPush(&ST, 3);
    14. 	StackPush(&ST, 4);
    15. 	StackPush(&ST, 5);
    16. 	StackPush(&ST, 6);
    17. 	temp=StackTop(&ST);
    18. 	StackPop(&ST);
    19. 	printf("%d ", temp);
    20. 	temp = StackTop(&ST);
    21. 	StackPop(&ST);
    22. 	printf("%d ", temp);
    23. 	temp = StackTop(&ST);
    24. 	StackPop(&ST);
    25. 	printf("%d ", temp);
    26. 	temp = StackTop(&ST);
    27. 	StackPop(&ST);
    28. 	printf("%d ", temp);
    29. 	temp = StackTop(&ST);
    30. 	StackPop(&ST);
    31. 	printf("%d ", temp);
    32. 	temp = StackTop(&ST);
    33. 	StackPop(&ST);
    34. 	printf("%d ", temp);
    35. 	temp = StackTop(&ST);
    36. 	StackPop(&ST);
    37. 	printf("%d ", temp);
    38. 	StackDestroy(&ST);
    39. }
    40.  
    41. void TestStack2()
    42. {
    43. 	ST ST;
    44. 	int temp = 0;
    45. 	int size = 0;
    46. 	StackInit(&ST);
    47. 	StackPush(&ST, 1);
    48. 	StackPush(&ST, 2);
    49. 	StackPush(&ST, 3);
    50. 	StackPush(&ST, 4);
    51. 	StackPush(&ST, 5);
    52. 	StackPush(&ST, 6);
    53. 	size = StackSize(&ST);
    54. 	printf("\n%d\n", size);
    55. 	temp = StackTop(&ST);
    56. 	StackPop(&ST);
    57. 	printf("%d ", temp);
    58. 	temp = StackTop(&ST);
    59. 	StackPop(&ST);
    60. 	printf("%d ", temp);
    61. 	temp = StackTop(&ST);
    62. 	StackPop(&ST);
    63. 	printf("%d ", temp);
    64. 	size = StackSize(&ST);
    65. 	printf("\n%d\n", size);
    66. 	temp = StackTop(&ST);
    67. 	StackPop(&ST);
    68. 	printf("%d ", temp);
    69. 	temp = StackTop(&ST);
    70. 	StackPop(&ST);
    71. 	printf("%d ", temp);
    72. 	temp = StackTop(&ST);
    73. 	StackPop(&ST);
    74. 	printf("%d ", temp);
    75. 	size = StackSize(&ST);
    76. 	printf("\n%d\n", size);
    77. 	StackDestroy(&ST);
    78. }
    79.  
    80. void main()
    81. {
    82. 	TestStack2();
    83. 	return 0;
    84. }

  • 相关阅读:
    C语言实现AES加密算法的示例代码
    操作系统--赵XX
    直播邀请函 | 第12届亚洲知识产权营商论坛：共建创新价值 开拓崭新领域
    【刷爆LeetCode】七月算法集训（29）分而治之
    软件测试基本常识
    Java并发编程—线程详解
    【ASE入门学习】ASE入门系列十六——色相与自动变色荧光棒
    java计算机毕业设计员工信息管理系统源码+mysql数据库+系统+lw文档+部署
    Python 中的 Urljoin 简介
    海外动态IP代理可以用来批量注册邮箱吗？
  • 原文地址：https://blog.csdn.net/weixin_64257568/article/details/136590657