这两天完成了栈的顺序存储结构的相关算法，包括初始化、压栈、出栈、取栈顶元素、判断栈是否为空、返回栈长度、栈的遍历、清栈、销毁栈。这次的实现过程有两点收获，总结如下：
一、清楚遍历栈的概念
栈的遍历指的是从栈底想栈顶方向运行visit()函数，这是之前的学习中所忽略的；栈的遍历解除了栈的输出顺序只能从栈顶像栈底方向的限制。
二、清空栈时要不要将stacksize重置
网上看到有的人在实现清空栈这一功能时，将stacksize重置为0，我觉得有点问题，起初的想法是将其重置为初始化时的值，在与同学讨论了后，最后决定不应重置stacksize的值，原因是:
重置的目的是针对使用了realloc()重新分配了地址的栈，但是realloc()函数分配的是一段连续的地址，指向栈底的指针指向了这段空间，即使将stacksize重置回初始值，增加的那段空间还是由指向栈底的指针来控制的(参照这句S.base=(Elemtype *)realloc(S.base,(S.stacksize+STACKINCREACE)*sizeof(Elemtype));思考)，因此重置没有意义。类比顺序表的清空：顺序表的清空也是只将当前长度置为0，没有改变它的listsize值。
这次使用的编译环境是VC++6.0。
//头文件内容
//--------------------栈的顺序存储结构--------------------
#define STACK_INIT_SIZE 100
#define STACKINCREACE 10
typedef char Elemtype;//在头文件中说明
typedef int Status;
typedef struct{
Elemtype *base;
Elemtype *top;
int stacksize;
}SqStack;
//----------------------函数声明部分----------------------
Status InitStack(SqStack &S);
Status Push(SqStack &S,Elemtype e);
Status Pop(SqStack &S,Elemtype &e);
Status GetTop(SqStack S,Elemtype &e);
Status StackEmpty(SqStack S);
int StackLength(SqStack S);
Status StackTraverse(SqStack S);
Status ClearStack(SqStack &S);
Status DestroyStack(SqStack &S); //源文件内容
#include <stdio.h>
#include <stdlib.h>
#include "SqStackHeader.h" //--------------------主函数入口--------------------
void main(){
SqStack stack;
char temp='a';
char getElem=NULL;
char popElem=NULL;
InitStack(stack);
Push(stack,temp);
Push(stack,'b');
GetTop(stack,getElem);
printf("栈顶元素是：%c\n",getElem);
char *empty=NULL;
empty=StackEmpty(stack)?"是空栈！":"不是空栈！";
// printf("是否为空栈判断结果：%s\n",empty);
// ClearStack(stack);
DestroyStack(stack);
StackTraverse(stack); // printf("栈的长度：%d\n",StackLength(stack)); // Pop(stack,popElem);
}
//------------------栈的初始化函数------------------
Status InitStack(SqStack &S){
S.base = (Elemtype *)malloc(STACK_INIT_SIZE*sizeof(Elemtype));
//2016.4.17编译时报错：missing “)”before ;
//错误原因：由于头文件中定义常量时后面加了;导致编译的时候将STACK_INIT_SIZE用100;代替，
//使得该函数提前结束语100处，malloc后的“(”找不到匹配的“)”而报错
//解决方法：去掉常量定义中的;
if(!S.base){
return false;
}
S.stacksize=STACK_INIT_SIZE;
S.top=S.base;
return true;
}
//---------------------入栈函数---------------------
Status Push(SqStack &S,Elemtype e){
//判断是否溢出
if(S.top-S.base>=S.stacksize){
S.base=(Elemtype *)realloc(S.base,(S.stacksize+STACKINCREACE)*sizeof(Elemtype));
if(!S.base){
return false;
}
S.top=S.base+S.stacksize;//注意因为这里的栈底指针的改变，导致栈顶指针随之改变
S.stacksize+=STACKINCREACE;
}
//压栈部分
*S.top=e;
S.top++;
return true;
}
//---------------------出栈函数---------------------
Status Pop(SqStack &S,Elemtype &e){
//非法判断
if(S.base==S.top){
return false;
}
S.top--; //注意这里因为top指向栈中当前元素的上一个空间，所以要先将其位置减一
e=*S.top;
return true;
}
//-------------------查看栈顶元素-------------------
Status GetTop(SqStack S,Elemtype &e){
if(S.base==S.top ){
return false;
}
e=*(S.top-);
return true;
}
//------------------判断栈是否为空------------------
Status StackEmpty(SqStack S){
if(S.base==S.top){
return true;
}
return false;
}
//------------------返回栈元素个数------------------
int StackLength(SqStack S){
if(S.base==S.top){
return ;
}
return S.top-S.base;
}
//--------------------遍历栈------------------------
Status StackTraverse(SqStack S){//从栈底到栈顶的方向
if(S.top==S.base){
return false;
}
while(S.base <S.top ){
printf("%c\t",*(S.base++));
}
printf("\n");
return true;
}
//--------------------清空栈------------------------
Status ClearStack(SqStack &S){//清空栈的时候不用将stacksize重新赋值
S.top=S.base; //因为经过realloc函数重新分配空间后(stacksize大小改变)，
return true; //S.base指向的是一段stacksize大小的连续存储空间
//即使将他重置，剩余的空间也是闲置的(顺序表里也只是经当前长度置为0)
}
//--------------------销毁栈------------------------
Status DestroyStack(SqStack &S){
free(S.base);
free(S.top);
S.base=NULL;
return true;
}