首页 > 代码库 > 数据结构——栈的类定义和实现

数据结构——栈的类定义和实现

#include<iostream>
#include<iomanip>
#include<string>  
#include<stdlib.h> //使用库函数exit()
using namespace std;

template<class Type>
class Stack{
    private:
        Type*data;   //栈元素数组
        int maxSize; //最大栈顶值
        int top;     //栈顶
    public:
        void setStack(int n) /*创建空栈*/
        {
            data=new Type[n];
            if(data=http://www.mamicode.com/=NULL)
            {
                cout<<"overflow!"<<endl;
                exit(1);
            }
            maxSize=n;
            top=-1;
        }

        void freeStack() /*销毁栈*/
        {
            free(data);
        }

        int stackSize() /*栈的长度*/
        {
            return (top+1);
        }

        bool isEmpty() /*判断栈是否为空*/
        {
            if(top==-1)
                return true;
            return false;
        }

        bool isFull() /*判断栈是否为满*/
        {
            if(top==maxSize-1)
                return true;
            return false;
        }

        Type Peek()  /*栈存在且非空则返回栈顶元素*/
        {
            if(top==-1)
            {
                cerr<<"栈空!"<<endl;
                exit(1);
                exit(1);
            }
            return (data[top]);
        }

        void Push(Type item)/*入栈*/
        {
            if(top==maxSize-1)
            {
                cerr<<"栈满!"<<endl;
                exit(1);
            }
            top++;
            data[top]=item;
        }

        Type Pop(Type e) /*栈非空则删除栈顶元素并用e返回其值*/
        {
            if(top==-1)
            {
                cerr<<"栈空!"<<endl;
                exit(1);
            }
            top--;
            return data[top+1];
        }
        void clearStack() /*清空栈*/
        {
            top=-1;
        }

        void stackTraverse(void (*visit)(Type*)) /*遍历栈,形参visit为函数指针(指向函数的指针变量)*/
        {
            while(top!=-1)
            {
                visit(data);
                top--;
            }

        }
};

/*测试*/
typedef struct Stu{
    char name[10];
    char stu_num[10];
    int age;
    int score;
}Type;

void StackPrintElem(Type*e) /*输出栈中元素*/
{
    cout<<"姓名 学号 年龄 成绩:"<<endl;
    cout<<e->name<<setw(8)<<e->stu_num;
    cout<<setw(4)<<e->age;
    cout<<setw(5)<<e->score<<endl;
}

void main()
{
    Type e;
    Stack<Type> S;
    int n=8;

    S.setStack(n);

    cout<<"压栈第一个元素:"<<endl;
    strcpy(e.name,"stu1");
    strcpy(e.stu_num,"100001");
    e.age=20;
    e.score=87;
    S.Push(e);
    StackPrintElem(&S.Peek());
    cout<<endl;

    if(S.isEmpty())
        cout<<"栈S空!"<<endl;
    else
        cout<<"栈S非空!"<<endl;
    cout<<endl;

    cout<<"压入第二个元素:"<<endl;
    strcpy(e.name,"stu3");
    strcpy(e.stu_num,"100002");
    e.age=21;
    e.score=90;
    S.Push(e);
    StackPrintElem(&S.Peek());
    cout<<endl;

    cout<<"现在栈S的长度:"<<S.stackSize()<<endl<<endl;
    cout<<"将元素e弹出栈!"<<endl;
    S.Pop(e);
    StackPrintElem(&e);
    cout<<endl;

    cout<<"栈的剩余元素:"<<endl;
    S.stackTraverse(StackPrintElem);
    cout<<endl;

    if(S.isEmpty())
        cout<<"栈S为空!"<<endl;
    else 
        cout<<"栈S非空!"<<endl;
    cin.get();
}