队列

/*
 * 测试函数
 * arrayQueue.cpp
*/
#include<iostream>
#include"myexceptions.h"
#include"arrayqueue.h"

using namespace std;

int main(void)
{
   arrayQueue<int> q(4);

   //在队列中添加一些元素
   q.push(1);
   cout <<"Queue rear is "<<q.back()<<endl;
   q.push(2);
   cout <<"Queue rear is "<<q.back()<<endl;
   q.push(3);
   cout <<"Queue rear is "<<q.back()<<endl;
   q.push(4);
   cout <<"Queue rear is "<<q.back()<<endl;


   cout <<"Queue should be 1234,front to rear"<<endl;

   if(q.empty())
       cout <<"The queue is empty"<<endl;
   else
       cout <<"The queue is not empty"<<endl;

   cout<<"The queue size is "<<q.size()<<endl;

   while(!q.empty())
   {
       cout <<"Queue front is"<<q.front()<<endl;
       q.pop();
       cout<<"Popped front element"<<endl;
   }

   try{q.pop();}
   catch(queueEmpty message)
   {
       cout<<"Last pop failed"<<endl;
       message.outputMessage();
   }


   arrayQueue<int> r(4);
   r.push(1);
   r.push(2);
   r.push(3);
   r.pop();
   r.pop();
   r.push(4);
   r.push(5);
   r.push(6);
   r.push(7);

   cout<<"Queue should be 34567,front to rear"<<endl;

   if(r.empty())
       cout<<"The queue is empty"<<endl;
   else
       cout<<"The queue is not empty"<<endl;

   cout<<"The queue size is "<<r.size()<<endl;

   while(!r.empty())
   {
       cout<<"Queue front is"<<r.front()<<endl;
       r.pop();
       cout<<"Popped front element"<<endl;
   }
    return 0;
}

/*
 * 队列抽象类定义
 * queue.h
*/
#ifndef QUEUE_H
#define QUEUE_H

using namespace std;

template<class T>
class queue
{
  public:
    virtual ~queue(){}//析构函数


    //判断队列是否为空
    virtual bool empty() const = 0;

    //队列中元素个数
    virtual int size() const = 0;

    //返回队首元素的引用
    virtual T& front() = 0;

    //返回队尾元素的引用
    virtual T& back() = 0;

    //出队
    virtual void pop() = 0;

    //入队
    virtual void push(const T& theElement) = 0;

};


#endif // QUEUE_H

/*
 * 用数组来存储队列元素
 * 我们这里的队列为循环队列
 * 之所以采用循环队列，是因为如果队列是直线的，队列进行多次增减元素操作之后，整个元素一直
 * 向前移动，队列后面会空出来很多空数组，浪费空间。
 * 为了节约存储空间，当然可以在每次元素操作后，对队列中的元素进行移位，但这样会增加时间复杂度。
 *
 * 如果将数组的首尾相连，变成循环数组，那么就不会存在这样的问题了。
 * 每次队列进行元素的增减，元素会在整个环中循环移动，除非某一刻，
 * 整个循环数组的空间已经被占满，这个时候才需要对数组进行扩充，否则，队列
 * 的元素增减操作可以一直不间断的进行，并且不会浪费空间，也不用像单链表一样，
 * 要对元素进行移动。
 * 这样队列的每次增减元素操作的时间复杂度为1，效率最高。
 * arrayQueue.h
*/
#ifndef ARRAYQUEUE_H
#define ARRAYQUEUE_H

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

using namespace std;

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

    //西沟函数
    ~arrayQueue(){delete [] queue;}

    //当队首等于队尾时，我们认为队空
    //这是人为设定的，否则难以判断什么情况下为队空
    bool empty() const
    {
        return theFront == theBack;
    }

    //计算队列中元素个数
    int size() const
    {
        //之所以这么算，画一个环形图就明白了
        //因为循环队列中，起初，theBack > theFront，则，队列中元素的个数就是
        //   theback - theFront
        //经过一系列的增减元素，可能变成theBack < theFront,这时队列中的元素个数应该为
        //      theBack - theFront + arrayLength
        //为了统一这两种计算方式，用一个表达式就可以概括这两种情况，如下
        // (theBack - theFront + arrayLength) % arrayLength
        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();
    }

    //元素入队，队尾元素入队
    void push(const T& theElement)
    {
        //循环队列判断队满的条件是：theBack+1 == theFront
        //当队满的时候，就要扩充队容量
        if((theBack+1)%arrayLength == theFront)
        {
            T* newQueue = new T[2*arrayLength];

            //将旧数组的元素复制到新数组中去
            int start = (theFront+1)%arrayLength;
            if(start < 2)
                copy(queue+start,queue+start+arrayLength-1,newQueue);
            else
            {
                copy(queue+start,queue+arrayLength,newQueue);
                copy(queue,queue+theBack+1,newQueue + arrayLength - start);
            }

            theFront = 2 * arrayLength - 1;
            theBack = arrayLength - 2;
            arrayLength *= 2;
            queue = newQueue;
        }

        theBack = (theBack + 1)%arrayLength;
        queue[theBack] = theElement;
    }
private:
    int theFront;
    int theBack;
    int arrayLength;
    T *queue;
};
#endif // ARRAYQUEUE_H

/*
 * 异常处理类
 * myExceptions.h
*/
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H
#include<string>

using namespace std;

//参数值异常
class illeaglParameterValue
{
public:
    illeaglParameterValue(string theMessage =
            "Illegal parameter value")
    {
        message = theMessage;
    }
    void outputMessage()
    {
        cout <<message<<endl;
    }
private:
    string message;
};


//队列空异常
class queueEmpty
{
  public:
    queueEmpty(string theMessage =
            "Invalid operation on empty queue")
    {
        message = theMessage;
    }
    void outputMessage()
    {
        cout << message <<endl;
    }
private:
    string message;
};


#endif // MYEXCEPTIONS_H