当前位置:   article > 正文

【数据结构】顺序栈的基本操作:出栈、入栈、取栈顶元素、输出所有栈中元素、括号匹配题目_元素入栈出栈怎么写

元素入栈出栈怎么写

概念描述

栈是限定仅在表位进行插入或删除操作的线性表。栈的表尾称为栈顶,表头称为栈底。不含元素的栈称为空栈。

左图为栈的示意图,右图为用铁路调度表示栈。

如下是入栈至栈满再进行出栈的过程示意图。值得注意的是,栈满后,top指针指向的不是顶端元素,而是顶端的下一个位置。

基本操作

构造一个空栈S

在正式开始前,照例需要定义一些如下的常量

  1. #define STACK_INIT_SIZE 100//存储空间初始分配量
  2. #define STACKINCREMENT 10//存储空间分配增量
  3. #define TRUE 1
  4. #define ERROR 0
  5. #define OVERFLOW -2
  6. typedef char SElemType;
  7. tyoedef int Status;
  1. typedef struct{
  2. SElemType *base;//栈底指针.在栈构造之前和销毁之后,base的值为NULL
  3. SElemType *top;//栈顶指针
  4. int stacksize;//当前已分配的存储空间,初始值一般为STACK_INIT_SIZE,不够时再以STACKINCREMENT为单位扩大
  5. }SqStack;

在顺序栈中,base指针始终指向栈底元素,栈不存在的条件为base=NULLtop指针初值指向栈底,栈的条件为base==top。栈不空时,top指向(栈顶+1)。也就是说,在正常情况下,S.top 是不指向任何元素的。(top-base)的值即为栈中元素的个数,也即栈的长度。当top-base==stacksize时,说明栈满。此时若想进行入栈操作,需要扩充分配存储空间。

判空

  1. Status StackEmpty(SqStack S)
  2. {
  3. if(!S.base) return TRUE;
  4. else return FALSE;
  5. }

构造一个空栈

  1. Status InitStack(SqStack &S)
  2. {
  3. S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
  4. if(!S.base) exit(OVERFLOW);
  5. S.top=S.base;
  6. S.stacksize=STACK_INIT_SIZE;
  7. return OK;
  8. }

若栈不存在,分配空间时发生上溢出错误而退出。

入栈

在入栈、出栈、取栈顶元素的函数中,不存在分配空间的问题,是return ERROR而不是 exit(OVERFLOW)

  1. Status Push(SqStack& S, SEIemType e)//入栈
  2. {
  3. if (S.top - S.base >= S.stacksize) return ERROR;
  4. *S.top = e;//注意S.top是指针型变量
  5. S.top++;//先赋值,再加一
  6. return OK;
  7. }

出栈

  1. Status (SqStack &S)
  2. {
  3. if(S.top==S.base) return ERROR;
  4. S.top--;
  5. e=*(S.top);
  6. return OK;
  7. }

值得注意的是,出栈后,元素e并未从栈中删除。改变的只是top指针的位置。虽然e还在栈中,但栈长已经改变,e的原位置此后可以被其它值覆盖。

取栈顶元素

取栈顶元素就是“top指针位置不变”版的“出栈”。博主初学时没意识到这一点,以为出栈就是删除元素,所以构造了一个很复杂的取栈顶元素函数。为避免误导,就不放在这里了。

  1. Status(SqStack S,SElemType)
  2. {
  3. if(S.top==S.base) return ERROR;
  4. e=*(S.top-1);//top指针位置不变
  5. return OK;
  6. }

输出栈中所有元素

和取栈顶元素同理,在不移动指针位置的情况下输出元素。若采用for循环,需要先求栈长。一般使用while循环。

  1. Status PrintStack(SqStack S)
  2. {
  3. int i=0;
  4. SElemType *s;
  5. s=S.base;//注意!顺序栈从底部开始向上存储,顺序输出是从S.base开始
  6. //并且,如果想做逆序输出,while循环条件应为s!=S.base-1
  7. while(s!=S.top)
  8. {
  9. printf("%c\n",*s);
  10. s++;
  11. i++;
  12. }
  13. printf("已输出栈中%d个元素",i);
  14. return OK;
  15. }
  1. Status PrintStack(SqStack S)
  2. {
  3. int a=S.top-S.base;
  4. if(S.base==S.top) return ERROR;
  5. int i;
  6. for(i=1;i<=a;i++)
  7. printf("%c\n",*(S.top-a));
  8. printf("已输出栈中%d个元素",a);
  9. return OK;
  10. }

