数据结构：模板实现栈和队列

（一）模板实现栈

#pragma once typedef unsigned int size_t; template <class T> class Stack { public:  Stack()   :_array(NULL)   ,_top(-1)   ,_capacity(0)  {}  ~Stack()  {   if(_array)   {    delete[] _array;   }  } public:  void Push(const T& num)  {   _CheckCapacity();   _array[++_top] = num;  }  void Pop()  {   if(Empty())   {    printf("Empty!");   }   else   {    _top--;   }  }  T& GetTop()  {   return _array[_top];  }  void PrintStack()  {   cout<<array[_top];  }  size_t Size()  {   return _top + 1;  }  bool Empty()  {   return _top == -1;  } private:  void _CheckCapacity()  {   if(_array == NULL)   {    _capacity = 3;    _array = new T[_capacity];    return;   }   if(_capacity = _top + 1)   {    _capacity *= 2;    T* tmp = new T[_capacity];    for(size_t i = 0; i <=(int)_top; i++)    {     tmp[i] = _array[i];    }    _array = tmp;   }  } private:  T* _array;  int _top;                 //下标  size_t _capacity; };

2.模板实现队列

#pragma once template <class T> struct Node {  T _data;  Node<T>* _next;  Node(const T& d)   :_data(d)   ,_next(NULL);  {} }; template <class T> class Queue { public:  Queue()   :_head(NULL)   ,_tail(NULL)   ,_size(0)  {}  ~Queue  {   if(_head)    delete _head;   if(_tail)    delete _tail;  } public:  void Push(const T& d)  {   if(_head == NULL)   {    _head = _tail = new Node<T>(d);   }   else   {    _tail->_next = new Node<T>(d);    _tail = _tail->_next;   }   _size++;  }  void Pop()  {   if(_head == NULL)   {    cout<<"Empty!"<<endl;    return;   }   else if(_head == _tail)   {    delete _head;    _head = _tail = NULL;   }   else   {    Node<T>* tmp = _head;    _head = _head->_next;    delete tmp;   }   _size--;  }  bool Empty()  {   return _head == NULL;  }  size_t Size()  {   return _size;  }  T& Front()  {   assert(_head);   return _head->_data;  }  T& Back()  {   assert(_tail);   return _tail->_data;  } private:  Node<T>* _head;  Node<T>* _tail;  size_t _size; };