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;
}