《数据结构》C语言版——顺序栈

栈是限定仅在表面进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底，不含元素的空表称为空栈。

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，通常的习惯做法是以top=0表示空栈。

话不多说，把代码跑起来！！！

#include <stdio.h>
#include <malloc.h>
#include <assert.h>//断言

typedef int ElemType;//定义元素类型为int型，即为存放整型数据的顺序栈
#define STACK_INIT_SIZE 8//初始化顺序栈可以存放8个数据元素

/*顺序栈的结构*/
typedef struct SeqStack
{
	ElemType *base;//指针base指向开辟的栈空间
	int capacity;//定义顺序栈的容量(最大容量)
	int top;//定义栈顶指针(同时表示当前栈中的元素个数)
}SeqStack;//定义结构体变量

/*初始化顺序栈*/
void InitStack(SeqStack *s)//给出顺序栈的位置
{
//申请顺序栈的空间(元素类型)
	s->base=(ElemType *)malloc(sizeof(ElemType)*STACK_INIT_SIZE);
	assert(s->base!=NULL);//不为空时空间申请成功
	s->capacity=STACK_INIT_SIZE;//栈的容量为初始化大小
	s->top=0;//栈顶指针top指向0下标的位置,表示此时栈中一个数据元素都没有
}

bool IsFull(SeqStack *s)//入栈判断栈是否满
{
	return s->top >= s->capacity;//指针top所指的下标正好与栈的容量相等,此时栈已满
}

bool IsEmpty(SeqStack *s)//出栈判断栈是否空
{
	return s->top==0;//指针top所指的下标正好是0下标
}

/*入栈*/
void Push(SeqStack *s,ElemType x)
{
	if(IsFull(s))
	{
		printf("栈空间已满,%d不能入栈\n",x);
		return;
	}
	s->base[s->top]=x;//当前指针top所指的位置来存放数据,指针base指向真实的栈空间
	s->top++;//指针top指向下一个可用的栈空间
}

/*出栈*/
void Pop(SeqStack *s)
{
	if(IsEmpty(s))
	{
		printf("栈空间已空,不能出栈\n");
		return;
	}
	s->top--;//指针top指向上一个可用的栈空间
}

/*取栈顶元素*/
bool GetTop(SeqStack *s,ElemType *v)
{
	if(IsEmpty(s))
	{
		printf("栈空间已空,不能取栈顶元素\n");
		return false;
	}
	*v=s->base[s->top-1];//把栈顶元素存放在元素v的地址里,传回元素v
//因为入栈一个元素后,指针top就指向下一个空的栈空间,所以取栈顶元素,应该读取上一个栈空间里的元素,即用top-1的结果作为base的下标
	return true;
}

/*显示栈中元素*/
void Show(SeqStack *s)
{
	for(int i=s->top-1;i>=0;i--)
//因为入栈一个元素后,指针top就指向下一个空的栈空间,所以显示元素时,应该读取上一个栈空间里的元素
	{
	printf("%d\n",s->base[i]);
	}
	printf("\n");
}

/*栈的长度*/
int Length(SeqStack *s)
{
	return s->top;//返回0则为空栈,返回1则栈的长度为1(此时栈中有1个元素)
}

/*清除栈*/
void Clear(SeqStack *s)
{
	s->top=0;//栈顶指针指向0下标
}

/*销毁栈*/
void Destory(SeqStack *s)
{
	free(s->base);//释放栈空间
	s->base=NULL;//预防野指针
	s->capacity=s->top=0;//栈容量,栈中的数据元素都置0
}

void main()
{
	SeqStack st;//定义一个名为st的顺序栈
	InitStack(&st);
	ElemType  v;//定义临时元素v
	printf("入栈\n");
	for(int i=1;i<=5;++i)
	{
	Push(&st,i);//把1,2,3,4,5依次入栈	
	}
	Show(&st);
	printf("栈的长度为%d\n",Length(&st));
	printf("\n");
	GetTop(&st,&v);//给出临时元素v的地址
	printf("%d 是栈顶元素\n",v);//临时元素v就是栈顶元素,实现取栈顶元素
	printf("\n");
	printf("出栈\n");
	Pop(&st);
	Show(&st);
	printf("栈的长度为%d\n",Length(&st));
	printf("\n");
	printf("清除栈\n");
	Clear(&st);
	Show(&st);
	printf("栈的长度为%d\n",Length(&st));
	Destory(&st);
}

运行结果：