循环队列

数据结构作业 之 循环队列的实现

主要思路：

• 设置标志法： 设置一个bool型的judge标记，初始化为false；
• 如果入队列成功，judge为true，如果出队列成功，judge设为false
• 判空条件是front%Maxsize == rear%Maxsize && judge == 0
• 判满条件是front%Maxsize == rear%Maxsize && judge == 1

代码实现：

//循环队列
#include <iostream>
using namespace std;
const int defaultMaxSize = 10;

template <class T>
class SeqQueue
{
private:
    int Front;
    int Rear;
    int maxSize;
    T * element;
    bool tag;
public:
    SeqQueue(int sz = defaultMaxSize):Front(0),Rear(0),maxSize(sz)
    {
        element = new T[maxSize];
        tag = false;
    }
    ~SeqQueue()
    {
        delete[] element;
        Front = 0;
        Rear = 0;
    }
    bool EnQueue(const T&x)//新的元素x入队列
    {
        //如果队列已经满了
        if(Front%maxSize == Rear%maxSize && tag == true)
        {
            return false;
        }
        element[Rear] = x;
        Rear = (Rear+1)%maxSize;
        tag = true;
        return true;
    }
    bool DeQueue(T&x)//队头元素出队列
    {
        //如果队列是空的
        if(Front%maxSize == Rear%maxSize && tag == false)
        {
            return false;
        }
        x = element[Front];
        Front = (Front+1)%maxSize;
        tag = false;
        return true;
    }
    //重载进行输出
    friend ostream&operator << (ostream&os,SeqQueue<T>&Q)
    {
        os << "front = " << Q.Front << " Rear = " << Q.Rear << endl;
        bool judge = Q.tag;
        for(int i = Q.Front; i != Q.Rear || judge ; i = (i+1)%Q.maxSize)
        {
            os << i << ":" << Q.element[i] << " ";
            if(i == Q.Front)
            {
                judge = false;
            }
        }
        return os;
    }
};
int main()
{
    int sz;
    cin >> sz;
    SeqQueue<int> sq(sz);
    for(int i = 0 ; i < sz; i++)
        sq.EnQueue(i+1);
    cout << sq << endl;
    for(int i = 0 ; i < sz/2; i++)
    {
        int x;
        sq.DeQueue(x);
        cout << x << " ";
    }
    cout << endl;

    cout << sq << endl;
    for(int i = 0 ; i < sz/2; i++)
    {
        sq.EnQueue(i+sz/2);
    }
    cout << sq << endl;
    return 0;
}

感觉输出函数重载那块不大好写，花了一点时间