[关闭]
@coder-pig 2019-05-31T06:26:04.000000Z 字数 3627 阅读 625

小猪的数据结构辅助教程——3.1 栈与队列中的顺序栈

数据结构


本节学习路线图与学习要点

学习要点

1.栈与队列的介绍,栈顶,栈底,入栈,出栈的概念
2.熟悉顺序栈的特点以及存储结构
3.掌握顺序栈的基本操作的实现逻辑
4.掌握顺序栈的经典例子:进制变换的实现逻辑


1.栈与队列的概念:

嗯,本节要进行讲解的就是栈 + 顺序结构 = 顺序栈
可能大家对栈的概念还是很模糊,我们找个常见的东西来拟物化~
不知道大家喜欢吃零食不——"桶装薯片"就可以用来演示栈!

生产的时候,往桶里放一片片薯片的过程,可以看成往栈里放元素(进栈),
吃薯片的时候,一片片取出薯片的过程,可以看成取出栈里的元素(出栈)
这里我们假设

我们下面来通过模拟往桶里放入薯片以及取出薯片的流程,来体会下栈的后进先出的特点!
假设薯片桶的容量是5,每次只放或取一块薯片!

放薯片

...
好的,薯片桶已经装满了!接着等吃货们开吃~

取薯片


嗯,薯片就这样吃完了~

流程非常简单,如果还是觉得不能理解,直接到超市买一桶薯片吧,自己实物
模拟模拟就知道了!又有借口买垃圾食品了~

吃货小贴士:
市面上很多的桶装薯片都不是马铃薯切片,而是马铃薯粉 + 实用淀粉,而袋装的基本
都是切片,买的时候可以自己看下配料表哦~


2.栈中的名词以及概念解析:

有了上面的桶装薯片的例子,相信再讲栈的一些名词,大家就不会一头雾水了~
入栈(Push):又叫压栈,栈的插入操作;
出栈(Pop):又叫弹栈,栈的删除操作;
我们上面也说了,栈和队列都是操作受限的线性表,操作受限表现在:
我们仅能够在表尾进行插入和删除操作
而线性表的表头和表尾分别对应的栈底(Bottom)栈顶(Top)
栈顶始终指向新元素的存放位置!栈底指向表头元素!
还有一点:栈在使用过程中所需的最大空间大小很难估计,所以一般
是先为栈分配一个基本容量,在使用过程中,当栈的空间不够试用再
逐段扩大!

名词术语差不多,接下来就到顺序栈的存储结构了!


3.顺序栈的存储结构

  1. typedef struct
  2. {
  3. ElemType *base; //栈底指针,始终指向栈底,如果为null说明栈不存在
  4. ElemType *top; //栈顶指针,当top == base时,为空栈;
  5. int stackSize; //当前已分配的存储空间,以元素为单位
  6. }SqStack;

另外,top - base等于当前栈中的元素个数!
非空栈的栈顶指针始终在栈顶元素的下一个位置上!


4.顺序栈的基本操作的代码实现

代码都很简单,就不过多的解释了~

1)构造空栈

  1. void InitStack(SqStack S)
  2. {
  3. S ->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
  4. if(!S->base)exit(ERROR);
  5. S ->top = S ->base; //栈顶指向栈底
  6. S ->stacksize = STACK_INIT_SIZE;
  7. }

2)将栈置空

  1. void ClearStack(SqStack S)
  2. {
  3. S ->top = S ->base; //栈顶指向栈底
  4. }

3)判断是否为空栈

  1. Status StackEmpty(SqStack S)
  2. {
  3. return S ->top == S ->base?TRUE:FALSE;
  4. }

4)销毁栈

  1. void DestoryStack(SqStack S)
  2. {
  3. free(S ->base); //释放栈空间
  4. S ->top = S ->base = NULL; //将栈顶和栈底设置为NULL
  5. S ->stacksize = 0; //存储空间设置为0
  6. }

5)获得栈中的元素个数

  1. int StackLength(SqStack S)
  2. {
  3. return S ->top - S ->base;
  4. }

6)获得栈顶元素

  1. Status GetTop(SqStack S,SElemType *e)
  2. {
  3. if(S ->top > S ->base)
  4. {
  5. e = S ->top - 1;
  6. return OK;
  7. }else{
  8. return ERROR;
  9. }
  10. }

