数据结构——顺序双栈模板类实现

数据结构3.1.2

顺序栈中单栈和双栈（数组的两端分别为栈底）其实极为相似，道理上是一样的，实现的时候只需要多定义一套top标记和bottom标记即可，在判断栈FULL的时候，即是判断两个top是否相遇，这里我用两个元素的数组来定义两个栈顶标记，下面贴出代码（实现方式是多种多样的，如有不当，万望指正）^ _ ^

模板类代码：

#include <iostream>
#include <cassert>
using namespace std;
template<class T>
class DBstack {
public:
    DBstack(int sz = );                      //构造函数/每个栈的起始容量是50
    ~DBstack();                                    //析构函数
    bool Push(T & x, int d);                    //将x推入d代表的栈中，d = 0是1号栈否则为2号栈
    bool Pop(T & x, int d);                     //将d号栈顶元素弹出，其值返回在引用x当中，d = 0是1号栈否则为2号栈
    bool getTop(T & x, int d);                  //得到d号栈的栈顶元素，其值返回带x的引用当中(不弹出)
    bool isEmpty(int d)const;                   //判断d号栈是否为NULL
    bool isFull()const;                         //判断栈是否为满
    int getSize(int d)const;                    //返回d号栈当前元素的个数
    void makeEmpty(int d);                      //清空d号栈
    void output(int d)const;                    //输出d号栈的内容
private:
    T *stack;                                   //双栈数组
    int top[];                                 //分别是两个栈的栈顶指针
    int bottom[];                              //两个栈的栈底指针
    void overflowProcess();                     //栈的溢出处理
};
//函数定义
template<class T>
DBstack<T>::DBstack(int sz) {
    //构造函数
    stack = new T[sz];          //开辟双栈数组
    assert(stack != NULL);      //中断处理
    top[] = bottom[] = -;
    top[] = bottom[] = sz;
}

template<class T>
DBstack<T>::~DBstack() {
    //析构函数，释放程序中的资源
    delete[] stack;
}

template<class T>
bool DBstack<T>::Push(T & x, int d) {
    //将x推入d代表的栈中，d = 0是1号栈否则为2号栈
    if (top[] +  == top[]) {                     //再插入即两个top相遇
        return false;                               //栈满，存储失败
    }
    if ( == d) {
        //推入1号栈
        stack[++top[]] = x;
    }
    else {
        stack[--top[]] = x;
    }
    return true;
}

template<class T>
bool DBstack<T>::Pop(T & x, int d) {
    //将d号栈顶元素弹出，其值返回在引用x当中，d = 0是1号栈否则为2号栈
    if (isEmpty(d)) {                           //检查栈是否为NULL
        return false;                           
    }
    //执行弹出操作
    if ( == d) {
        x = stack[top[]--];
    }
    else {
        x = stack[top[]++];
    }
    return true;
}

template<class T>
bool DBstack<T>::getTop(T & x, int d) {
    //得到d号栈的栈顶元素，其值返回带x的引用当中(不弹出)
    if ( == d) {
        x = stack[top[]];
        return true;
    }
    else {
        x = stack[top[]];
        return true;
    }
    return false;
}

template<class T>
bool DBstack<T>::isEmpty(int d)const {
    //判断d号栈是否为NULL
    if ( == d) {
        if (top[] == bottom[]) {
            return true;
        }
    }
    else {
        if (top[] == bottom[]) {
            return true;
        }
    }
    return false;
}

template<class T>
bool DBstack<T>::isFull()const {
    //判断栈是否为FULL
    if (top[] == top[]) {
        return true;
    }
    return false;
}

template<class T>
int DBstack<T>::getSize(int d) const {
    //返回d号栈当前元素的个数
    if ( == d) {
        return top[] + ;
    }
    else {
        return  - top[];
    }
}

template<class T>
void DBstack<T>::makeEmpty(int d) {
    //set NULL
    if ( == d) {
        top[] = bottom[];
    }
    else {
        top[] = bottom[];
    }
}

template<class T>
void DBstack<T>::output(int d)const {
    //输出任意栈的全部元素
    if ( == d) {
        //输出1号栈的全部元素
        for (int i = bottom[] + ; i <= top[]; i ++) {
            cout << stack[i] << ' ';
        }
    }
    else {
        //输出2号栈的全部元素
        for (int j = bottom[] - ; j >= top[]; j --) {
            cout << stack[j] << ' ';
        }
    }
    cout << endl;
}
           

main测试代码：

int main()
{
    //填充元素测试
    DBstack<int> doubl_stack;                   //创建一个双栈
    for (int i = ; i <= ; i ++) {             //给0号栈填充上5个值
        doubl_stack.Push(i , );
    }
    for (int j = ; j <= ; j++) {              //同上
        doubl_stack.Push(j, );                 //第二个参数非0即可
    }
    doubl_stack.output();                      //输出两个栈中的元素
    doubl_stack.output();

    //弹出元素测试
    int pop_1, pop_2, pop_3, pop_4;
    doubl_stack.Pop(pop_1, );
    doubl_stack.Pop(pop_2, );
    doubl_stack.Pop(pop_3, );
    doubl_stack.Pop(pop_4, );
    doubl_stack.output();                      //输出两个栈中的元素
    doubl_stack.output();

    //得到元素个数测试
    int add_1 = ;
    doubl_stack.Push(add_1, );
    cout << doubl_stack.getSize() << endl;
    cout << doubl_stack.getSize() << endl;

    //set Empty测试
    int pop_5;
    doubl_stack.makeEmpty();
    doubl_stack.output();
    doubl_stack.output();
    doubl_stack.Pop(pop_5 ,);                  //检测pop函数对Empty的处理是否正常

    system("pause");
    return ;
}
           

运行效果：