栈的顺序存储及代码实现

栈是在数据结构中经常能遇到的，在我们平时也能遇到。比如当我们在打断点调试时，经常能遇到堆栈，先调用的后出来。或者网页的后退键也是栈的应用。

一.栈及其初始化

• 栈是限定仅在表尾进行插入和删除操作的线性表。
• 我们把允许插入的一端称为栈顶，另一端称为栈底。
• 栈称为先进后出，简称FOLI
• 栈也是线性表，也有前驱后继关系。线性表的表尾是栈顶
• 栈插入操作叫进栈，入栈
• 栈删除操作叫出栈

栈的结构

栈的顺序存储

#define MAXSIZE 7
typedef int SElemtype;
typedef struct{
	SElemtype data[MAXSIZE];
	int top;
}Stack;

栈的初始化

void Stack_Init(Stack *s,int n)
{
	int i; 
	s->top = n - 1;
	for(i = 0;i < n;i++)
	{
		s->data[i] = i + 10;
		printf("%d  ",s->data[i]);
	}
	printf("\n");
}

二.栈的操作（出栈，入栈）

2.1入栈

因为操作都在栈顶操作，所以时间复杂度都是O（1）

Status Push(Stack *s,SElemtype e)
{
	if(s->top == MAXSIZE - 1)
	return ERROR;
	s->data[++(s->top)] = e;
	return OK;
}

这里就是别忘了栈顶的移动和判断能否入栈

2.2出栈

Status Poll(Stack *s,SElemtype *e)
{
	if(s->top == -1)
	return ERROR;
	*e = s->data[(s->top)--];
	return OK;
}

2.3代码实现：

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 7
typedef int SElemtype;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct{
	SElemtype data[MAXSIZE];
	int top;
}Stack;


void Stack_Init(Stack *s,int n)
{
	int i; 
	s->top = n - 1;
	for(i = 0;i < n;i++)
	{
		s->data[i] = i + 10;
		printf("%d  ",s->data[i]);
	}
	printf("\n");
}
Status Push(Stack *s,SElemtype e)
{
	if(s->top == MAXSIZE - 1)
	return ERROR;
	s->data[++(s->top)] = e;
	return OK;
}

Status Poll(Stack *s,SElemtype *e)
{
	if(s->top == 0)
	return ERROR;
	*e = s->data[(s->top)--];
	return OK;
}
int main(void)
{
	SElemtype e;
	Stack s;
	Stack_Init(&s,5);
	Push(&s,100);
	for(int i = 0;i < 6;i++)
	{
		printf("%d  ",s.data[i]);
	}
	Poll(&s,&e);
	printf("%d ",e);
	return 0;
}

三.两栈共享空间

栈的顺序存储很方便，但是必须知道存储空间大小，如果不够用那会是非常麻烦。
那么我们可以让两个栈共用。让一个栈的栈底为另一个的初始

共享的结构

typedef struct{
	SElemtype data[MAXSIZE];
	int top1;
	int top2;
}DoubleStack;

初始化

void DoubleStack_Init(DoubleStack *ds,int n1,int n2)
{
	int i;
	ds->top1 = 0;
	ds->top2 = MAXSIZE - 1;
	for(i = 0;i < MAXSIZE;i++)
	{
		ds->data[i] = 0;
	}
	for(i = ds->top1;i < n1;i++)
	{
		ds->data[(ds->top1)++] = 10 + i;
	}
	for(i = ds->top2;i > ds->top1 + n2;i--)
	{
		ds->data[(ds->top2)--] = 50 + i;
	}
}

这里我的栈顶是提前了一个，就是本来应该是5，结果是6了，忘了改了，但是下面结果没错，我下面的做了适当修改

3.1插入元素

在这里我们就需要判断是栈1还是栈2

Status DoubleStack_Push(DoubleStack *ds,SElemtype e,int stackNumber)
{
	if(ds->top1 + 1 == ds->top2)
	return ERROR;
	if(stackNumber == 1)
	   ds->data[(ds->top1)++] = e;
	else if(stackNumber == 2)
	   ds->data[(ds->top2)--] = e;
	return OK;
}

这里需要注意是怎么判断栈是否是满。就是当两个相遇时候，因为一个是在前面，一个是在后面。

3.2删除元素

Status DoubleStack_Poll(DoubleStack *ds,SElemtype *e,int stackNumber)
{
	if(stackNumber == 1 )
	{
		if(ds->top1 == -1)
		    return ERROR;
		*e = ds->data[ds->top1 - 1];
		ds->data[ds->top1] = 0;
		ds->top1--;
	}
	else if(stackNumber == 2 )
	{
		if(ds->top1 == MAXSIZE)
		    return ERROR;
		*e = ds->data[ds->top2 + 1];
		ds->data[ds->top2 + 1] = 0;
		printf("%d   ",ds->top2);
		ds->top2++;
	}
	return OK;
}

这里为了适应我之前错误，进行修改了，结果是对的

总体代码

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20
typedef int SElemtype;
typedef int Status;
#define OK 1
#define ERROR 0
typedef struct{
	SElemtype data[MAXSIZE];
	int top1;
	int top2;
}DoubleStack;

void DoubleStack_Init(DoubleStack *ds,int n1,int n2)
{
	int i;
	ds->top1 = 0;
	ds->top2 = MAXSIZE - 1;
	for(i = 0;i < MAXSIZE;i++)
	{
		ds->data[i] = 0;
	}
	for(i = ds->top1;i < n1;i++)
	{
		ds->data[(ds->top1)++] = 10 + i;
	}
	for(i = ds->top2;i > ds->top1 + n2;i--)
	{
		ds->data[(ds->top2)--] = 50 + i;
	}
}

Status DoubleStack_Push(DoubleStack *ds,SElemtype e,int stackNumber)
{
	if(ds->top1 + 1 == ds->top2)
	return ERROR;
	if(stackNumber == 1)
	   ds->data[(ds->top1)++] = e;
	else if(stackNumber == 2)
	   ds->data[(ds->top2)--] = e;
	return OK;
}

Status DoubleStack_Poll(DoubleStack *ds,SElemtype *e,int stackNumber)
{
	if(stackNumber == 1 )
	{
		if(ds->top1 == -1)
		    return ERROR;
		*e = ds->data[ds->top1 - 1];
		ds->data[ds->top1] = 0;
		ds->top1--;
	}
	else if(stackNumber == 2 )
	{
		if(ds->top1 == MAXSIZE)
		    return ERROR;
		*e = ds->data[ds->top2 + 1];
		ds->data[ds->top2 + 1] = 0;
		printf("%d   ",ds->top2);
		ds->top2++;
	}
	return OK;
}

int main(void)
{
	SElemtype e;
	DoubleStack ds;
	DoubleStack_Init(&ds,7,4);
	DoubleStack_Push(&ds,1000,2);
	for(int i = 0;i < MAXSIZE;i++)
	printf("%d  ",ds.data[i]);
	printf("\n");
	DoubleStack_Poll(&ds,&e,2);
	for(int i = 0;i < MAXSIZE;i++)
	printf("%d  ",ds.data[i]);
	return 0;
}

四.结尾

栈的共享就像一个会移动的盒子，就是两端无论怎么动，大小还是那么大，而且两端都增加，很快空间就会满了。为了能更好的放更多元素，其实可以使用栈的链式存储。