数据结构的C++实现之两栈共享存储空间

数据结构的C++实现之两栈共享存储空间2013-08-14 csdn Simba888888数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度

n-1处。这样，如果两个栈增加元素，就是两端点向中间延伸。当top1 + 1 == top2 的时候为栈满。

示例代码：（改编自《大话数据结构》）

#include <iostream>using namespace std;#defineMAXSIZE 20typedef int ElemType;typedef struct{ElemType data[MAXSIZE];int top1; //栈1栈顶指针int top2; //栈2栈顶指针} SqStack;/* 构造一个空栈*/bool InitStack（SqStack *Sq）{cout << "Init Stack ..." << endl;Sq->top1 = -1; //表示空栈Sq->top2 = MAXSIZE;return true;}/* 置为空栈 */bool ClearStack（SqStack *Sq）{cout << "Clear Stack ..." << endl;Sq->top1 = -1;Sq->top2 = MAXSIZE;return true;}bool StackEmpty（SqStack Sq）{if （Sq.top1 == -1 && Sq.top2 == MAXSIZE）return true;elsereturn false;}int StackLength（SqStack Sq）{cout << "Stack Length : ";return Sq.top1 + 1 + MAXSIZE - Sq.top2;}/* 返回栈顶元素 */bool GetTop（SqStack Sq, ElemType *ptr, int StackNum）{if （StackNum == 1）{if （Sq.top1 ！= -1）{*ptr = Sq.data[Sq.top1];cout << "Get Top1 Item " << *ptr << endl;return true;}return false;}else if （StackNum == 2）{if （Sq.top2 ！= MAXSIZE）{*ptr = Sq.data[Sq.top2];cout << "Get Top2 Item " << *ptr << endl;return true;}return false;}else{cout << "Stack Num must be 1 or 2！" << endl;return false;}}/* 压栈 */bool Push（SqStack *Sq, ElemType Elem, int StackNum）{if （StackNum == 1）{cout << "Push Item to Stack1 : " << Elem << endl;if （Sq->top1 + 1 == Sq->top2） //栈满return false;Sq->data[++Sq->top1] = Elem;return true;}else if （StackNum == 2）{cout << "Push Item to Stack2 : " << Elem << endl;if （Sq->top1 + 1 == Sq->top2）return false;Sq->data[--Sq->top2] = Elem;return true;}else{cout << "Stack Num must be 1 or 2！" << endl;return false;}}/* 出栈 */bool Pop（SqStack *Sq, ElemType *ptr, int StackNum）{if （StackNum == 1）{if （Sq->top1 == -1）return false;*ptr = Sq->data[Sq->top1--];cout << "Pop Item from Stack1 :" << *ptr << endl;return true;}else if （StackNum == 2）{if （Sq->top2 == MAXSIZE）return false;*ptr = Sq->data[Sq->top2++];cout << "Pop Item from Stack2 :" << *ptr << endl;return true;}else{cout << "Stack Num must be 1 or 2！" << endl;return false;}}bool StackTraverse（SqStack Sq）{cout << "Traverse Stack ..." << endl;if （StackEmpty（Sq））return false;cout << "Stack1 : ";for （int i = 0; i <= Sq.top1; i++）cout << Sq.data[i] << " ";cout << endl;cout << "Stack2 : ";for （int i = MAXSIZE - 1; i >= Sq.top2; i--）cout << Sq.data[i] << " ";cout << endl;return true;}int main（void）{SqStack Sq;InitStack（&Sq）;for （int i = 0; i < 5; i++）Push（&Sq, i, 1）;for （int i = 5; i < 10; i++）Push（&Sq, i, 2）;StackTraverse（Sq）;int result;Pop（&Sq, &result, 1）;Pop（&Sq, &result, 2）;StackTraverse（Sq）;GetTop（Sq, &result, 1）;GetTop（Sq, &result, 2）;if （！StackEmpty（Sq））cout << StackLength（Sq） << endl;ClearStack（&Sq）;return 0;}

输出为：

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有想法关系时，也就是当一个栈增长时另一个栈在缩短的情况。

还需要注意的一点是必须是同种数据类型的栈，否则不但不能更好地解决问题，反而会使问题更加复杂。