数据结构——循环队列（顺序队列）模板类实现

朴灿烈づ我的快乐病毒、 2022-06-07 07:17 368阅读 0赞

**数据结构笔记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;
    }

运行结果：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220607/b38fbd16c3e145e3a17eb56b42b9d012.png