双端栈

【概述】

早期计算机中，为更有效的利用存储空间，在顺序栈的基础上引入了双端栈，其又被称共享栈

双端栈令两个顺序栈共享一个数组空间，将栈底分别设为数组的两端，栈顶从两端向中间延伸，以达到利用同一个数组空间的目的

双端栈的两个栈的共享空间相互调节，只有在整个数组存满后才会发生上溢，有效地利用了存储空间

双端栈的实现类如下：

#define N 50 + 5 //申请空间个数
template <typename T> 
class ShStack {
  public:
    ShStack();                   //初始化栈
    int getLen(int i);           //求栈长
    bool empty(int i);           //判空
    bool full();                 //判满
    bool pop(int i, T &elem);    //出栈
    bool push(int i, T elem);    //入栈
    bool getTop(int i, T &elem); //取栈顶
    void print(int i);           //输出
  private:
    T data[N];                   //栈空间
    int top1;                    //1号栈指针
    int top2;                    //2号栈指针
};

【初始化】

在初始化时，栈为空栈，栈中无元素，对于 $1$ 号栈，栈指针设为存储空间顶部 -1，对于 $2$ 号栈，栈指针设为存储空间尾部 N

template <typename T> 
ShStack<T>::ShStack() { //初始化栈
    top1 = -1;          //1号栈栈底为头部
    top2 = N;           //2号栈栈底为尾部
}

【求栈长】

对于双端栈来说，其通过指定的栈号 i 来求对应栈的长度

若求 $1$ 号栈的栈长，与顺序栈相同，直接返回对应栈指针 +1 的位置 top1+1 即可

若求 $2$ 号栈的栈长，则需要从存储空间的尾部 N 开始计算，减去该栈栈指针 top2 的位置即可

template <typename T>
int ShStack<T>::getLen(int i) { //求栈长
    if (i == 1) //判断1号栈
        return top1 + 1;
    else       //判断2号栈
        return N - top2;
}

【判空】

对于双端栈来说，其通过指定的栈号 i 来判断对应栈是否为空

在判断时，只需判断对应栈的栈指针 top1、top2 是否为对应初始值即可

template <typename T>
bool ShStack<T>::empty(int i) { //判空
    if (i == 1) { //判断1号栈
        if (top1 == -1)
            return true;
        return false;
    } 
    else {       //判断2号栈
        if (top2 == N)
            return true;
        return false;
    }
}

【判满】

对于双端栈来说，其两个栈空间是共享的，不存在一个栈满另一个栈不满的情况，只可能两个栈所占用的空间占满了整个存储空间

因此，在判满时，只需要判断两个栈指针的位置 top1 与 top2 是否相邻即可

template <typename T> 
bool ShStack<T>::full() { //判满
    if (top1 == top2 - 1)
        return true;
    return false;
}

【出栈】

对于双端栈来说，其通过指定的栈号 i 来对指定栈进行出栈操作，但在出栈前，要对对应栈进行下溢判断

之后，若是 $1$ 号栈出栈，其栈顶元素出栈后令栈指针 top1 后移一位；若是 $2$ 号栈出栈，其栈顶元素出栈后令栈指针 top2 前移一位

template <typename T> 
bool ShStack<T>::pop(int i, T &elem) { //出栈
    if (empty(i)) //下溢判断
        return false;
    if (i == 1)   //1号栈入栈
        elem = data[top1--];
    else          //2号栈入栈
        elem = data[top2++];
    return true;
}

【入栈】

对于双端栈来说，其通过指定的栈号 i 来对指定栈进行出栈操作，但在入栈前，要对整个栈进行上溢判断

之后，若是 $1$ 号栈入栈，其先令栈指针 top1 前移一位，再将元素放入栈中；若是 $2$ 号栈入栈，其先令栈指针 top2 后移一位，再将元素放入栈中

template <typename T> 
bool ShStack<T>::push(int i, T elem) { //入栈
    if (full()) //上溢判断
        return false;
    if (i == 1) //1号栈入栈
        data[++top1] = elem;
    else        //2号栈入栈
        data[--top2] = elem;
    return true;
}

【取栈顶】

对于双端栈来说，其通过指定的栈号 i 来对指定栈进行取栈顶操作，但在取栈顶元素前，要对对应栈进行下溢判断

之后，根据要取的栈号 i，取对应栈指针的元素即可

template <typename T> 
bool ShStack<T>::getTop(int i, T &elem) { //取栈顶
    if (empty(i)) //下溢判断
        return false;
    if (i == 1)   //取1号栈栈顶
        elem = data[top1];
    else          //取2号栈栈顶
        elem = data[top2];
    return true;
}

【输出】

对于双端栈来说，其通过指定的栈号 i 来对指定栈进行输出操作

在输出时，从指定栈的栈顶开始，将栈中所有元素依次出栈，进行输出即可

template <typename T> 
void ShStack<T>::print(int i) { //输出
    int elem;
    while (!empty(i)) { //将所有元素依次出栈进行输出
        pop(i, elem);
        cout << elem << " ";
    }
    cout << endl;
}