顺序栈以及双栈的设计与测试

data_structure

返回目录

一、顺序栈

1、类设计

template<class T,int MAXSIZE>
class SeqStack
{
public:
    SeqStack();
    ~SeqStack();
private:
    T data[MAXSIZE];        //数据域
    int top;                //栈顶标志
public:
    bool Push(T x);         //压栈
    T Pop();                //出栈
    T Top();                //取首元素
    bool IsEmpty();         //判空
    bool IsFull(void);      //判满
    int Size();             //返回个数
};

2、具体实现

#include "SeqStack.h"
/**
* 无参数构造函数
* 作用:栈顶置空，生成空栈
* @param[in] 无
* @param[out] 无
*/
template<class T, int MAXSIZE>
SeqStack<T,MAXSIZE>::SeqStack()
{
    top = -1;
}
/**
* 析构函数
* 作用:垃圾回收
* @param[in] 无
* @param[out] 无
*/
template<class T, int MAXSIZE>
SeqStack<T, MAXSIZE>::~SeqStack()
{
}
/**
* 压栈操作
* 作用:将元素压入栈顶
* @param[in] T x
* @param[out] 成功返回true
*/
template<class T, int MAXSIZE>
bool SeqStack<T, MAXSIZE>::Push(T x)
{
    if (top==MAXSIZE-1)
    {
        cerr << "上溢" << endl;
        return false;
    }
    top++;
    data[top] = x;
    return true;
}
/**
* 出栈操作
* 作用:将栈顶元素弹出
* @param[in] 
* @param[out]T x
*/
template<class T, int MAXSIZE>
T SeqStack<T, MAXSIZE>::Pop()
{
    if (!IsEmpty())
    {
        T x = data[top];
        top--;
        return x;
    }
    else
    {
        cerr << "下溢" << endl;
    }
}
/**
* 取出栈顶元素
* 作用:将栈顶元素取出
* @param[in]
* @param[out]T x
*/
template<class T, int MAXSIZE>
T SeqStack<T, MAXSIZE>::Top()
{
    if (!IsEmpty())
        return data[top];
    else
        cerr << "下溢" << endl;
}
/**
* 判空
* 作用:判断栈是否空
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MAXSIZE>
bool SeqStack<T, MAXSIZE>::IsEmpty()
{
    return top==-1;
}
/**
* 判空
* 作用:判断栈是否满
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MAXSIZE>
bool SeqStack<T, MAXSIZE>::IsFull()
{
    return top == maxSize - 1; 
}
/**
* 元素个数
* 作用:返回栈元素个数
* @param[in]
* @param[out]  返回元素个数
*/
template<class T, int MAXSIZE>
int SeqStack<T, MAXSIZE>::Size()
{
    if (top!=-1)
    {
        return top+1;
    }
    return 0;
}

3、测试

    SeqStack<int,100> a;
    //压入数据  
    for (int i = 0; i < 10; i++)  
    {  
        a.Push(i);  
    }  
    //栈的大小  
    cout<< "栈元素个数："<<a.Size()<<endl;
    //栈顶元素
    cout << "栈顶元素：" << a.Top() << endl;
    //取栈项数据并将数据弹出栈  
    while (!a.IsEmpty())  
    {  
        cout << "顺序出栈：" << a.Pop() << endl;
    }  

测试截图：

4、总结

• 栈（statck）这种数据结构在计算机中是相当出名的。
• 栈中的数据是先进后出的（FILO）。
• 根据这个特性，可以很好的利用这种结构。
• top()、push()、pop()、empty()是比较常用的方法。

二、双栈

1、类设计

template<class T, int MaxSize>
class SeqStack
{
public:
    SeqStack();                         // 构造函数
    virtual ~SeqStack();               // 析构函数
    void Push(int i, T x);              // 对栈i压栈
    T Pop(int i);                       // 对栈i出栈
    T Top(int i);                       // 取栈i的栈顶元素
    int Size(int i);                    //返回个数
    bool IsEmpty(int i);                // 判栈i是否空
    bool IsFull();                      // 判满
private:
    T data[MaxSize];                    // 数据域
    int top1;                           // 栈顶指针（栈1）
    int top2;                           // 栈顶指针（栈2）
};

2、具体实现

