顺序栈.cpp

数据结构：顺序栈

//包含顺序栈操作实现的程序文件“顺序栈.cpp”
#include"顺序栈.h"
//初始化栈S，分配栈空间大小为ms，置为空
void InitStack(StackSq& S, int ms)
{
	//检查ms是否有效
	if(ms<=0) {cout<<"ms值非法！"<<endl; exit(1);}
	//置栈空间大小为ms
	S.MaxSize=ms;
	//动态存储空间分配
	S.stack=new ElemType[ms];
	if(!S.stack){
		cerr<<"Memory allocation failure!"<<endl;
		exit(1);
	}
	//初始置为空
	S.top=-1;
}

//元素item进栈，即插入到栈顶
void Push(StackSq& S, ElemType item)
{
	//若栈空间用完则动态扩大存储空间
	if(S.top==S.MaxSize-1){
		AllotStack(S);
	}
	//栈顶指针后移一个位置
	S.top++;
	//将新元素插入到栈顶
	S.stack[S.top]=item;
}

//删除栈顶元素并返回之
ElemType Pop(StackSq& S)
{
	//若栈空则退出运行
	if(S.top==-1){
		cerr<<"Stack is empty!"<<endl;
		exit(1);
		}
	//栈顶指针减1表示退栈
	S.top--;
	//返回原栈顶指针的值
	return S.stack[S.top+1];
}

//返回S的栈顶元素的值，但不移动栈顶指针的值
ElemType Peek(StackSq& S)
{
	//若栈空则退出
	if(S.top==-1){
		cerr<<"Stack is empty!"<<endl;
		exit(1);
	}
	//返回栈顶元素的值
	return S.stack[S.top];
}

//判断S是否为空，是返回true,否则返回false
bool EmptyStack(StackSq& S)
{
	return S.top==-1;
}

//清除栈S中的所有元素，释放动态存储空间
void ClearStack(StackSq& S)
{
	delete []S.stack;
	S.top=-1;
	S.MaxSize=0;
}

//实现栈空间的再分配
void AllotStack(StackSq& S)
{
	//定义一个新的栈空间，它为原栈空间的两倍
	ElemType *p=new ElemType[2*S.MaxSize];
	if(!p) {cout<<"内存空间用完，退出！"; exit(1);}
	//拷贝原栈中的内容
	for(int i=0; i<=S.top; i++)
		p[i]=S.stack[i];
	//释放S栈中的动态空间
	delete []S.stack;
	//使S栈的栈顶指针指向新的栈顶空间
	S.stack=p;
	//置栈空间大小为原来的两倍
	S.MaxSize=2*S.MaxSize;
}