C++ 利用模板类链表实现栈结构

C++ 利用模板类链表实现栈结构

运行环境： Dev-c++ 5.11

日期：2018.10.11

主程序 main.cpp

//Written by Xuebi
//本程序利用链表实现栈结构，实现Pop,Push,Top基本功能 
//链表采用前插法构建，不存在空结点 
#include <iostream>
using namespace std;
template <class T> class Stack;
template <class T>
class ChainNode
{
      friend class Stack<T>;
private:
      ChainNode*p;
      T data;
      ChainNode(T element):data(element),p(0){};
};
template <class T>
class Stack
{
private:
      ChainNode<T>*top;
public:
      Stack();
      ~Stack();
      T Top();
      void Pop();
      void Push(const T&element);
      bool IfNonEmpty();
      void MakeAllEmpty();
};
template <class T>
Stack<T>::Stack()
{
      top=0;
}
template <class T>
void Stack<T>::Pop()
{
      if(IfNonEmpty())
      {
            ChainNode<T>*A=top;
            top=top->p;
            delete A;
      }
      else
            cout<< "cannot Pop!"<<endl;;
}
template <class T>
void Stack<T>::Push(const T&element)
{
      ChainNode<T>*newnode=new ChainNode<T>(element);
      newnode->p=top;
      top=newnode;
}
template <class T>
T Stack<T>::Top()//返回栈顶data 
{
      if(IfNonEmpty())
      return top->data;
      else
            {
             cout<< "cannot Top! Return 0"<<endl;
             return NULL;
   }
   
}
template <class T>
bool Stack<T>::IfNonEmpty()//判断栈结构是否为空 
{
      if(top==0)
            return 0;
      else
            return 1;
}
template <class T>
void Stack<T>:: MakeAllEmpty()//破坏栈结构，释放栈 
{
      while(IfNonEmpty())
            {Pop();}
      cout<<"All Empty!"<<endl;
}
template <class T>
Stack<T>::~Stack()//调用MakeALLEmpty函数进行析构 
{
      MakeAllEmpty();
      delete top;
}
int main()
{
      cout << "Hello world!" << endl;
      Stack<int> st;
      st.Push(1);
      st.Push(2);
      st.Push(3);
      st.Push(4);
      cout<<st.Top()<<endl;//输出4 
      st.Pop();
      st.Pop();
      st.Pop();
      st.Pop();
   cout<<st.Top()<<endl;
      st.Pop();
      cout<<st.Top()<<endl;
      st.MakeAllEmpty();
      cout<<"After Make AllEmpty, we push and push!"<<endl;
      st.Push(1);
      st.Push(2);
      st.Push(3);
      st.Push(4);
      cout<<st.Top()<<endl;
      st.Pop();
      cout<<st.Top()<<endl;
      st.Pop();
      cout<<st.Top()<<endl;
}