线性表-链表栈

  1: //linkstack.cpp
  2: 
  3: #ifndef LINKSTACK_CPP_CPP
  4: #define LINKSTACK_CPP_CPP
  5: 
  6: #include <iostream>
  7: #include "linkstack.h"
  8: 
  9: template<class T>
 10: LinkStack<T>::LinkStack()
 11: {
 12:   head = new Node<T>;
 13:   head->next = NULL;
 14: }
 15: 
 16: 
 17: template<class T>
 18: LinkStack<T>::LinkStack(T data[],int size)
 19: {
 20:   head = new Node<T>;
 21:   Node<T> * newNode;
 22:   head->next = NULL;
 23:   for(int i = 0; i < size; ++i)
 24:   {
 25:     newNode = new Node<T>;
 26:     newNode->data = data[i];
 27:     newNode->next = head->next;
 28:     head->next = newNode;
 29:   }
 30: } 
 31: 
 32: template<class T>
 33: LinkStack<T>::~LinkStack()
 34: {
 35:   Node<T> * ptrNode,* tempNode;
 36:   ptrNode = head;
 37:   while(ptrNode)
 38:   {
 39:     tempNode = ptrNode;
 40:     ptrNode = ptrNode->next;
 41:     delete tempNode;
 42:   }
 43:   head = NULL;
 44: }
 45: 
 46: template<class T>
 47: void LinkStack<T>::Push(const T &item)
 48: {
 49:   Node<T> * newNode = new Node<T>;
 50:   newNode->data = item;
 51:   newNode->next = head->next;
 52:   head->next = newNode;
 53: }
 54: 
 55: template<class T>
 56: T LinkStack<T>::Pop()
 57: {
 58:   T data = head->next->data;
 59:   head->next = head->next->next;
 60:   return data;
 61: }
 62: 
 63: template<class T>
 64: T LinkStack<T>::GetTop()
 65: {
 66:   T data = head->next->data;
 67:   return data;
 68: }
 69: 
 70: template<class T>
 71: bool LinkStack<T>::Empty() const
 72: {
 73:   return (NULL == head->next);
 74: }
 75: 
 76: template<class T>
 77: void LinkStack<T>::Clear()
 78: {
 79:   head->next = NULL;
 80: }
 81: 
 82: #endif

  1: //linkstack.h
  2: 
  3: #ifndef LINKSTACK_H_H
  4: #define LINKSTACK_H_H
  5: 
  6: #include <iostream>
  7: using namespace std;
  8: 
  9: template<class T>
 10: struct Node
 11: {
 12: 
 13:   T data;
 14:   Node<T> * next;
 15: public:
 16:   Node()
 17:   {
 18: 
 19:   }
 20: 
 21:   Node(T _data,Node * _next = NULL)
 22:   {
 23:     data = _data;
 24:     next = _next;
 25:   }
 26: };
 27: 
 28: template<class T>
 29: class LinkStack
 30: {
 31: private:
 32:   Node<T> * head;//top
 33: 
 34: public:
 35:   LinkStack();
 36:   LinkStack(T data[],int size);
 37:   ~LinkStack();
 38: 
 39:   void Push(const T &item);
 40:   T Pop();
 41:   T GetTop();
 42: 
 43:   bool Empty() const;
 44: 
 45:   void Clear();
 46: 
 47: };
 48: 
 49: #endif

  1: //test.cpp
  2: #include "linkstack.h"
  3: #include "linkstack.cpp"
  4: #include <iostream>
  5: using namespace std;
  6: 
  7: int main(int argc, char *argv[])
  8: {
  9:   int data[] = {1,2,3,4,5,6,7,8,9,10};
 10:   LinkStack<int> stack(data,10);
 11: 
 12:   while(!stack.Empty())
 13:   {
 14:     cout<<stack.Pop()<<endl;
 15:   }
 16: 
 17:   return 0;
 18: }