/*
表示堆栈的结构
*/
#define MaxSize//存储数据元素的最大个数
typedef struct SNode *Stack;
struct SNode{
	//数组的分量
	ElementType Data[MaxSize];
	//栈顶位置其数组下标位于哪里,但Top不是一个地址.
	int Top;
}

入栈

/*
入栈
PtrS是Stack类型的一种结构指针
item准备入栈的对象

用数组表示堆栈时:
Top=0,表示分量下标为0的地方有一个元素。
Top=-1,表示堆栈空,在最下面的位置。
Top>0且<=MaxSize-1,表示堆栈不为空,且至少有两个元素。
*/
void Push(Stack PtrS, ElementType item){
	/*
	入栈操作首先判断堆栈是否满,即:最多放MaxSize这些元素。
	因为数组的下标是从0开始的,所以从0一直到MaxSize-1。
	所以当Top指向MaxSize-1的时候,意味着n个元素全部放满了。
	*/
	if(PtrS->Top == MaxSize-1){
		//这里用数组表示,说明数组是有界限的。
		printf("堆栈满");
		return;
	}else{
		/*
		此语句做了两件事情:
		item放在Top+1的一个位置。
		++放在Top上面,实现入栈操作。
		*/
		PtrS->Data[++(PtrS->Top)] = item;
		return;
	}
}

出栈

/*
出栈
PtrS是Stack类型的一种结构指针

用数组表示堆栈时:
Top=0,表示分量下标为0的地方有一个元素。
Top=-1,表示堆栈空,在最下面的位置。
Top>0且<=MaxSize-1,表示堆栈不为空,且至少有两个元素。
*/
ElementType Pop(Stack Ptrs){
	if(Ptrs->Top == -1){
		printf("堆栈空!");
		/*
		ERROR是ElementType的特殊值,标识错误.
		*/
		return ERROR;
	}else{
		return (Ptrs->Data[(Ptrs->Top)--]);
	}
}

案例

首先把数组对分，左边一半是个堆栈，右边一半是另一堆栈，这样的话，一个数组就实现了两个堆栈。看下这样有什么问题？

堆栈都是往右边涨，都空出来的右边是空的。

假如，第二个堆栈继续涨，那么第二个堆栈就再也放不进去了。

但此时，数组还是有空间的，第一个堆栈还有地方没放。

此时，TOP1的位置指向堆栈的第一块最右边的位置，TOP2的位置指向数组末尾的位置。

所以，简单的把一个数组对分来做两个堆栈就会有问题:一个堆栈满了，另一个堆栈没满。

那么我们的要求是，只要数组有剩余空间，那么就入栈。

此时，换一种思路，数组依然做两个堆栈，但是不是都往右边涨了，而是都往中间涨，第一个堆栈有数据时往右挪动，第二个堆栈有数据时往左挪动，删除的话，二者就往相反方向挪动，这样只要数组有空间，那么就可以执行入栈操作。

如何判断堆栈满了呢？

第一个堆栈TOP1(数组下标)，第二个堆栈TOP2(数组下标)。

但并不是TOP1+TOP2=堆栈满。

有且仅当两个堆栈的指针相遇的时候，堆栈就满了，而不是TOP1+TOP2=堆栈满。

/*
最大地利用数组空间:基础结构

一个数组实现两个堆栈,使这两个堆栈分别从数组的两头开始向中间生长。
当两个栈顶指针相遇时,表示两个栈都满了。
*/
#define MaxSize<存储数据元素的最大个数>
struct DStack{
	ElementType Data[MaxSize];
	int Top1;//堆栈1的栈顶指针
	int Top2;//堆栈2的栈顶指针
} S;
/*
Top1代表Data数组的下标
第1个堆栈空的条件/位置:Top1 = -1
数组的第一个位置是:0
*/
S.Top1 = -1;
/*
Top2代表Data数组的下标
第2个堆栈空的条件/位置:Top1 = MaxSize
数组的最后一个位置是:MaxSize-1
*/
S.Top2 = MaxSize;

/*
最大地利用数组空间:push操作

一个数组实现两个堆栈,使这两个堆栈分别从数组的两头开始向中间生长。
当两个栈顶指针相遇时,表示两个栈都满了。

PtrS是Stack类型的一种结构指针
Tag作为区分两个堆栈的标识,1和2.
*/
void Push(struct DStack *Ptrs, ElementType item, int Tag){
	//堆栈满,两个指针挨在一起了
	if(Ptrs->Top2 - Ptrs->Top1 == 1){
		printf("堆栈满");
		return;
	}
	//对第1个/左边的堆栈操作(从低位到高位)
	else if(Tag == 1){
		//入栈
		Ptrs->Data[++(Ptrs->Top1)] = item;
	}
	//对第2个/右边的堆栈操作(从高位到低位)
	else{
		//入栈
		Ptrs->Data[--(Ptrs->Top2)] = item;
	}
}

/*
最大地利用数组空间:pop操作

一个数组实现两个堆栈,使这两个堆栈分别从数组的两头开始向中间生长。
当两个栈顶指针相遇时,表示两个栈都满了。

PtrS是Stack类型的一种结构指针
Tag作为区分两个堆栈的标识,1和2.
*/
ElementType Pop(struct DStack *Ptrs, int Tag){
	//对第1个/左边的堆栈操作(从高位到低位)
	if(Tag == 1){
		if(Ptrs->Top1 == -1){
			printf("堆栈1空");
			return NULL;
		}else{
			//出栈
			return Ptrs->Data[(Ptrs->Top1)--];
		}
	}
	//对第2个/右边的堆栈操作(从低位到高位)
	else{
		if(Ptrs->Top2 == MaxSize){
			printf("堆栈空");
			return NULL;
		}else{
			//出栈
			return Ptrs->Data[(Ptrs->Top2)++];
		}
	}

}