数据结构（6）队列

队列遵循先进先出（FIFO）的规则，也是可以用数组或链表来描述

数组实现方式中，循环队列是个不错的方案，只是要注意插入新元素前要检查一下队列有没有满，否则空队列和满队列都会造成队首元素和队末元素的索引相同

template<class T>
class arrayQueue
{
public:
    arrayQueue(int initialCapacity = 10);
    ~arrayQueue() { delete[] queue; }
    bool empty() const { return theFront == theBack; }
    int size() const
    {
        return (theBack - theFront + arrayLength) % arrayLength;
    }
    T& front()
    {// return front element
        if (theFront == theBack)
            throw queueEmpty();
        return queue[(theFront + 1) % arrayLength];
    }
    T& back()
    {// return theBack element
        if (theFront == theBack)
            throw queueEmpty();
        return queue[theBack];
    }
    void pop()
    {// remove theFront element
        if (theFront == theBack)
            throw queueEmpty();
        theFront = (theFront + 1) % arrayLength;
        queue[theFront].~T();  // destructor for T
    }
    void push(const T& theElement);
private:
    int theFront;       // 1 counterclockwise from theFront element
    int theBack;        // position of theBack element
    int arrayLength;    // queue capacity
    T* queue;           // element array
};

下面是构造函数和插入元素

插入元素时要检查队列是否满了，满了就双倍数组长度并把所有元素按顺序平移到开头

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<class T>
void arrayQueue<T>::push(const T& theElement)
{// Add theElement to queue.

   // increase array length if necessary
    if ((theBack + 1) % arrayLength == theFront)
    {// double array length
       // allocate a new array
        T* newQueue = new T[2 * arrayLength];

        // copy elements into new array
        int start = (theFront + 1) % arrayLength;
        if (start < 2)
            // no wrap around
            copy(queue + start, queue + start + arrayLength - 1, newQueue);
        else
        {  // queue wraps around
            copy(queue + start, queue + arrayLength, newQueue);
            copy(queue, queue + theBack + 1, newQueue + arrayLength - start);
        }

        // switch to newQueue and set theFront and theBack
        theFront = 2 * arrayLength - 1;
        theBack = arrayLength - 2;   // queue size arrayLength - 1
        arrayLength *= 2;
        queue = newQueue;
    }

    // put theElement at the theBack of the queue
    theBack = (theBack + 1) % arrayLength;
    queue[theBack] = theElement;
}

用链表描述也很简单

template<class T>
class linkedQueue : public queue<T>
{
   public:
      linkedQueue(int initialCapacity = 10)
            {queueFront = NULL; queueSize = 0;}
      ~linkedQueue();
      bool empty() const 
           {return queueSize == 0;}
      int size() const
          {return queueSize;}
      T& front()
         {
            if (queueSize == 0)
               throw queueEmpty();
            return queueFront->element;
         }
      T& back()
         {
            if (queueSize == 0)
               throw queueEmpty();
            return queueBack->element;
         }
      void pop();
      void push(const T&);
   private:
      chainNode<T>* queueFront;  // pointer to queue front
      chainNode<T>* queueBack;   // pointer to queue back
      int queueSize;             // number of elements in queue
};

template<class T>
linkedQueue<T>::~linkedQueue()
{// Destructor.
   while (queueFront != NULL)
   {// delete front node
      chainNode<T>* nextNode = queueFront->next;
      delete queueFront;
      queueFront = nextNode;
   }
}

template<class T>
void linkedQueue<T>::pop()
{// Delete front element.
   if (queueFront == NULL)
      throw queueEmpty();

   chainNode<T>* nextNode = queueFront->next;
   delete queueFront;
   queueFront = nextNode;
   queueSize--;
}


template<class T>
void linkedQueue<T>::push(const T& theElement)
{// Add theElement to back of queue.

   // create node for new element
   chainNode<T>* newNode = new chainNode<T>(theElement, NULL);

   // add new node to back of queue
   if (queueSize == 0)
      queueFront = newNode;       // queue empty
   else 
      queueBack->next = newNode;  // queue not empty
   queueBack = newNode;

   queueSize++;
}