7)往栈中插入元素(压栈)

  1. void PushStack(SqStack S,SElemType e)
  2. {
  3. //判断当前栈容量是否满了,满了需要增加空间
  4. if(S ->top - S ->base == S ->stacksize)
  5. {
  6. S ->base = (SElemType *)realloc(S ->base,
  7. (S ->stacksize + STACK_INCREMENT)*sizeof(SElemType));
  8. if(!S->base)exit(ERROR);
  9. S ->top = S ->base + S ->stacksize; //修改栈顶指针指向新的栈顶
  10. S ->stacksize += STACK_INCREMENT; //更新容量
  11. }
  12. *(S ->top ++) = e;
  13. }

8)弹出栈中的元素

  1. Status PopStack(SqStack S,SElemType e)
  2. {
  3. if(S ->top == S ->base)return ERROR; //栈为空
  4. e = *(--S ->top); //栈顶元素值付给e,栈顶指针下移
  5. return OK;
  6. }

9)遍历栈中的元素

  1. void StackTraverse(SqStack S,void *visit(SElemType))
  2. {
  3. //从栈底开始到栈顶
  4. while(S ->top > S ->base)
  5. visit(*(S ->base ++));
  6. printf("\n");
  7. }

5.顺序栈应用实例:进制转换

进制转换相信大家肯定不会陌生,应该也写过这样的程序~
而本节猪脚是栈,所以我们肯定要用栈来解决这个进制转换的问题!
下面我们利用顺序栈来写下十进制转各种进制的简单例子~

运行结果

代码实现

  1. #include <stdio.h>
  2. #define STACK_INIT_SIZE 10 //存储空间的初始分配量
  3. #define STACK_INCREMENT 2 //分配增量
  4. #define OK 1
  5. #define ERROR 0
  6. #define TRUE 1
  7. #define FALSE 0
  8. typedef int SElemType;
  9. typedef int Status;
  10. typedef struct SqStack
  11. {
  12. SElemType *base; //栈底指针变量
  13. SElemType *top; //栈顶指针变量
  14. int stacksize; //当前可试用的最大容量
  15. }SqStack;
  16. //初始化栈
  17. void InitStack(SqStack *S)
  18. {
  19. S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
  20. if( !S->base )exit(0);
  21. S->top = S->base;
  22. S->stacksize = STACK_INIT_SIZE;
  23. }
  24. //获取栈的当前长度
  25. int StackLength(SqStack S)
  26. {
  27. return (S.top - S.base);
  28. }
  29. //入栈
  30. void PushStack(SqStack *S, SElemType e)
  31. {
  32. if(S->top - S->base >= S->stacksize )
  33. {
  34. S->base = (SElemType *)realloc(S->base, (S->stacksize + STACK_INCREMENT) * sizeof(SElemType));
  35. if( !S->base )exit(0);
  36. S->top = S->base + S->stacksize;
  37. S->stacksize = S->stacksize + STACK_INCREMENT;
  38. }
  39. *(S->top) = e;
  40. S->top++;
  41. }
  42. //出栈
  43. void PopStack(SqStack *S, SElemType *e)
  44. {
  45. if(S->top == S->base )return;
  46. *e = *--(S->top);
  47. }
  48. int main()
  49. {
  50. SqStack s;
  51. SElemType n,m,e;
  52. InitStack(&s);
  53. printf("请输入要转换的进制:n >= 0\n");
  54. scanf("%d",&n);
  55. printf("请输入要进行转换的十进制数:\n");
  56. scanf("%d",&m);
  57. while(m)
  58. {
  59. PushStack(&s,m % n);
  60. m = m / n;
  61. }
  62. printf("输出十进制转%d进制后的值:\n",n);
  63. while(StackLength(s))
  64. {
  65. PopStack(&s,&e);
  66. if(n == 16)
  67. {
  68. printf("%X ",e); //输出十六进制的结果
  69. }
  70. else printf("%d ",e);
  71. }
  72. printf("\n\n");
  73. return 0;
  74. }

代码很简单,无非是求余,然后把求余结果入栈;急着除以进制数,继续求余,直到等于0,
然后是元素出栈~


6.本节实例代码下载:

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/Stack/Stack1.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/Stack/Stack2.c

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注