数据结构笔记--循环队列分析

循环队列是队列的一种顺序表示和实现方法。我们用一个一维数组来存储队列元素值，为了解决“假溢出”现象并使得空间得到充分利用，一个较巧妙的方法是将顺序数组看成一个环状数组（注意：环状空间只是逻辑空间，真实的在内存中的还是连续空间，这就解释了为什么后面的操作要取模）。然而，当我们将数组设计成这样后，队列为满与队列为空就无法正确表示。解决办法有两个：一种是少用一个元素空间。则队满的状况就是(rear+1)%MAXSIZE == front,队空的条件不变，仍然是rear == front。另一种方法是增设一个标志量flag，初始化队列设flag为false，在入队中判断rear == front为真，设置flag为true，在出队中判断rear == front为真，设置flag为false。这是因为只有入队才有可能队满，出队才可能队空。

少用一个元素空间的实现方法：

typedef char DataType;

#define MaxSize 10

typedef struct queue
{
    DataType m_array[MaxSize];
    int m_front;
    int m_rear;
}Queue;

//初始化循环队列
void Init(Queue* q)
{
    q->m_front = q->m_rear = 0;
}

//判断队列是否为空
bool Isempty(Queue* q)
{
    if (q->m_front == q->m_rear)
    {
        return true;
    }
    return false;
}

//判断队列是否为满
bool Isfull(Queue* q)
{
    if ((q->m_rear + 1) % MaxSize == q->m_front)
    {
        return true;
    }
    return false;
}

//入队列
int Enter(Queue* q, DataType data)
{
    if (Isfull(q))
    {
        cout << "队列已满" << endl;
        return 0;
    }
    q->m_array[q->m_rear] = data;
    q->m_rear = (q->m_rear + 1) % MaxSize;
    return 1;
}

//出队列
int Delete(Queue* q, DataType* data)
{
    if (Isempty(q))
    {
        cout << "队列为空" << endl;
        return 0;
    }
    *data = q->m_array[q->m_front];
    cout << "出队元素为 " << *data << endl;
    q->m_front = (q->m_front + 1) % MaxSize;
    return 1;
}

//求队列头
DataType GetFront(Queue* q)
{
    if (Isempty(q))
    {
        cout << "队列为空" << endl;
        return 0;
    }
    return q->m_array[q->m_front];
}

上面的代码实现的时候使用了静态数组，也就是说程序在运行时遇到比数组元素个数多的情况就会发生错误，解决办法自然就是使用malloc动态开辟空间咯。当然，如果你使用C++编写，数组也可以使用vector，这时为了提高重用性，你的结构体就可以定义成队列类，元素类型就可以写成模板。

另一种增设一个标志量flag的方法，同样可以编程实现，只是flag的定义不应该定义在结构体内，因为flag是所有节点共同拥有一份，也就是一个队列只有一份，所以flag应该定义为静态，或者全局。同时，代码插入数据等操作也不用再有求模运算。