数据结构——循环队列（顺序队列）模板类实现-蒲公英云

数据结构笔记3.3
顺序队列是用顺序表实现的（即依托于数组），这里实现的是循环队列，其实也可以不用循环，但是那样的话，空间的利用效率就太低了，这就是”假溢出”问题，因为在数组的前端可能还有空闲的位置（因为队列中的数据是在动态变化的，可能出队也可能入对）。
为了能够充分利空间，所以用循环队列，即在逻辑上把数组的队结构看成一个环。具体实现：实现的方式还是十分巧妙地，运用两个指针和钟运算(就是取模或是取余运算)。
队头指针进1：front = (front + 1) % maxSize;
队尾指针进1 : rear = (rear + 1) % maxSize;
上面两个式子就是钟运算在队列数据操作时候的实现原理。
另外，在判断队列NULL与队列FULL的时候会遇到混淆的问题，NULL的时候，在即rear == front ，但是由于是循环表，当表FULL的时候，两者也是相等的，一种区分方式就是当rear检测到其下一个就是front的时候作为队列满的依据，这样就相当于队列满的时候也会有一个节点是空闲的。
好了，在编写这个类的过程中，需要强调的就这几个地方，下面贴出代码：
虚基类代码（此代码段放入queue.h当中，并在模板类代码中包含）

template<class T>
class Queue {
public:
    Queue(){}                               //构造函数
    ~Queue(){}                             //析构函数
    virtual bool EnQueue(const T & x) = 0;  //新元素x进入队列
    virtual bool DelQueue(T & x) = 0;       //队头元素出队列
    virtual bool getFront(T & x) = 0;       //读取队头元素的值
    virtual bool IsEmpty()const = 0;        //判断队列是否为NULL
    virtual bool IsFull() const = 0;        //判断队列是否已满
    virtual int getSize() const = 0;            //求队列元素的个数
};
模板class代码：
#include <iostream>
#include <cassert>
#include <cmath>
#include "queue.h"
using namespace std;
//顺序队列模板类定义(循环队列)
template<class T>
class SeqQueue : public Queue<T> {
public:
    SeqQueue(int sz = 10);              //构造函数
    ~SeqQueue();                       //析构函数
    //若队列不满则将x进入队列，否则溢出处理
    bool EnQueue(const T & x);
    //若队列不空则删除队头元素x，并返回true，否则返回false
    bool DelQueue(T & x);
    //若队列不空则函数返回队头元素并返回true，否则返回false
    bool getFront(T & x);
    //置空操作，队头指针与队尾指针置0
    void makeEmpty();
    //判断队列是否为空，是则返回true否则返回false
    bool IsEmpty() const;
    //判断队列是否已满，是返回true否则返回false
    bool IsFull() const;
    //求队列元素的个数
    int getSize() const;
    //输出队列元素,运算符重载函数调用
    void output(ostream & out);
protected:
    int rear, front;                    //队尾与队头指针
    T *elements;                        //存放队列元素的数组
    int maxSize;                        //队列最大可容纳的元素个数
};
//函数定义
template<class T>
SeqQueue<T>::SeqQueue(int sz) {
    //建立一个最大就有maxSzie个元素的空队列
    maxSize = sz;
    elements = new T[sz];               //开辟内存
    assert(elements != NULL);           //内存分配不成功的中断处理
    rear = front = 0;                   //初始化队头与队尾指
}
template<class T>
SeqQueue<T>::~SeqQueue() {
    //析构函数，释放程序中相应的资源
    delete[] elements;
}
template<class T>
bool SeqQueue<T>::EnQueue(const T & x) {
    //若队列不满则将x进入队列，否则溢出处理
    if (IsFull()) {
        //如果队列已经满，则返回false
        return false;
    }
    elements[rear] = x;
    rear = (rear + 1) % maxSize;    //通过钟运算实现元素的循环填充
    return true;
}
template<class T>
bool SeqQueue<T>::DelQueue(T & x) {
    //若队列不空则删除队头元素x，并返回true，否则返回false
    if (IsEmpty()) {
        return false;
    }
    x = elements[front];
    front = (front + 1) % maxSize;
    return true;
}
template<class T>
bool SeqQueue<T>::getFront(T & x)  {
    //若队列不空则函数返回队头元素并返回true，否则返回false
    if (IsEmpty()) {
        return false;
    }
    x = elements[front];
    return true;
}
template<class T>
bool SeqQueue<T>::IsEmpty() const {
    if (rear == front) {
        return true;
    }
    else {
        return false;
    }
}
template<class T>
bool SeqQueue<T>::IsFull() const {
    if (fmod((rear + 1), maxSize) == front) {
        //如果rear的下一个节点与front相同则定义为队列已满
        //从而区分队列为NULL，即rear==front的情况
        return true;
        //注意这个时候队列中会有一个NULL的节点
    }
    else {
        return false;
    }
}
template<class T>
void SeqQueue<T>::makeEmpty() {
    //置NULL操作
    rear = front = 0;
}
template<class T>
int SeqQueue<T>::getSize() const {
    //求队列元素的个数
    return (rear - front + maxSize) % maxSize;
}
template<class T>
void SeqQueue<T>::output(ostream & out) {
    for (int i = front; i != rear; i = (i + 1) % maxSize) {
        out << elements[i] << ' ';
    }
    cout << endl;
}
template<class T>
ostream & operator << (ostream & out, SeqQueue<T> & SQ) {
    //重载插入运算符
    SQ.output(out);
    return out;
}

Main测试代码：

int main()
{
    SeqQueue<int> squeue;               //定义循环队列对象
    squeue.EnQueue(1);                  //进队与出队测试
    squeue.EnQueue(2);
    squeue.EnQueue(3);
    squeue.EnQueue(4);
    squeue.EnQueue(5);
    cout << squeue;
    int outQueVal_1, outQueVal_2;
    squeue.DelQueue(outQueVal_1);
    squeue.DelQueue(outQueVal_2);
    cout << squeue;
    int quFrontVal = 0;
    squeue.getFront(quFrontVal);        //提取队头数据测试
    cout << quFrontVal << endl;
    squeue.makeEmpty();                 //设置NULL与测试NULL测试
    if (squeue.IsEmpty()) {
        cout << "队列为NULL" << endl;
    }
    else {
        cout << "队列非空" << endl;
    }
    squeue.EnQueue(2);                  //取队列大小测试
    squeue.EnQueue(3);
    squeue.EnQueue(4);
    cout << squeue.getSize() << endl;
    system("pause");
    return 0;
}