数据结构03-栈

顺序栈

1、基本概念

栈是限定仅在表尾进行插入或删除操作的线性表，表末端为栈顶(Top)，表头称为栈顶(Bottom),不含元 素称为空战 (用顺序表存储的栈更常见) 因此栈又称为后进先出(Last in First out, LIFO)的线性表。

2、数据类型定义

//顺序栈ADTtypedef struct SequenceStack{    // 栈底    int *base;    // 栈顶    int *top;}SequenceStack;

3、功能实现

bool InitStack(SequenceStack &S){    S.base=new int[Maxsize];       //为顺序栈分配一个最大容量为Maxsize的空间	if(!S.base)                    //空间分配失败		return false;	S.top=S.base;                 //top初始为base，空栈	return true;}bool Push(SequenceStack &S,int e){    if(S.top-S.base==Maxsize)      //栈满		return false;	*(S.top++)=e;                 //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;	return true;}bool Pop(SequenceStack &S,int e){    if(S.top == S.base)      //栈空		return false;	e = *(--S.top);                 //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;	return true;}int GetTop(SequenceStack S){          //取栈顶 	if(S.top!=S.base)          //栈非空		return *(S.top-1);     //返回栈顶元素的值，栈顶指针不变    else        return -1;}

3、测试代码

int main(){   int n,x;	SequenceStack S;	InitStack(S);//初始化一个顺序栈S	cout<<"请输入元素个数n："<<endl;	cin>>n;	cout<<"请依次输入n个元素，依次入栈："<<endl;	while(n--){		cin>>x; //输入元素		Push(S,x);	}	cout<<"元素依次出栈："<<endl;	while(S.top!=S.base){//如果栈不空，则依次出栈        cout<<GetTop(S)<<"\t";//输出栈顶元素        Pop(S,x);   //栈顶元素出栈    }	return 0;}