stack顺序存储结构

《偶刚开始学习数据结构，欢迎拍砖111》

栈是只能通过访问它的一段来实现数据存储的一种线性数据结构，换句话来说就是先进后出的原则，FILO，与队列刚好相反哈，现在只说stack。

栈包括以下几种基本运算

（1）初始化

（2）判断是否为空

（3）push

（4）pop

（5）top

其他的则根据这几种基本操作进行组合，即可实现。

栈的实现同样有顺序存储与链式存储两种方式，现在说一说顺序存储

首先顺序存储简单可以理解为对数组的操作，所以他的缺点就是容量是有限的。

ok，言归正传。

《一》array_based_stack的实现

首先同样将存储的元素设定为int

下面是stack类型

1#define MAX_STACK_SIZE 100     //栈的容量
2typedef struct ArrayBasedStack{
3	int *base; //存储空间
4	int top;   //top指向最上面的一个可用元素,为空时，top = -1；
5
6}AStack;

以及以下几个操作的定义

1int initStack(AStack* s);
2bool stackEmpty(AStack* s);
3int* push(AStack* s, int elem);//成功则返回栈顶指针，否则返回null
4int* pop(AStack* s);//返回新的栈顶指针
5int top(AStack* s);

下面是实现

1#include "stack_array_based.h"
2#include <MALLOC.H>
3#include <STDIO.H>
4int initStack(AStack* s)
5{
6	s->base = (int *)malloc(MAX_STACK_SIZE * sizeof(int));
7	if (s->base==NULL)
8	{
9		return -1;
10	}
11	s->top = -1;
12	return 0;
13}
14
15bool stackEmpty(AStack* s)
16{
17	if (s->top == -1)
18	{
19		return true;
20	}
21	return false;
22}
23int* push(AStack* s, int elem)
24{
25	if (s->top==MAX_STACK_SIZE-1) //栈满
26	{
27		return NULL;
28	}
29	s->top++;
30	s->base[s->top] = elem;
31	
32	return &(s->base[s->top]);
33}
34int* pop(AStack* s)//返回新的栈顶指针
35{
36
37	if (stackEmpty(s))
38	{
39		return NULL;
40	}
41	s->top --;
42	if (top<0)
43	{
44		return NULL;
45	}
46	return &(s->base[s->top]);
47}
48int top(AStack* s)
49{
50	return (s->base[s->top]);
51}

最后再来个简单的测试实例

1#include "stack_array_based.h"
2#include <MALLOC.H>
3#include <STDIO.H>
4
5int main()
6{
7	AStack* s = (AStack*)malloc(sizeof(AStack));
8	if (s == NULL)
9	{
10		return -1;
11	}
12	
13	initStack(s);
14	printf("top:%d\n",s->top);
15	//向栈中插入是个数据
16	for (int i = 0; i<10; i++)
17	{
18		push(s,i);
19	}
20	//将数据打印
21	while(!stackEmpty(s))
22	{
23		printf("%d\t",top(s));
24		pop(s);
25	}
26}

实验结果如下

《二》栈的链式实现

请参照linklist，自行实现。

《偶刚开始学习数据结构，欢迎拍砖111》