栈的顺序存储实现
栈的顺序存储也称为顺序栈,它利用一组地址连续的存储单元,依次存放自栈底到栈顶的元素,同时附设栈顶标识top来指示栈顶元素在顺序栈中的位置。向顺序栈中插入元素时,其过程如图1所示。
图1 向顺序栈中插入元素
由图1可知,向栈中插入元素时,需先使top指针指向栈顶后面的空位,然后进行赋值。删除栈中元素时,只将top向下移动,指示到新的栈顶元素,删除过程如图2所示。
图2 顺序栈弹栈
由图2可知,弹栈是将top移动,指示到新的栈顶元素。原来的栈顶元素依然存在与存储单元中,但无法再通过栈进行访问。
在这个过程中,有一点需要注意:不管栈的示例图如何画(在图3-2中,栈是开口向上,在图3-3与图3-4中,栈是开口向右,当然读者也可以将其开口向下或者开口向左),都是为了更清晰的描述问题,其存储原理是一样的,这一点读者不可混淆。学习其原理后,下面我们来实现一个顺序栈,此顺序栈所具备的功能如下:
● 顺序栈的初始化。
● 判断栈是否为空。
● 获取栈顶元素。
● 弹栈、压栈。
● 销毁栈。
然后在测试文件main.c中完成此顺序栈的测试,具体如例1所示。
例1
seqstack.h //头文件
1 #ifndef _SEQSTACK_H_
2 #define _SEQSTACK_H_
3
4 #define MAXSIZE 1024
5 #define INFINITY 65535
6 typedef struct
7 {
8 int data[MAXSIZE]; //在结构中定义一个数组
9 int top; //指示栈顶元素,在数组中相当于索引
10 }SeqStack;
11
12 void InitStack(SeqStack* stack); //初始化栈
13 int IsEmpty(SeqStack* stack); //判断栈是否为空
14 int SeqStack_Top(SeqStack* stack); //返回栈顶元素
15 int SeqStack_Pop(SeqStack* stack); //弹出栈顶元素
16 void SeqStack_Push(SeqStack* stack, int val); //将元素val压入栈中
17 void SeqStack_Destory(SeqStack* stack); //销毁栈
18
19 #endif
seqstack.c //函数实现文件
20 #include "seqstack.h"
21
22 void InitStack(SeqStack* stack) //初始化栈
23 {
24 stack->top = -1;
25 }
26
27 int IsEmpty(SeqStack* stack) //判断栈是否为空
28 {
29 if (stack->top == -1)
30 return 1;
31 return 0;
32 }
33
34 int SeqStack_Top(SeqStack* stack) //返回栈顶元素
35 {
36 if (!IsEmpty(stack))
37 return stack->data[stack->top];
38 return INFINITY; //只是作个简单标识,有可能栈顶元素也为-1;
39 }
40
41 int SeqStack_Pop(SeqStack* stack) //弹出栈顶元素
42 {
43 if (!IsEmpty(stack))
44 return stack->data[stack->top--]; //弹出一个元素后,top要减1
45 return INFINITY;
46 }
47
48 void SeqStack_Push(SeqStack* stack, int val) //将元素val压入栈中
49 {
50 if (stack->top >= MAXSIZE - 1) //栈已满
51 return;
52 stack->top++; //增加元素后,top要加1
53 stack->data[stack->top] = val; //将val元素存到数组中
54 }
55
56 void SeqStack_Destory(SeqStack* stack) //销毁栈
57 {
58 if (!IsEmpty(stack))
59 free(stack);
60 }
main.c //测试文件
61 #include <stdio.h>
62 #include <stdlib.h>
63 #include "seqstack.h"
64
65 int main()
66 {
67 srand((unsigned)time(0)); //以时间为种子产生随机
68 SeqStack stack; //创建一个顺序栈
69 InitStack(&stack); //初始化栈
70
71 //向栈中添加元素
72 for (int i = 0; i < 50; i++)
73 {
74 SeqStack_Push(&stack, rand() % 1000); //添加的是随机产生的数
75 }
76
77 //获取栈顶元素
78 printf("栈顶元素:%d\n", SeqStack_Top(&stack));
79
80 //打印栈中元素
81 printf("栈中的元素:");
82 for (int i = 0; i < 50; i++)
83 {
84 if (i % 5 == 0)
85 printf("\n"); //每5个元素一行
86 printf("%d ", SeqStack_Pop(&stack)); //依次将栈顶元素弹出
87 }
88
89 printf("\n");
90
91 system("pause");
92 return 0;
93 }
运行结果如图3所示。
图3 例1运行结果
在例1的实现中,用一个struct来定义栈。在此结构体中定义了一个数组data来存放元素,同时定义了top来指示栈顶元素。
代码22-25行初始化栈。栈中数据索引从0开始,当top值为-1时栈为空。
代码27-32行是判断栈是否为空,其判断条件为top值是否为-1,如果top值为-1,则栈为空;如果top值不为-1,证明栈中有元素,栈不为空。
代码34-39行是读取栈顶元素,就是读取数组data中索引为top的元素,因此该元素为lstack->data[lstack->top]。
代码41-46行是将栈顶元素弹出,栈顶元素为lstack->data[lstack->top],将其弹出后,top指示下面的元素,所以top要减1。
代码48-54行是元素入栈,首先是让top指示到数组中要插入数据的位置,因为是顺序栈,所以top++;然后将元素存储到数组的栈顶元素lstack->data[lstack->top]中。
代码56-60行是销毁栈,就是将分配的结构空间释放掉。
学习完顺序栈,读者可再与之前学习的顺序表相比较,区分两者在执行读取、插入、删除等操作时的异同,以巩固所学知识。
顺序栈是在顺序表的基础上实现的,读者可以利用已经实现的顺序表来实现一个顺序栈,例如在创建顺序栈时,直接调用已经在顺序表中实现的SeqList_Create()函数。这种实现方式就留给读者自己来实现,读者可以参考博学谷中的相关资源,也可以参考相应的讲解视频。当然,读者也可以有自己的实现方式,我们追求的是更高效简便的算法。