双栈(Dual Stack) 1. 双栈的概念 1.1 双栈的定义 双栈是指两个顺序栈，是一种特殊的顺序栈。 1.2 双栈中各元素的逻辑及存储关系 双栈共享一个地址连续的存储单元。即程序同时需要两个栈时，可以定义一个足够大的栈空间，该空间的两端分别设为两个栈的栈底，用bottom[0]=-1和bottom[1]=maxSize指示。 压入数据时，让两个栈的栈顶top[0]和top[1]都向中间伸展，如果指示栈顶的指针top[0]+1等于另一个栈顶的指针top[1]时两栈已满。 每次进栈时top[0]加1或top[1]减1，而退栈时top[0]减1或top[1]加1。 如果top[0] == -1且top[1] == maxSize两栈为空。 双栈的模型： 

在双栈的情形下：  (1)栈的初始化语句：bottom[0]=top[0]=-1，bottom[1]=top[1]=maxSize。  (2)栈满的条件：top[0]+1 == top[1]。  (3)栈空的条件：bottom[0]==top[0]==-1且bottom[1]==top[1]==maxSize。 2. 双栈的实现 2.1 双栈的类定义及其操作的实现 文件：DualStack.h

#ifndef DUAL_STACK_H_

#define DUAL_STACK_H_

#include

#include

#include

using namespace std;

const int defaultSize = 50;         //默认栈空间大小 const int stackIncreament = 20;     //栈溢出时扩展空间的增量 const int n = 2;                    //设置n=2个栈共有一个栈空间

template class DualStack { public:     DualStack(int sz = defaultSize);        //构造函数     ~DualStack();                           //析构函数 public:     bool Push(const T& x, int d) ;      //新元素x进栈     bool Pop(T& x, int d);              //栈顶元素出栈，并将该元素的值保存至x     bool getTop(T& x, int d) const;     //读取栈顶元素，并将该元素的值保存至x     bool IsEmpty() const;               //判断栈是否为空     bool IsFull() const;                //判断栈是否为满     int getSize() const;                //计算栈中元素个数     void MakeEmpty();                   //清空栈的内容     void overflowProcess();             //栈的溢出处理 public:     template     friend ostream& operator