括号匹配

题干描述

由键盘输入一系列左括号和右括号,判断这些括号是否成功配对。一旦发现不配对的括号,立刻退出程序并说明原因。如:( { [ ] [ ] } )是匹配成功,而((]是由于括号不匹配而失败,{ ( [ ] )是因为左括号多余而失败,( { } ) ]是因为右括号多余而失败。

题目分析

代码(含分析)

  1. Status March_Brackets(SqStack& S)
  2. {
  3. char ch;//输入一连串字符(括号),以回车结束.起初,括号都存储在ch中,栈S为空栈.
  4. SElemType* s;
  5. s = S.top-1;//s指向栈顶元素
  6. printf("请输入字符:\n");
  7. ch = getchar();//输入括号,进入循环
  8. while (ch != '\n')//循环接收括号字符以回车为结束符,每输入一个括号,就进行一次判断。
  9. {
  10. if (ch =='(' || ch == '[' || ch == '{') //如果ch是左括号,入栈.栈中存放左括号,有匹配的右括号就出栈.若全部匹配成功,栈空。
  11. Push(S, ch); //入栈
  12. if (ch == ')')//输入字符为右括号
  13. {
  14. if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; }
  15. /*在Pop函数中, 若返回值为0, 说明是空栈.这有两种情况:1,还未输入左括号,第一个输入的就是右括号;
  16. 2,之前输入的左、右括号都已成功匹配,左括号已全部出栈*/
  17. else if (*s != '(') { printf("右括号与左括号不匹配\n"); return ERROR; }
  18. /*最后输入的左括号不是小括号,与输入的右小括号不匹配*/
  19. }
  20. else if (ch == ']')
  21. {
  22. if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; }
  23. else if (*s != '[') { printf("右括号与左括号不匹配\n"); return ERROR; }
  24. }
  25. else if (ch == '}')
  26. {
  27. if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; }
  28. else if (*s != '{') { printf("右括号与左括号不匹配\n"); return ERROR; }
  29. }
  30. ch = getchar();
  31. }//循环结束,说明输入的右括号都有预支品牌的左括号.但这不意味着匹配成功!!还有左括号多余的可能。
  32. if (S.top != S.base)//栈不空,说明有左括号未出栈,未匹配
  33. {
  34. printf("左括号多余,不匹配\n");
  35. return ERROR;
  36. }
  37. else//栈空,说明左括号已全部出栈,匹配成功
  38. {
  39. printf("匹配完整,成功退出\n");
  40. return OK;
  41. }
  42. }

上机实现

完整代码

