C++栈的实现

/*

 * C++栈的实现

 * Lzy     2011-七夕

 */

 

#include

using namespace std;

 

template <class T>

class SeqStack;       //前向声明

 

template <class T>

class LinkNode                //定义模板类节点

{

private:

    T data;                    //数据域

    LinkNode<T> *next;       //指针域

public:

    friend class SeqStack<T>;          //声明SeqStack为友元类

};

 

template <class T>

class SeqStack

{

protected:

    LinkNode<T> *top;             //头指针

public:

    SeqStack();

    bool IsEmpty() const {return top->next == NULL;}

    bool Push(const T &x);                //元素x入栈

    bool Pop(T &x);                        //元素出栈,保存在X

    ~SeqStack(){delete top;}

};

 

/*

 * 出栈

 */

template <class T>

bool SeqStack<T>::Pop(T &x)

{

    if(IsEmpty() == true)

        return false;

 

    LinkNode<T> *p = top->next;

    x = p->data;                  //数据弹出

    top->next = p->next;

    delete p;                      //删除P节点

    return true;

}

 

/*

 * 入栈

 */

template <class T>

bool SeqStack<T>::Push(const T &x)

{

    LinkNode<T> *p = new LinkNode<T>;  //分配新的空间

    p->data = x;                      //数据存入

    p->next = top->next;

    top->next = p;                        //插到头点后

    return true;

}

 

/*

 * 初始化栈

 */

template <class T>

SeqStack<T>::SeqStack()

{

    top = new LinkNode<T>;       //栈顶分配空间

    top->next = NULL;                     //栈指针域指向空

}

 

/*

 * 测试程序

 */

int main(void)

{

    SeqStack<int> L;

 

    for(int i=0; i<5; i++)

        L.Push(i);

 

    int temp;

    for(int i=0; i<5; i++)

    {

            L.Pop(temp);

            cout<<" "<<temp<<endl;

    }

 

    return 0;

}

 

源码： C++栈的实现.rar