[数据结构与算法]双向栈的基础操作

双向栈：

一个双向栈是在同一向量空间实现的两个栈，它们的栈底分别设在向量空间的两端。

双向栈有什么优点？
入栈时，各自的栈顶向中间伸展，仅当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以做到互补余缺，使得每个栈的可利用空间均有可能超过n/2。这不仅减少了栈溢出的可能性，也增加了空间的利用率。
什么时候用双向栈？
可以看到，当两个栈对空间的需求有相反关系的时候，也就是一个栈的空间增长，另一个栈的空间缩小时，可以使用双向栈。

在会手写栈的基础上，不难写出双向栈的代码。
下面给出本人写的C语言的双向栈（只有一些基础的操作）：

#include<stdio.h>
#include<stdlib.h>
enum boolean{FALSE,TRUE};
typedef enum boolean Bool;
typedef int ElementType;

struct DSstack{
    int size,top1,top2;
    ElementType *elements;
};

typedef struct DSstack dsstack;

void InitStack(dsstack *s,int sz){
    s->size=sz;
    s->elements=(ElementType *)malloc(sizeof(ElementType)*s->size);
    s->top1=-1;
    s->top2=sz;
}
void FreeStack(dsstack *s){
    free(s->elements);
}
void MakeEmpty(dsstack *s){
    s->top1=-1;
    s->top2=s->size;
}
Bool IsFull(dsstack *s){
    return (Bool)(s->top1+1==s->top2);
}
Bool IsEmpty(dsstack *s,int i){
    if(!i) return (Bool)(s->top1==-1);
    else return (Bool)(s->top2==s->size);
}
void Push(dsstack *s,int i,ElementType a){
    if(!i){
        if(IsFull(s)){
            printf("stack is FULL !\n");
            exit(0);
        }
        else s->elements[++s->top1]=a;
    }
    else{
        if(IsFull(s)){
            printf("stack is FULL!\n");
            exit(0);
        }
        s->elements[--s->top2]=a;
    }
}
void Pop(dsstack *s,int i){
    if(!i){
        if(IsEmpty(s,i)){
            printf("stack is EMPTY!\n");
            exit(0);
        }
        else s->top1--;
    }
    else{
        if(IsEmpty(s,i)){
            printf("stack is EMPTY!\n");
            exit(0);
        }
        else s->top2++;
    }
}
ElementType GetTop(dsstack *s,int i){
    if(!i){
        if(IsEmpty(s,0)){
            Printf("stack is EMPTY!\n");
            exit(0);
        }
        else
            return s->elements[s->top1];        
    }
    else{
        if(IsEmpty(s,1)){
            printf("stack is EMPTY!\n");
            exit(0);
        }
        else 
            return s->elements[s->top2];
    }
}