#include "SeqStack.h"
/**
* 无参数构造函数
* 作用:栈顶置空，生成空栈，栈1从头开始，栈2从底开始
* @param[in] 无
* @param[out] 无
*/
template<class T, int MaxSize>
SeqStack<T, MaxSize>::SeqStack()
{
    top1 = -1;
    top2 = MaxSize;
}
/**
* 析构函数
* 作用:垃圾回收
* @param[in] 无
* @param[out] 无
*/
template<class T, int MaxSize>
SeqStack<T, MaxSize>::~SeqStack()
{
}
/**
* 压栈操作
* 作用:将元素压入栈顶，根据标志i判断栈号
* @param[in] T x    int i
* @param[out] 
*/
template<class T, int MaxSize>
void SeqStack<T, MaxSize>::Push(int i,T x)
{
    if (IsFull())
    {
        cerr << "上溢！" << endl;
        exit(1);
    }
    if (i == 1)
    {
        top1++;
        data[top1] = x;
    }
    else if (i == 2)
    {
        top2--;
        data[top2] = x;
    }
    else
    {
        cout << "栈选择错误！默认存入栈1" << endl;
        top1++;
        data[top1] = x;
    }
}
/**
* 出栈操作
* 作用:将栈i顶部元素弹出
* @param[in] 
* @param[out]T x
*/
template<class T, int MaxSize>
T SeqStack<T, MaxSize>::Pop(int i)
{
    if (IsEmpty(i))
    {
        cerr << "下溢！" << endl;
        exit(1);
    }
    T x;
    if (i == 1)
    {
        x = data[top1];
        top1--;
    }
    else if (i == 2)
    {
        x = data[top2];
        top2++;
    }
    return x;
}
/**
* 取出栈顶元素
* 作用:将栈顶元素取出
* @param[in]
* @param[out]T x
*/
template<class T, int MaxSize>
T SeqStack<T, MaxSize>::Top(int i)
{
    if (IsEmpty(i))
    {
        cerr << "下溢！" << endl;
        exit(1);
    }
    if (i == 1)
    {
        return data[top1];
    }
    else if (i == 2)
    {
        return data[top2];
    }
}
/**
* 判空
* 作用:判断栈是否空
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MaxSize>
bool SeqStack<T, MaxSize>::IsEmpty(int i)
{
    if (i == 1)
        return top1 == -1;
    if (i == 2)
        return top2 == MaxSize;
    return false;
}
/**
* 判空
* 作用:判断栈是否满
* @param[in]
* @param[out]  布尔值
*/
template<class T, int MaxSize>
bool SeqStack<T, MaxSize>::IsFull()
{
    return top1 + 1 == top2; 
}
/**
* 元素个数
* 作用:返回栈元素个数
* @param[in]
* @param[out]  返回元素个数
*/
template<class T, int MAXSIZE>
int SeqStack<T, MAXSIZE>::Size(int i)
{
    if (i==1)
    {
        return top1+1;
    } 
    else if (i==2)
    {
        return MAXSIZE-top2;
    }
    else
    {
        cerr<<"error"<<endl;
        exit(1);
    }
}

3、测试

int main()
{
    SeqStack<int, 100> a;
    //压入数据  
    for (int i=0;i<5;i++)
    {
        a.Push(1,i);
        a.Push(2,10-i);
    }
    //栈的大小  
    cout<< "栈1元素个数："<<a.Size(1)<<endl;
    cout<< "栈2元素个数："<<a.Size(2)<<endl;
    //栈顶元素
    cout << "栈1栈顶元素：" << a.Top(1) << endl;
    cout << "栈2栈顶元素：" << a.Top(2) << endl;
    // 出栈
    while (!a.IsEmpty(1))
    {
        cout << "栈1出栈：" << a.Pop(1) << endl;
    }
    while (!a.IsEmpty(2))
    {
        cout << "栈2出栈：" << a.Pop(2) << endl;
    }
    return 0;
}

测试截图：

错误测试：

    //错误数据的测试
    a.Push(3,10);
    a.Push(3,11);

![此处输入图片的描述][4]

4、总结

• 与数组单栈相比，双栈更加节省空间
• 注意错误情况的处理

[4glb.clouddn.com/%E5%8F%8C%E6%A0%8801.png