栈

栈是一种特殊的线性表，栈限定仅在表尾进行插入或删除的操作。因此，对栈来说，表尾端有其特殊含义，成为栈顶（top）,相应的，表头端称为栈底（bottom）。不含元素的空表称为空栈。栈又称为后进先出（last in first out）的线性表。

1.栈的实现

在实现之前先把需要使用到的库和头文件进行包含 
所需的头文件stack.h已经在上方提供

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

1）构造一个空栈

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

2）销毁栈

Status DestoryStack_S(SqStack &S){
	//销毁栈S，S不再存在
	free(S.base);
	S.base = NULL;
	return 0; 
}//DestoryStack_S

3）清空栈

Status ClearStack_S(SqStack &S){
	//把S置为空栈
	S.top = S.base;
	return 0; 
}//ClearStack_S

4）判断栈是否为空

Status StackEmpty_S(SqStack &S){
	//若栈S为空栈，则返回TRUE，否则返回FALSE
	return (S.base == S.top)?TRUE:FALSE; 
}//SratckEmpty_S

5）获取栈中数据元素的个数

Status StackLength_S(SqStack S){
	//返回S的元素个数，即栈的长度
	return (S.top-S.base); 
}//StackLength_S

6）取栈顶元素

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

7）压栈操作

Status Push_S(SqStack &S,SElemType e){
	//插入元素e为新的栈顶元素
	if(S.stacksize == StackLength_S(S))
	{
		S.base = (SElemType *)realloc(S.base,(S.stacksize+SATCKINCREMENT)*sizeof(SElemType));    //增加栈存储容量
		if(!S.base)
		return ERROR;
		S.stacksize += SATCKINCREMENT;  
	 } 
	 *S.top = e;
	 S.top++;
	 return OK;
}//Push_S

8）调用visit()函数遍历栈

Status visit_display_S(SElemType e){
	//打印元素 
	printf("%d",e);
	printf("\n");
	return OK;
}//visit_display_S 
Status StackTraverse_S(SqStack &S,Status (*visit)(SElemType)){
	//从栈底到栈顶依次对栈中的每个元素调用函数visit()，一旦visit()失效，则操作失败
	SElemType *p;
	p = S.base; //p指向栈底
	while(p!=S.top) //遍历栈的元素 
	{
		visit(*p);
		p++;
	 } 
	 return OK;
}//StackTreaverse_S