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

ゞ浴缸里的玫瑰 2022-06-07 06:44 196阅读 0赞

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

#include <iostream>
    #include <cassert>
    using namespace std;
    template<class T>
    class DBstack {
    public:
        DBstack(int sz = 100);                      //构造函数/每个栈的起始容量是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[2];                                 //分别是两个栈的栈顶指针
        int bottom[2];                              //两个栈的栈底指针
        void overflowProcess();                     //栈的溢出处理
    };
    //函数定义
    template<class T>
    DBstack<T>::DBstack(int sz) {
        //构造函数
        stack = new T[sz];          //开辟双栈数组
        assert(stack != NULL);      //中断处理
        top[0] = bottom[0] = -1;
        top[1] = bottom[1] = 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[0] + 1 == top[1]) {                     //再插入即两个top相遇
            return false;                               //栈满，存储失败
        }
        if (0 == d) {
            //推入1号栈
            stack[++top[0]] = x;
        }
        else {
            stack[--top[1]] = 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 (0 == d) {
            x = stack[top[0]--];
        }
        else {
            x = stack[top[1]++];
        }
        return true;
    }
    
    template<class T>
    bool DBstack<T>::getTop(T & x, int d) {
        //得到d号栈的栈顶元素，其值返回带x的引用当中(不弹出)
        if (0 == d) {
            x = stack[top[0]];
            return true;
        }
        else {
            x = stack[top[1]];
            return true;
        }
        return false;
    }
    
    template<class T>
    bool DBstack<T>::isEmpty(int d)const {
        //判断d号栈是否为NULL
        if (0 == d) {
            if (top[0] == bottom[0]) {
                return true;
            }
        }
        else {
            if (top[1] == bottom[1]) {
                return true;
            }
        }
        return false;
    }
    
    template<class T>
    bool DBstack<T>::isFull()const {
        //判断栈是否为FULL
        if (top[0] == top[1]) {
            return true;
        }
        return false;
    }
    
    template<class T>
    int DBstack<T>::getSize(int d) const {
        //返回d号栈当前元素的个数
        if (0 == d) {
            return top[0] + 1;
        }
        else {
            return 100 - top[1];
        }
    }
    
    template<class T>
    void DBstack<T>::makeEmpty(int d) {
        //set NULL
        if (0 == d) {
            top[0] = bottom[0];
        }
        else {
            top[1] = bottom[1];
        }
    }
    
    template<class T>
    void DBstack<T>::output(int d)const {
        //输出任意栈的全部元素
        if (0 == d) {
            //输出1号栈的全部元素
            for (int i = bottom[0] + 1; i <= top[0]; i ++) {
                cout << stack[i] << ' ';
            }
        }
        else {
            //输出2号栈的全部元素
            for (int j = bottom[1] - 1; j >= top[1]; j --) {
                cout << stack[j] << ' ';
            }
        }
        cout << endl;
    }

main测试代码：

int main()
    {
        //填充元素测试
        DBstack<int> doubl_stack;                   //创建一个双栈
        for (int i = 1; i <= 5; i ++) {             //给0号栈填充上5个值
            doubl_stack.Push(i , 0);
        }
        for (int j = 1; j <= 7; j++) {              //同上
            doubl_stack.Push(j, 1);                 //第二个参数非0即可
        }
        doubl_stack.output(0);                      //输出两个栈中的元素
        doubl_stack.output(1);
    
        //弹出元素测试
        int pop_1, pop_2, pop_3, pop_4;
        doubl_stack.Pop(pop_1, 0);
        doubl_stack.Pop(pop_2, 1);
        doubl_stack.Pop(pop_3, 1);
        doubl_stack.Pop(pop_4, 1);
        doubl_stack.output(0);                      //输出两个栈中的元素
        doubl_stack.output(1);
    
        //得到元素个数测试
        int add_1 = 100;
        doubl_stack.Push(add_1, 0);
        cout << doubl_stack.getSize(0) << endl;
        cout << doubl_stack.getSize(1) << endl;
    
        //set Empty测试
        int pop_5;
        doubl_stack.makeEmpty(0);
        doubl_stack.output(0);
        doubl_stack.output(1);
        doubl_stack.Pop(pop_5 ,0);                  //检测pop函数对Empty的处理是否正常
    
        system("pause");
        return 0;
    }

运行效果：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220607/ee0e924278e84a79bd4dc26ba9b2ad7d.png