栈

栈：限定仅在表尾进行插入或删除操作的线性表。对栈来说，表尾端称为栈顶，表头端称为栈底。不含元素的空表称为空栈

栈又称为后进先出的线性表（LIFO结构，last in first out）

base：栈底指针，在顺序栈中，它的位置始终指向栈底。base=NULL，栈结构不存在

top：栈顶指针，初始值指向栈底，即top=base

基本的算法操作描述：

Status InitStack(SqStack &S){
	//构造一个空栈S
	S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(!S.base) exit(OVERFLOW);//存储分配空间失败
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return OK;
}//InitStack

Status GetTop(SqStack &S,SElemType &e){
	//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
	if(S.top==S.base) return ERROR;
	e=*(S.top-1);
	return OK;
}//GetTop

Status Push(SqStack &S,SElemType &e){
	//插入元素e为新的栈顶元素
	if(S.top-S.base>=S.stacksize){
		//栈满，追加存储空间
		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		if(!S.base) exit(OVERFLOW);//存储分配空间失败
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	* S.top++ =e;
	return OK;
}//Push

Status Pop(SqStack &S,SElemType &e){
	//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
	if(S.top==S.base) return ERROR;
	e= *--S.top;
	return OK;
}//Pop

栈的应用举例：