数据结构（共享栈的实现）

1.定义

共享栈：两个栈共享同一片内存空间，两个栈从两边往中间增长。

目的：节省内存空间。

空栈判断：一号栈的栈顶指针为-1，二号栈的栈顶指针为MaxSize。

栈满判断：一号栈的栈顶指针位置等于二号栈的栈顶指针-1。

2.代码

（1）定义结构体

typedef struct{
	int data[MaxSize];//一个存放栈中数据元素的结构体 
	int top1;//指向一号栈栈顶的指针
	int top2;// 指向二号栈栈顶的指针
	int size1;//记录一号栈大小 
	int size2; //记录二号栈大小 
	int search;//遍历指针 
}SqStack;//定义栈的结构体 

（2）初始化栈

void InitStack(SqStack *S){//初始化 
	S->top1=-1;//1号栈的栈顶指针指向栈顶初始化位置 
	S->top2=MaxSize;//2号栈的栈顶指针指向栈尾初始位 
	S->size1 = 0;
	S->size2 = 0;
	S->search=-1;//遍历指针 
}

（3）入栈操作

bool Push(SqStack *S,int pushNum){//一号栈入栈 
	if(S->top1==S->top2-1){//栈满 
		return false;//入栈失败 
	}
	S->data[++S->top1]=pushNum;//入栈 
	S->size1++;//栈长+1 
	return true;
}
bool Push2(SqStack *S,int pushNum){//二号栈入栈 
	if(S->top1==S->top2-1){//栈满 
		return false;//入栈失败 
	}
	S->data[--S->top2]=pushNum;//入栈 
	S->size2++;//栈长+1 
	return true;
}

（4）读取栈顶

bool ReadTop(SqStack *S,int *readNum){//一号栈读取栈顶元素 
	if(S->size1==0){//一号栈中没有元素 
		return false;
	}
	*readNum = S->data[S->top1];
//	printf("栈顶元素是%dn",readNum);
	return true;
}
bool ReadTop2(SqStack *S,int *readNum){//二号栈读取栈顶元素 
	if(S->size2==0){//二号栈中没有元素 
		return false;
	}
	*readNum = S->data[S->top2];
//	printf("栈顶元素是%dn",readNum);
	return true;
}

（5）出栈操作

bool Pop(SqStack *S,int *popNum){//一号栈出栈操作 
	if(S->size1==0){//一号栈中没有元素 
		return false;
	}
	*popNum = S->data[S->top1--];//和读栈的区别在出栈将栈顶指针下移一位
	S->size1--;//计数-1 
	return true; 
}
bool Pop2(SqStack *S,int *popNum){//二号出栈操作 
	if(S->size2==0){//二号栈中没有元素 
		return false;
	}
	*popNum = S->data[S->top2++];//二号栈的栈顶指针和一号栈移动方向相反 
	S->size2--;//计数-1 
	return true; 
}

（6）遍历整个栈存储空间

void TraversalStack(SqStack S){
	int Traversal = S.search+1;
	int record = 0;
	while(Traversal 
 
 
3.整体代码
 
//共享栈 
#include 
#include 

#define MaxSize 10//栈中元素的最大个数 
//   -1是栈顶指针的初始化位置  [0,1,2,3,4,5,6,7,8,9] 
typedef struct{
	int data[MaxSize];//一个存放栈中数据元素的结构体 
	int top1;//指向一号栈栈顶的指针
	int top2;// 指向二号栈栈顶的指针
	int size1;//记录一号栈大小 
	int size2; //记录二号栈大小 
	int search;//遍历指针 
}SqStack;//定义栈的结构体 

void InitStack(SqStack *S){//初始化 
	S->top1=-1;//1号栈的栈顶指针指向栈顶初始化位置 
	S->top2=MaxSize;//2号栈的栈顶指针指向栈尾初始位 
	S->size1 = 0;
	S->size2 = 0;
	S->search=-1;//遍历指针 
}
bool Push(SqStack *S,int pushNum){//一号栈入栈 
	if(S->top1==S->top2-1){//栈满 
		return false;//入栈失败 
	}
	S->data[++S->top1]=pushNum;//入栈 
	S->size1++;//栈长+1 
	return true;
}
bool Push2(SqStack *S,int pushNum){//二号栈入栈 
	if(S->top1==S->top2-1){//栈满 
		return false;//入栈失败 
	}
	S->data[--S->top2]=pushNum;//入栈 
	S->size2++;//栈长+1 
	return true;
}
bool ReadTop(SqStack *S,int *readNum){//一号栈读取栈顶元素 
	if(S->size1==0){//一号栈中没有元素 
		return false;
	}
	*readNum = S->data[S->top1];
//	printf("栈顶元素是%dn",readNum);
	return true;
}
bool ReadTop2(SqStack *S,int *readNum){//二号栈读取栈顶元素 
	if(S->size2==0){//二号栈中没有元素 
		return false;
	}
	*readNum = S->data[S->top2];
//	printf("栈顶元素是%dn",readNum);
	return true;
}

bool Pop(SqStack *S,int *popNum){//一号栈出栈操作 
	if(S->size1==0){//一号栈中没有元素 
		return false;
	}
	*popNum = S->data[S->top1--];//和读栈的区别在出栈将栈顶指针下移一位
	S->size1--;//计数-1 
	return true; 
}
bool Pop2(SqStack *S,int *popNum){//二号出栈操作 
	if(S->size2==0){//二号栈中没有元素 
		return false;
	}
	*popNum = S->data[S->top2++];//二号栈的栈顶指针和一号栈移动方向相反 
	S->size2--;//计数-1 
	return true; 
}

void TraversalStack(SqStack S){
	int Traversal = S.search+1;
	int record = 0;
	while(Traversal