数据结构与算法：队列 arrayQueue

#ifndef arrayQueue_
#define arrayQueue_

#include "queue.h"
#include "myExceptions.h"
#include <sstream>

using namespace std;

template<class T>
class arrayQueue : public queue<T>
{
   public:
      arrayQueue(int initialCapacity = 10);
      ~arrayQueue() {delete [] queue;}
      bool empty() const {return theFront == theBack;}
      int size() const
          {return (theBack - theFront + arrayLength) % arrayLength;}
      T& front()
         {// 返回头元素的引用
            if (theFront == theBack)
               throw queueEmpty();
            return queue[(theFront + 1) % arrayLength];
         }
      T& back()
         {// 返回尾元素的引用
            if (theFront == theBack)
               throw queueEmpty();
            return queue[theBack];
         }
      void pop()
           {// 删除首元素
              if (theFront == theBack)
                 throw queueEmpty();
              theFront = (theFront + 1) % arrayLength;
              queue[theFront].~T();  // T 的析构函数
           }
      void push(const T& theElement);  // 把元素 theElement 加入队尾
   private:
      int theFront;       // 逆时针方向，指向列首元素的下一个位置
      int theBack;        // 尾元素的位置
      int arrayLength;    // 队列容量
      T *queue;           // 元素数组
};

template<class T>
arrayQueue<T>::arrayQueue(int initialCapacity)
{// Constructor.
   if (initialCapacity < 1)
   {ostringstream s;
    s << "Initial capacity = " << initialCapacity << " Must be > 0";
    throw illegalParameterValue(s.str());
   }
   arrayLength = initialCapacity;
   queue = new T[arrayLength];
   theFront = 0;
   theBack = 0;
}

template<typename T>
void arrayQueue<T>::push(const T& theElement)
{// 把元素 theElement 加入队列
   
    if ((theBack + 1) % theFront == theFront)
    {// 加倍数组长度
        // 分配新的数组空间
        T* newQueue = new T[theFront * 2];

        // 把原数组复制到新数组
        int start = (theFront + 1) % arrayLength;
        if (start < 2)
            // 没有形成环
            copy(queue + start, queue + arrayLength, newQueue);
        else
        {// 队列形成环
            copy(queue + start, queue + theFront, newQueue);
            copy(queue, queue + theBack + 1, newQueue + arrayLength - start);
        }
        theFront = 2 * arrayLength - 1;
        theBack = arrayLength - 2;          // 队列长度 - 1
        arrayLength *= 2;
        delete [] queue;
        queue = newQueue;
   }

   // 把元素 theElement 插入队列的尾部
    theBack = (theBack + 1) % arrayLength;
    queue[theBack] = theElement;
}

#endif