数据结构——顺序双栈模板类实现-蒲公英云

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

数据结构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;
}