stack2.h

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>
#include "StackNode.h"                 //链式栈的结点

template <class T>
class Stack2                           //链式栈类
{
  public:
    StackNode<T> *top;                 //指向栈顶结点的指针

    Stack2();                          //构造函数
    ~Stack2();                         //析构函数
    bool isEmpty()const;               //判断栈是否为空
    bool push(T& k);                   //数据元素k入栈
    T pop();                           //出栈
    T get();                           //获得栈顶元素值，未出栈
    friend ostream& operator<<(ostream& out,Stack2<T> &s);
                                       //输出栈中各数据元素值，输出流运算符重载
};

template <class T>
Stack2<T>::Stack2()                    //构造函数,构造空栈
{
    top=NULL;
}

template <class T>
Stack2<T>::~Stack2()                   //析构函数
{
    StackNode<T> *p=top,*q;
    while(p!=NULL)
    {
        q=p;
        p=p->next;
        delete q;
    }
    top=NULL;
}

template <class T>
bool Stack2<T>::isEmpty()const         //判断栈是否为空
{
    return top==NULL;
}

template <class T>
bool Stack2<T>::push(T& k)             //数据元素k入栈
{
    StackNode<T> *q=new StackNode<T>(k);
    q->next=top;                       //q结点作为新的栈顶结点
    top=q;      
    return true;
}  

template <class T>
T Stack2<T>::pop()                     //出栈
{
    T k;
    if(!isEmpty())                     //栈不空
    {
        k=top->data;                   //取得栈顶元素值
        StackNode<T> *p=top;
        top=top->next;                 //后继结点作为新的栈顶结点
        delete p;                      //删除原栈顶结点
    }
    return k;                          //返回栈顶元素值
}

template <class T>
T Stack2<T>::get()                     //获得栈顶元素值，未出栈
{
    if(!isEmpty())
        return top->data;
    else 
        return 0;
}

template <class T>
ostream& operator<<(ostream& out,Stack2<T> &s)
{                                      //输出栈中各数据元素值，输出流运算符重载
    cout<<"链式栈:   ";
    StackNode<T> *p=s.top;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return out;
}