经高手指点:由于getchar的一些特性,建议只执行一次括号判断函数。不要在主函数中反复执行它。

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef char SElemType;
  4. typedef int Status;
  5. constexpr auto ERROR = 0;
  6. constexpr auto OK = 1;
  7. constexpr auto OVERFLOW = -2;
  8. constexpr auto STACK_MAX_SIZE = 100;
  9. typedef struct {
  10. SElemType* base;
  11. SElemType* top;
  12. int stacksize;
  13. }SqStack;
  14. Status InitStack(SqStack& S)//建立空顺序栈
  15. {
  16. S.stacksize = STACK_MAX_SIZE;
  17. S.base = (SElemType*)malloc(STACK_MAX_SIZE * sizeof(SElemType));
  18. if (!S.base) exit(OVERFLOW);
  19. S.top = S.base;
  20. return OK;
  21. }
  22. Status Push(SqStack& S, SElemType e)//入栈
  23. {
  24. if (S.top - S.base >= S.stacksize) exit(OVERFLOW);
  25. *S.top = e;//注意S.top是指针型变量
  26. S.top++;//先赋值,再加一
  27. return OK;
  28. }
  29. Status Pop(SqStack& S, SElemType& e)//出栈
  30. {
  31. if (S.base == S.top) return ERROR;
  32. S.top--;//注意S.top是指针型变量
  33. e = *S.top;//先减一,再赋值
  34. return OK;
  35. }
  36. Status GetTop(SqStack S, SElemType &e)//获取栈顶元素
  37. {
  38. if (S.top == S.base) return ERROR;
  39. e = *(S.top - 1);//top指针位置不变
  40. return OK;
  41. }
  42. Status PrintStack(SqStack S)//输出栈所有元素
  43. {
  44. if (S.top == S.base) return ERROR;
  45. int i = 0;
  46. SElemType* s;
  47. s = S.base;
  48. while (s != S.top)
  49. {
  50. printf("%c\n", *s);
  51. i++;
  52. s++;
  53. }
  54. printf("已输出栈中%d个元素", i);
  55. return OK;
  56. }
  57. Status March_Brackets(SqStack& S)
  58. {
  59. char ch;//输入一连串字符(括号),以回车结束.起初,括号都存储在ch中,栈S为空栈.
  60. SElemType* s;
  61. s = S.top-1;//s指向栈顶元素
  62. printf("请输入字符:\n");
  63. ch = getchar();//输入括号,进入循环
  64. while (ch != '\n')//循环接收括号字符以回车为结束符,每输入一个括号,就进行一次判断。
  65. {
  66. if (ch =='(' || ch == '[' || ch == '{') //如果ch是左括号,入栈.栈中存放左括号,有匹配的右括号就出栈.若全部匹配成功,栈空。
  67. Push(S, ch); //入栈
  68. if (ch == ')')//输入字符为右括号
  69. {
  70. if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; }
  71. /*在Pop函数中, 若返回值为0, 说明是空栈.这有两种情况:1,还未输入左括号,第一个输入的就是右括号;
  72. 2,之前输入的左、右括号都已成功匹配,左括号已全部出栈*/
  73. else if (*s != '(') { printf("右括号与左括号不匹配\n"); return ERROR; }
  74. /*最后输入的左括号不是小括号,与输入的右小括号不匹配*/
  75. }
  76. else if (ch == ']')
  77. {
  78. if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; }
  79. else if (*s != '[') { printf("右括号与左括号不匹配\n"); return ERROR; }
  80. }
  81. else if (ch == '}')
  82. {
  83. if ((Pop(S, *s) == 0)) { printf("右括号多余,不匹配\n"); return ERROR; }
  84. else if (*s != '{') { printf("右括号与左括号不匹配\n"); return ERROR; }
  85. }
  86. ch = getchar();
  87. }//循环结束,说明输入的右括号都有预支品牌的左括号.但这不意味着匹配成功!!还有左括号多余的可能。
  88. if (S.top != S.base)//栈不空,说明有左括号未出栈,未匹配
  89. {
  90. printf("左括号多余,不匹配\n");
  91. return ERROR;
  92. }
  93. else//栈空,说明左括号已全部出栈,匹配成功
  94. {
  95. printf("匹配完整,成功退出\n");
  96. return OK;
  97. }
  98. }
  99. int main(void)
  100. {
  101. SqStack S; int i;
  102. char e; char f; char k;
  103. InitStack(S);
  104. printf("请向栈中输入字符\n");
  105. for (i = 0; i < 7; i++)
  106. {
  107. scanf_s("%c", &e);
  108. Push(S, e);//入栈
  109. }
  110. printf("已初始化栈如下\n");
  111. PrintStack(S);
  112. GetTop(S, f);//获取栈顶元素
  113. printf("栈顶元素为\n");
  114. putchar(f);
  115. printf("删除栈顶元素\n");
  116. Pop(S, k);//出栈
  117. printf("更新栈如下\n");
  118. PrintStack(S);
  119. printf("下面进入括号匹配\n");
  120. SqStack B;
  121. InitStack(B);
  122. March_Brackets(B);
  123. return 0;
  124. }

运行结果

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

闽ICP备14008679号