队列初体验

淡淡的烟草味﹌ 2022-06-17 07:28 275阅读 0赞

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。 进行插入操作的一端称为队尾，通常称为入队列；进行删除操作的一端称为队头，通常称为出队列。 队列具有先进先出的特性(FIFO)。  
队列又分为顺序队列和链式队列  
所谓顺序队列也就是分配个这个队列的存储空间是连续的

链式队列相当于我们的单链表  
![这里写图片描述][SouthEast]  
对链式队列的操作相当于对我们单链表的操作，不过在插入的时候我们需要移动尾指针，在删除的时候我们需要移动头指针。  
顺序队列：  
![这里写图片描述][SouthEast 1]

但是这种方式的实现相当于我们顺序表的头删头删操作每次在头部插入一个元素或者在头部删除一个元素，我们都需要对后面的元素进行整体的搬移，效率极其低。  
因此在我们我们STL容器中根被就没有头插和头删操作。而如果我们在队列中使用这种方式将队头后的元素向前搬移那么效率就非常低

![这里写图片描述][SouthEast 2]  
![这里写图片描述][SouthEast 3]

那么这样就浪费了我们的存储空间比如0和1号位置明明有空间，但因为假溢出我们不能再继续进行插入操作  
顺序队列因多次入队列和出队列操作后出现的尚有存储空间但不能再进行入队列操作的溢出称作为假 溢出。  
顺序队列最大存储空间已经存满而又要求进行入队列操作所引起的溢出称为真溢出。  
为了解决假溢出的问题我们引入了循环队列  
如上述例子我们为队列分配的最大空间是6，当队列处于上图假溢出的时候我们无法再继续进行插入，否则会越界导致程序崩溃，而我们又不适合像顺序栈那样直接去扩充容量，因为我们实际的存储空间并没有被用完。因此巧妙地方法就是我们可以将这个顺序队列想象成是一个环状的空间。如图所示我们称之为环形队列

![这里写图片描述][SouthEast 4]

刚开始我们将队头和队尾同时指向这个环形队列的队头。  
但是此时对环形队列的判空和判满的操作就不再简单了  
判断这个环形队列我们不能采用队头==队尾来判断  
为什么？  
看下图：

![这里写图片描述][SouthEast 5]

那么现在怎么去判断队列是空的还是满的？

因此我们必须采用其他的方式来判断队列是空还是满  
方式1：  
少用一个存储单元 如果少用一个存储空间，则也队尾指针加1等于对头指针为队列满的判断条件： (rear+1)%MaxSize==front 队列空的条件仍旧为rear == front

![这里写图片描述][SouthEast 6]

方式2：  
设置一个标记为 设置标记为flag，初始时置flag = 0；每当入队列操作成功，就置flag=1；每当出队列成功就置 flag=0.此时判断队列空 的条件为：rear == front && flag == 0； 判断队列满的条件为rear == front&& flag == 1  
![这里写图片描述][SouthEast 7]  
因此采用这种方式也可以判断队列空或者满的情况

方式3：  
设置一个计数器 设置计数器count，初始时置count=0，每当入队列操作成功，就是count加1，每当出队列成 功，就使count减1。此时队列空的判断条件为：count==0；队列满的判断条件为count>0 && rear == front 或者count == MaxSize  
这种方式比较加纳但只要我们插入元素的个数==最大存储空间就可以直接判断当前队列已满‘  
如果插入元素的个数==0就可以直接判断当前队列是空的

循环队列的具体实现：

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    template<class T>
    class Queue
    {
    public:
        friend std::ostream& operator<< <T>(std::ostream& _cout, const Queue<T>& v);
        Queue(size_t Capacity = 4)
        :_Capacity(Capacity)
        , _Front(0)
        , _Rear(0)
        , _pData(NULL)
        , _Count(0)
        {
            _Capacity += 1;
            _pData = new T[_Capacity];
        }
        ~Queue()
        {
            if (_pData != NULL)
            {
                delete[]_pData;
            }
        }
        void Push(const T &data);
        void Pop();
        int  Size();
        bool Empty();
        int  Front();
        int  Back();
        void Print();
        bool IsFull();
    private:
        T* _pData;
        size_t _Capacity;
        size_t _Front;
        size_t _Rear;
        size_t _Count;
    
    };
    template<class T>
    void Queue<T>::Push(const T &data)
    {
        if (_Count!=_Capacity)
        {
            _pData[_Rear] = data;
            _Rear = (_Rear + 1) % _Capacity;
            _Count++;
        }
    }
    template<class T>
    void Queue<T>::Pop()
    {
        if (!Empty())
        {
            _Front = (_Front + 1) % _Capacity;
            _Count--;
        }
    }
    template<class T>
    int Queue<T>::Size()
    {
        return _Count;
    }
    template<class T>
    bool Queue<T>::IsFull()
    {
        return _Count == _Capacity;
    }
    template<class T>
    bool Queue<T>::Empty()
    {
        return _Count == 0;
    }
    template<class T>
    int  Queue<T>::Front()
    {
        return _pData[Front];
    }
    template<class T>
    int  Queue<T>::Back()
    {
        return _pData[Back];
    }
    template<class T>
    void Queue<T>::Print()
    {
        for (int i = _Front; i < _Count + _Front; i++)//要注意始终是从队头开始打印元素
        {
            cout << _pData[i%_Capacity] << " ";//必须磨上它的容量
        }
        cout << endl;
    }
    template<class T>
    ostream& operator<<(ostream& _cout, const Queue<T>& v)
    {
        for (int i =v._Front; i < v._Count+v._Front; i++)
        {
            _cout << v._pData[i%(v._Capacity)]<<" ";
        }
        return _cout;
    }
    void FunTest()
    {
        Queue<int>s;
        s.Push(1);
        s.Push(2);
        s.Push(3);
        s.Push(4);
        s.Push(5);
        s.Print();
        cout << s.IsFull() << endl;
        s.Pop();
        cout << s.IsFull() << endl;
        s.Push(6);
        s.Pop();
        s.Pop();
        cout << s;
    }
    int main()
    {
        FunTest();
        system("pause");
        return 0;
    }

在这里一定要注意输出操作符重载的时候由于我使用的模板，因此在声明的时候一定要加上模板参数列表中的T，否则会出现链接型错误！！！  
friend std::ostream& operator<< (std::ostream& \_cout, const Queue& v);

[SouthEast]: /images/20220617/6de2aa46e92c4140bfac7989cc847d13.png
[SouthEast 1]: /images/20220617/13fad4f3acaa4d6599a80d34fdfc7a34.png
[SouthEast 2]: /images/20220617/539ae2ed0de24890a0b3cd46b183f0be.png
[SouthEast 3]: /images/20220617/b7b3cc94ee3c4aa8bb81cc606cde6a85.png
[SouthEast 4]: /images/20220617/9c48751a558841de8b90a4c080a59302.png
[SouthEast 5]: /images/20220617/27daba770af6416a8eb4868fc1e0ef31.png
[SouthEast 6]: /images/20220617/301dbb989064476ca452ed453d54a0f9.png
[SouthEast 7]: /images/20220617/4eba452b9adb40b4a546a575956b2d6f.png