• 轻松学会结构栈


    目录

    栈的概念

    栈的实现 

    Stack.h

    Stack.c 

    first.c


    栈的概念

            栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

            压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
            出栈:栈的删除操作叫做出栈。出数据也在栈顶。

    栈的实现 

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

    Stack.h

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. //typedef int STDataType;
    7. //#define N 10
    8. //typedef struct Stack
    9. //{
    10. // STDataType a[N];
    11. // int top;
    12. //}ST;
    13. typedef int STDataType;
    14. typedef struct Stack
    15. {
    16. STDataType* a;
    17. int top;
    18. int capacity;
    19. }ST;
    20. void StackInit(ST* ps);
    21. void StackDestroy(ST* ps);
    22. void StackPush(ST* ps);
    23. void StackPop(ST* ps);
    24. int StackSize(ST* ps);
    25. bool StackEmpty(ST* ps);
    26. STDataType StackTop(ST* ps);

    Stack.c 

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"Stack.h"
    3. void StackInit(ST* ps)
    4. {
    5. assert(ps);
    6. ps->a = NULL;
    7. ps->top = 0;
    8. ps->capacity = 0;
    9. }
    10. void StackDestroy(ST* ps)
    11. {
    12. assert(ps);
    13. free(ps->a);
    14. ps->a = NULL;
    15. ps->top = ps->capacity = 0;
    16. }
    17. void StackPush(ST* ps, STDataType x)
    18. {
    19. assert(ps);
    20. if (ps->top == ps->capacity)
    21. {
    22. int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    23. STDataType* tmp =(STDataType*)realloc(ps->a,sizeof(STDataType) * newCapacity);
    24. if (tmp == NULL)
    25. {
    26. printf("realloc fail\n");
    27. exit(-1);
    28. }
    29. ps->a = tmp;
    30. ps->capacity = newCapacity;
    31. }
    32. ps->a[ps->top] = x;
    33. ps->top++;
    34. }
    35. void StackPop(ST* ps)
    36. {
    37. assert(ps);
    38. assert(!StackEmpty(ps));
    39. ps->top--;
    40. }
    41. STDataType StackTop(ST* ps)
    42. {
    43. assert(ps);
    44. assert(!StackEmpty(ps));
    45. return ps->a[ps->top - 1];
    46. }
    47. bool StackEmpty(ST* ps)
    48. {
    49. assert(ps);
    50. return ps->top == 0;
    51. }
    52. int StackSize(ST* ps)
    53. {
    54. assert(ps);
    55. return ps->top;
    56. }

    first.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"Stack.h"
    3. void meau()
    4. {
    5. printf("*****************************************\n");
    6. printf("1、数据入栈 2、数据出栈\n");
    7. printf("3、查看栈顶数据 4、栈的长度\n");
    8. printf("5、全部出栈\n");
    9. printf("*****************************************\n");
    10. }
    11. int main()
    12. {
    13. ST st;
    14. StackInit(&st);
    15. int option;
    16. int num;
    17. do {
    18. meau();
    19. if (scanf("%d", &option) == EOF)
    20. {
    21. printf("scanf输入错误\n");
    22. exit(0);
    23. break;
    24. }
    25. switch (option)
    26. {
    27. case 1:
    28. {
    29. printf("请输入你要入栈的数据\n");
    30. scanf("%d", &num);
    31. StackPush(&st, num);
    32. break;
    33. }
    34. case 2:
    35. {
    36. printf("元素%d完成出栈\n", StackTop(&st));
    37. StackPop(&st);
    38. break;
    39. }
    40. case 3:
    41. {
    42. printf("元素%d在栈顶\n", StackTop(&st));
    43. break;
    44. }
    45. case 4:
    46. {
    47. printf("栈的长度为%d\n", StackSize(&st));
    48. break;
    49. }
    50. case 5:
    51. {
    52. printf("全部出栈\n");
    53. while (!StackEmpty(&st))
    54. {
    55. printf("%d\n", StackTop(&st));
    56. StackPop(&st);
    57. }
    58. break;
    59. }
    60. default:
    61. exit(-1);
    62. break;
    63. }
    64. } while (option != -1);
    65. StackDestroy(&st);
    66. return 0;
    67. }

     栈的选择题

    1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出
    栈的顺序是( )。
            A 12345ABCDE
            B EDCBA54321
            C ABCDE12345
            D 54321EDCBA
    2.若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
            A 1,4,3,2
            B 2,3,4,1
            C 3,1,4,2
            D 3,4,2,1

    答案 

            1.B
            2.C

  • 相关阅读:
    linux定时删除服务器日志
    酷早报:6月23日Web3加密行业每日新闻汇总
    关于数据权限的设计
    商务社交中为何电子名片这么火?都在使用哪一款免费的电子名片?
    SpringCloud&Alibaba
    windows下安装protocol buffer
    【定时功能】消息的定时发送-基于RocketMQ
    Abbexa丨Abbexa动物组织 PCR 试剂盒提取说明书
    PC防锁屏定时工具
    航空专场 | 无人机设计仿真流程讲解与案例实操
  • 原文地址:https://blog.csdn.net/qq_51581716/article/details/127731288