循环队列

简介：

用一组地址连续的存储单元依次存放从队列头到队列尾的元素

在实现过程中，使得这一组连续的存储单元在逻辑上成为一个环

此处与顺序队列不同，不能通过存储再分配来扩大数组空间，因为即使队列尾指向
数组最后一个单元，队列可用空间也不一定为0，这是由于逻辑上的环状结构，如果
此时队列头指向的并非数组第一个单元，那么仍有剩余空间给队列新元素使用。

此处有一个问题需要注意：

如何判断队列是否为空？
当front=rear时，队列可能为空，也可能是因为整个队列占满了整个可用的存储空间

解决此问题的方法有：
1）设置一个标志位用于标识是否为空
2）少用一个元素空间，约定以队列头指针在队列尾指针的下一位为满
下面实现采用增设一个标志位的方法

用于测试的文件，以及测试结果以及其他简单数据结构的实现可以去作者GitHub上查看

 （下面代码只是最初实现，后续如果有修改，由于太麻烦，不会再更改下文，仅仅更新Github上的代码文件）

定义与实现：

#define SqQueueDataType int
#define InitSqQueueData 12345
#define SqQueueAvailableSpace 10

class SqQueue {
public:
    SqQueue();
    ~SqQueue();

    // 队列的初始化
    void SqQueueInit();

    // 销毁队列
    void SqQueueDestroy();

    // 将队列清空
    void SqQueueClear();

    // 判断是否为空队列
    bool SqQueueEmpty();

    // 获取队列长度，即队列中元素个数
    int SqQueueLength();

    // 获取队列头结点保存的数据值
    bool SqQueueGetHead(SqQueueDataType& value);

    // 入队，插入新的队列结点
    bool SqQueueEn(SqQueueDataType value);

    // 出队，删除队尾结点
    bool SqQueueDe();
    bool SqQueueDe(SqQueueDataType& value);    // 出队并返回其值

    // 遍历队列，从队头到队尾
    void SqQueueTraverse();

private:
    // 标识对头 队尾，由于采用一组
    int front;    // front指向的下一个元素位对头元素
    int rear;     // rear指向队尾元素
    bool isEmpty;
    SqQueueDataType* base;    // 指向所分配的连续存储空间
};

SqQueue::SqQueue()
{
    SqQueueInit();
}

SqQueue::~SqQueue()
{
    SqQueueDestroy();
}

void SqQueue::SqQueueInit()
{
    base = new(std::nothrow) SqQueueDataType[SqQueueAvailableSpace];
    
    if (!base)
        std::exit(1);

    front = 0;
    rear = 0;
    isEmpty = true;
}

void SqQueue::SqQueueDestroy()
{
    delete []base;
}

void SqQueue::SqQueueClear()
{
    // 置为空队列
    front = 1;
    rear = 1;
}
bool SqQueue::SqQueueEmpty()
{
    return isEmpty;
}

int SqQueue::SqQueueLength()
{
    return (rear - front + SqQueueAvailableSpace) % SqQueueAvailableSpace;
}

bool SqQueue::SqQueueGetHead(SqQueueDataType& value)
{
    if (isEmpty)
        return false;
    else {
        value = base[front + 1];
        return true;
    }
}

bool SqQueue::SqQueueEn(SqQueueDataType value)
{
    if (!isEmpty && rear == front)
        return false;    // 队列可用空间已满

    rear = (rear + 1) % SqQueueAvailableSpace;
    base[rear] = value;
    isEmpty = false;
}

bool SqQueue::SqQueueDe()
{
    if (isEmpty)
        return false;

    front = (front + 1) % SqQueueAvailableSpace;

    if (front == rear)
        isEmpty = true;  // 队列仅有一个元素出队后变为空队列

    return true;
}

bool SqQueue::SqQueueDe(SqQueueDataType& value)
{
    if (isEmpty)
        return false;

    front = (front + 1) % SqQueueAvailableSpace;
    value = base[front];

    if (front == rear)
        isEmpty = true;  // 队列仅有一个元素出队后变为空队列

    return true;
}

void SqQueue::SqQueueTraverse()
{
    if (isEmpty)
        return;

    int f = (front + 1) % SqQueueAvailableSpace;

    while (f != rear) {
        std::cout << base[f] << std::endl;
        f = (f + 1) % SqQueueAvailableSpace;
    }
    std::cout << base[f] << std::endl;
}