循环队列及其相关操作

循环队列简要提点

• 解决队列操作过程中不断出队和入队导致的队满的”假象”（即队尾rear==Maxsize，而队首却不是0）。
• 当队列”假满”时，引入循环，队尾和队首到达数组尾端，又会重新绕回开头。
• 可以把循环队列的存储形象地看成一个“圆环”。
• 循环队列的主要操作有：入队(Enqueue)、出队(Dequeue)、判断队是否空、满。

---

循环队列的数组实现

• 基本数据结构：队首front、队尾rear、当前队长度length以及存储元素的数组elemList

代码实现(C/C++)

#include<iostream>
using namespace std;

typedef int ElemType;
const int MAXSIZE = 6;
typedef struct {
    int front;      // 队首
    int rear;       // 队尾
    int length;     // 队长度
    ElemType elemList[MAXSIZE];
}CirDeque;

void initCDeque(CirDeque *De)       // 初始化队列
{
    De->front = 0;
    De->rear = -1;
    De->length = 0;
}

int isEmpty(CirDeque *De)       // 判断队列是否为空
{
    return De->length == 0;
}

int isFull(CirDeque *De)
{
    return De->length == MAXSIZE;
}

void Enqueue(CirDeque *De, ElemType x)      // 入队列
{
    if (isFull(De))
    {
        cout << "Have been Filled\n";
    }
    else
    {
        De->rear = (De->rear + 1) % MAXSIZE;        // 循环存储
        De->elemList[De->rear] = x;
        De->length++;
    }

}

ElemType Dequeue(CirDeque *De)      // 出队列
{
    if (isEmpty(De))
    {
        cout << "Empty!\n";
        //exit(1);
    }
    De->length--;
    ElemType x = De->elemList[De->front];
    De->front = (De->front + 1) % MAXSIZE;
    return x;
}

ElemType Front(CirDeque *De)        // 取队首元素
{
    return De->elemList[De->front];
}

ElemType Rear(CirDeque *De)     // 取队尾元素
{
    return De->elemList[De->rear];
}

void print(CirDeque *De)        // 打印队列的内容
{
    cout << "Now the Circular Deque contents: " << endl;    // 打印队内元素
    if (De->rear > De->front)           
    {
        for (int i = De->front;i <= De->rear;i++)
        {
            cout << De->elemList[i] << " ";
        }
    }
    else
    {
        for (int i = De->front;i <= De->rear+MAXSIZE;i++)
        {
            cout << De->elemList[i % MAXSIZE] << " ";
        }
    }
    cout << endl;
    cout << "The Front's index is "<< De->front <<" and its value is: " << Front(De) << endl;   // 打印队首
    cout << "The Rear's index is " << De->rear << " and its value is: " << Rear(De) << endl;    // 打印队尾
}

int main()
{
    const ElemType date[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    CirDeque* myCirDeque = new CirDeque;        // 初始化队列
    initCDeque(myCirDeque);
    if (isEmpty(myCirDeque))
        cout << "Empty CirDeque, now enqueue some values... " << endl;
    for (int i = 0;i < 9;i++)
    {
        Enqueue(myCirDeque, date[i]);
    }
    print(myCirDeque);

    cout << "Dequeue twice from the Deque...\n";
    Dequeue(myCirDeque);
    Dequeue(myCirDeque);
    print(myCirDeque);

    cout << "Enqueue two numbers to the Circular Deque: \n";
    ElemType number1, number2;
    cin >> number1>>number2;
    Enqueue(myCirDeque, number1);
    Enqueue(myCirDeque, number2);
    print(myCirDeque);

    delete myCirDeque;
    system("pause");
    return 0;

}

操作实现结果

Empty CirDeque, now enqueue some values...
Have been Filled
Have been Filled
Have been Filled                // 原始数组有9个，而最大队容量为6，故提示3次队满信息。
Now the Circular Deque contents:    // 打印循环队列内容
1 2 3 4 5 6
The Front's index is 0 and its value is: 1      // 队首下标为0，元素值为1
The Rear's index is 5 and its value is: 6       // 队尾下标为5，元素值为1
Dequeue twice from the Deque...                 // 出队两次
Now the Circular Deque contents:                // 此时，队包含
3 4 5 6
The Front's index is 2 and its value is: 3      // 出队两次，队首后移，下标+2，元素值为3
The Rear's index is 5 and its value is: 6       // 队尾不变，下标依然为5，元素值为6
Enqueue two numbers to the Circular Deque:      // 输入两个数，入队2次
13 17
Now the Circular Deque contents:                // 此时循环队列中元素为
3 4 5 6 13 17
The Front's index is 2 and its value is: 3      // 入队，队首不变，下标为2，元素值为3
The Rear's index is 1 and its value is: 17      // 循环队列，入队1次，rear=0，入队两次rear=1