栈

栈的逻辑结构

栈：限定仅在表尾进行插入和删除操作的线性表。
空栈：不含任何数据元素的栈。
允许插入和删除的一端称为栈顶，另一端称为栈底。

栈的示意图

栈的操作特性：后进先出

顺序栈类的声明：

顺序栈的实现——入栈
操作接口： void Push( T x );
template
void seqStack::Push ( T x)
{
if (top==MAX_SIZE-1) throw “溢出”;
top++;
data[top]=x;
}

顺序栈的实现—判断是否是空栈
操作接口： bool Empty( )
template
bool seqStack::Empty ()
{
if (top==-1)
return true;
return false;
}

顺序栈的实现——取栈顶
操作接口： T GetTop( );
template
T seqStack::GetTop ( )
{
if (Empty()) throw ”空栈” ；
return data[top];
}

顺序栈的实现——出栈
操作接口： T Pop( );
template
T seqStack:: Pop ( )
{
if (top==-1) throw “溢出”;
x=data[top];
top–;
return x;
}

两栈共享空间：
使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。
栈1的底固定在下标为0的一端；
栈2的底固定在下标为StackSize-1的一端。
top1和top2分别为栈1和栈2的栈顶指针；
Stack_Size为整个数组空间的大小（图中用S表示）；

两栈共享空间类的声明：
const int Stack_Size=100;
template
class BothStack
{
public:
BothStack( );
~BothStack( );
void Push(int i, T x);
T Pop(int i);
T GetTop(int i);
bool Empty(int i);
private:
T data[Stack_Size];
int top1, top2;
};

两栈共享空间的实现——插入
操作接口：void Push(int i, T x) ;

1. 如果栈满，则抛出上溢异常；
2. 判断是插在栈1还是栈2；
   2.1 若在栈1插入，则
   2.1.1 top1加1;
   2.1.2 在top1处填入x；
   2.2 若在栈2插入，则
   2.2.1 top2减1;
   2.2.2 在top2处填入x；

template
T BothStack::Pop(int i){
if (i1) {
if (top1 -1) throw “下溢”;
return data[top1–];
}
if (i2) {
if (top2StackSize) throw “下溢”;
return data[top2++];
}
}