typedef struct{
	SElemType *base;
	SElemType *top;
	
	int stacksize;
}SqStack;

//====== ADT Stack的表示与实现 ======

//----- 栈的顺序存储表示-------------



#define STACK_INIT_SIZE   100              //存储空间初始分配量
#define STACKINCREMENT 10                  //存储空间分配增量

typedef struct{
	SElemType *base;                       //在构造之前和销毁之后，base的值为NULL
	SElemType *top;                        //栈顶指针
	
	int stacksize;                         //当前已分配的存储空间，以元素为单位
}SqStack;


//-------- 基本操作的函数原型说明 -----------------

//构造一个空栈S
Status InitStack(SqStack &S);

//销毁栈S， S不再存在
Status DestroyStack(SqStack &S);

//把S置为空栈
Status ClearStack(SqStack &S);

//若S为空栈，则返回TRUE，否则返回FALSE
Status StackEmpty(SqStack S);

//返回S的元素个数，即栈的长度
int StackLength(SqStack S);

//若栈不空，则用e返回S的栈顶元素，并返回OK； 否则返回ERROR
Status GetTop(SqStack S, SElemType &e);

//插入元素e为新的栈顶元素
Status Push(SqStack &S, SElemType e);

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqStack &S, SElemType &e);

//从栈底到栈顶依次对栈中每个元素调用函数visit()，一旦visit()失败，操作失败
Status StackTraverse(SqStack S, Status (*visit)());



//------ 基本操作的算法描述（部分）-------------
Status InitStack(SqStack &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;
}

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

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 = S.stacksize + STACKINCREMENT;
	}
	
	*S.top++ = e;
	
	return OK;
}

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

	return OK;	
}

typedef struct SNode{
	SElemType data;
	struct SNode *prev;
	struct SNode *next;
}SNode;

typedef struct{
	SNode *base;
	SNode *top;
	int stacksize;
}LsNode, *LinkStack;



Status InitStack(LinkStack *S)
{
	if(!S)
		return ERROR;

	*S = (LinkStack)malloc(sizeof(LsNode));
	if(!*S)
		exit(OVERFLOW);

	(*S)->base = (*S)->top = NULL;
	(*S)-stacksize = 0;

	return OK;
}

Status Push(LinkStack *S, SElemType e)
{
	SNode *p = (SNode *)malloc(sizeof(SNode));
	if(!p)
		exit(OVERFLOW);

	p->prev = p->next = NULL;
	p->data = e;

	if((*S)->top == NULL){
		(*S)->base = (*S)->top = p;
		(*S)->stacksize = 1;
	}else{
		(*S)->top->next = p;
		p->prev = (*S)->top;

		(*S)->top = (*S)->top->next;
		(*S)->stacksize = (*S)->stacksize+1;
	}

	return OK;
}

Status Pop(LinkStack *S, SElemType &e)
{
	if ((*S)->base == NULL){
		return ERROR;		
	}

	if((*S)->base == (*S)->top)
	{
		e = (*S)->top->data;
		
		free((*S)->top);
		(*S)->top = (*S)->base = NULL;
		return OK;
	}

	e = (*S)->top->data;
	
	SNode *p = (*S)->top;
	(*S)->top = (*S)->top->prev;
	(*S)->top->next = NULL;

	free(p);
	return OK;
}

do{
	若当前位置可通，则{             

		将当前位置插入栈顶；         //纳入路径

		若该位置是出口位置，则结束；
		否则切换当前位置的东方邻块为新的当前位置;
	}
	否则{
		若栈不空，且栈顶位置仍有其他方向未经探索，
		    则设定新的当前位置为沿顺时钟方向旋转找到的栈顶位置的下一邻块；
		若栈不空，但栈顶位置的四周均不可通，则{
			删去栈顶位置;                  //从路径中删去该通道块
           
			若栈不空，则重新测试新的栈顶位置，
				直至找到一个可通的相邻块或出栈至栈空;
		}
	}
}while(栈不空);

Status MazePath(MazeType maze, PosType start, PosType end)
{
	//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中(从栈底到栈顶),
	//并返回TRUE；否则返回FALSE
	
	InitStack(S);
	curpos = start;          //设定"当前位置"为"入口位置"
	curstep = 1;             //探索第一步
	
	do{
		if(Pass(curpos)){                 //当前位置可以通过，即是未曾走到过的通道块
			
			FootPrint(curpos);            //留下足迹
			e = (curstep, curpos, 1);
			Push(S, e);                   //加入路径
			
			if(curpos == end)   
				return TRUE;              //到达终点(出口)          
				
			curpos = NextPos(curpos, 1);  //下一位置是当前位置的东邻	
			curstep++;                    //探索下一步
		}
		else{                             //当前位置不能通过
			if(!StackEmpty(S)){
				Pop(S, e);
				
				while(e.di == 4 && !StackEmpty(S)){
					MarkPrint(e.seat);
					Pop(S, e);                 //留下不能通过的标记，并退回一步
				}
				
				if(e.di < 4){
					e.di++;
					Push(S, e);               //换下一个方向探索
					
					curpos = NextPos(e.seat, e.di);    //设定当前位置是该新方向上的相邻块
				}
			
			}
		}
		
	}while(!StackEmpty(S));
	
	return FALSE;
}

//算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈， OP为运算符集合
OperandType EvaluateExpression()
{
	InitStack(OPTR);
	Push(OPTR,'#');

	InitStack(OPND);
	
	c = getchar();
	while(c != '#' || GetTop(OPTR) != '#')
	{
		if(!In(c, OP))
		{
			//不是运算符则进栈
			Push(OPND,c);
			c = getchar();
		}
		else{
			switch(Precede(GetTop(OPTR),c))
			{
				case '<':
				{
					//栈顶元素优先权低
					Push(OPTR,c);
					c = getchar();
					break;
				}
				case '=':
				{
					//脱括号，并接收下一字符
					Pop(OPTR,x);
					c = getchar();
					break;
				}
				case '>':
				{
					//退栈并将运算结果入栈
					Pop(OPTR,theta);
					Pop(OPND,b);
					Pop(OPND,a);
					Push(OPND,Operate(a,theta,b));
					break;
				}
			}
		}
	}

	return GetTop(OPND);
}

	//将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘按规则搬到塔座z上，y可用作辅助塔座
	
	//移动操作move(x,n,z)可定义为（c是初值为0的全局变量，对搬动计数）：
	void move(char x, int n, char z)
	{
		printf("%i. Move disk %i from  %c to  %c\n", ++c, n, x,z);
	}

	void hanoi(int n,char x,char y, char z)
1	{
2		if(n == 1)
3			move(x,1,z);
4		else{
5			hanoi(n-1,x,z,y);	//将x上编号为1至n-1的圆盘移到y，z作辅助塔
6			move(x,n,z);		//将编号为n的圆盘从x移到z
7			hanoi(n-1,y,x,z);	//将y上编号为1至n-1的圆盘移到z，x作为辅助塔
8		}
9	}