队列 Queue 的循环数组实现

using namespace std;

const int MAXSIZE = 100000; 

/* 用循环数组实现的队列 */ 
template <class T> 
class Queue
{
    private:
        int max_size; // 队列最大长度
        int front;    // 当前队头的数组下标 
        int rear;     // 当前队尾的数组下标 
        T * array;    // 存储
    
    public:
        Queue()  // 默认构造函数 
        {
            max_size = MAXSIZE;
            front = rear = 0;
            array = new T[max_size+1];
        }
        
        Queue(int _max_size)    // 指定最大队列容量的构造函数 
        {
            max_size = _max_size < MAXSIZE ? _max_size : MAXSIZE;
            front = rear = 0;
            array = new T[max_size+1];
        }
        
        ~Queue() { delete [] array; }    // 析构函数 
        
        bool full()    // 判断当前队列是否满 
        {
            return (rear + 1) % (max_size + 1) == front;
        }
        
        bool empty()   // 判断当前队列是否为空 
        {
            return front == rear;
        }
        
        int push(T & e)    // 将元素e入队，若成功则返回当前队尾位置，否则返回-1 
        {
            if ( this->full() )
                return -1;
            rear = (rear + 1) % (max_size + 1);
            array[rear] = e;
            return rear;
        } 
        
        T & query(int pos)  // 返回队列中位置为pos的元素，pos>=0, pos=0为队头。
        {
            pos = (front + pos + 1) % (max_size + 1);
            return array[pos];
        } 
        
        T pop()    // 得到当前队尾元素，如果队列为空，则返回的元素无意义 
        {
            if ( this->empty() )
                return array[front]; 
            front = (front + 1) % (max_size + 1);
            return array[front];
        }
};