數據結構：模板實現棧和隊列

（一）模板實現棧

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