C++实现环形队列（数组描述）

环形队列可以在数组长度不变的前提下有效地同时降低队列插入和删除的最坏时间复杂度。数组视为一个环时，每一个位置都会有其上一位置和下一位置，位置0与数组末端位置array_length相邻。同时定义队列头queue_front所在位置沿逆时针方向的下一个元素为队列的头元素，queue_back所在位置的元素为队列的尾元素。当且仅当queue_front = queue_back是，队列为空，考虑到队列为满是此条件仍会触发，因此这种队列不能插满，在向队列插入最后一个元素之前，需要判断这次操作是否会使得队列成为满队列。
本程序由三个文件组成，头文件定义了环形队列类，函数描述文件定义了成员函数，测试文件给出了示例运行。以下是头文件：

//
//  queuedefine.hpp
//  环形队列（数组描述）
//
//  Created by lq on 2019/9/13.
//  Copyright © 2019 Mr.liang. All rights reserved.
//

#ifndef queuedefine_hpp
#define queuedefine_hpp

class queuedefine
{
private:
    int *array;//数组
    int queue_front;//队列头序号
    int queue_back;//队列尾序号
    int length;//数组长度
public:

    queuedefine();//环形队列构造函数
    ~queuedefine();//环形队列析构函数
    
    bool empty_check();//检查队列是否为空
    bool full_check();//检查队列是否即将为满队列
    int get_size();//返回队列元素数量
    int & front();//返回队列头元素
    int & back();//返回队列尾元素
    void pop();//出队
    void push(const int & element);//入队element
    void show();//遍历队列
    void change_length(int new_length);//在需要时改变队列长度
};

#endif /* queuedefine_hpp */

下面是成员函数定义文件：

//
//  queuedefine.cpp
//  环形队列（数组描述）
//
//  Created by lq on 2019/9/13.
//  Copyright © 2019 Mr.liang. All rights reserved.
//

#include "queuedefine.hpp"
#include <iostream>
#include <string>
using namespace std;

queuedefine::queuedefine()
{
    length = 10;
    array = new int[length];
    queue_front = 0;
    queue_back = 0;
}

queuedefine::~queuedefine()
{
    cout<<"Bye"<<endl;
}

bool queuedefine::empty_check()
{
    if(queue_front == queue_back)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool queuedefine::full_check()
{
    if((queue_back+1)%length == (queue_front%length))
    {
        return true;
    }
    else
    {
        return false;
    }
}

int queuedefine::get_size()
{
    int size;
    int location_start = queue_front%length;
    int location_end = queue_back%length;
    if(location_end > location_start)
    {
        size = location_end - location_start;
    }
    else if(location_start == location_end)
    {
        size = 0;
    }
    else
    {
        size = length - (queue_front%length) + (queue_back%length);
    }
    return size;
}

int & queuedefine:: front()
{
    int location = (queue_front+1)%length;
    return array[location];
}

int & queuedefine:: back()
{
    int location = queue_back%length;
    return array[location];
}

void queuedefine::push(const int & element)
{
    int start = queue_front % length;
    //注意：不要写成int end = queue_back % length + 1
    int end = (queue_back+1) % length;
    if(start == end)
    {
        cout<<"full_check = 1"<<endl;
        change_length(2*length);
        length = 2*length;
        
    }
    queue_back = (queue_back+1)%length;
    array[queue_back] = element;
}

void queuedefine::change_length(int new_length)
{
    int *temp_array = new int [new_length];
    int start = (queue_front + 1)%length;
    if(start<2)
    {
        copy(array+start,array+start+length-1,temp_array);
    }
    else
    {
        copy(array+start,array+length,temp_array);
        copy(array,array+queue_back+1,temp_array+length-start);
    }
    queue_front = 2*length - 1;
    queue_back = length - 2;
    delete[] array;
    array = temp_array;
}

void queuedefine::pop()
{
    queue_front = (queue_front+1)%length;
}

void queuedefine::show()
{
    cout<<"length is "<<length<<endl;
    cout<<"size is "<<get_size()<<endl;
    cout<<"queue_front is "<<queue_front<<endl;
    cout<<"queue_back is "<<queue_back<<endl;
    for(int i = 0;i<get_size();i++)
    {
        int location = (queue_front+i+1)%length;
        cout<<"第"<<i+1<<"个元素在数组的位置为"<<location<<",其值为："<<endl;
        cout<<array[location]<<endl;
    }
}

下面是测试文件，首先输入一个过长（大于length），然后出队一次并输出队头元素，队尾元素以及遍历输出：

//
//  main.cpp
//  环形队列（数组描述）
//
//  Created by lq on 2019/9/13.
//  Copyright © 2019 Mr.liang. All rights reserved.
//

#include <iostream>
#include "queuedefine.hpp"
using namespace std;
int main(int argc, const char * argv[]) {
    // insert code here...
    queuedefine queue;
    for(int i = 0;i<12;i++)
    {
        queue.push(i);
    }
    queue.pop();
    //for(int i = 12;i < 22;i++)
    //{
       // queue.push(i);
    //}
    cout<<"queue_front is "<<queue.front()<<endl;
    cout<<"queue_back is "<<queue.back()<<endl;
    queue.show();
    return 0;
}

运行结果如下：

full_check = 1
queue_front is 1
queue_back is 11
length is 20
size is 11
queue_front is 0
queue_back is 11
第1个元素在数组的位置为1,其值为：
1
第2个元素在数组的位置为2,其值为：
2
第3个元素在数组的位置为3,其值为：
3
第4个元素在数组的位置为4,其值为：
4
第5个元素在数组的位置为5,其值为：
5
第6个元素在数组的位置为6,其值为：
6
第7个元素在数组的位置为7,其值为：
7
第8个元素在数组的位置为8,其值为：
8
第9个元素在数组的位置为9,其值为：
9
第10个元素在数组的位置为10,其值为：
10
第11个元素在数组的位置为11,其值为：
11
Bye
Program ended with exit code: 0

在刚刚的基础上，再入队10个元素：

//
//  main.cpp
//  环形队列（数组描述）
//
//  Created by lq on 2019/9/13.
//  Copyright © 2019 Mr.liang. All rights reserved.
//

#include <iostream>
#include "queuedefine.hpp"
using namespace std;
int main(int argc, const char * argv[]) {
    // insert code here...
    queuedefine queue;
    for(int i = 0;i<12;i++)
    {
        queue.push(i);
    }
    queue.pop();
    for(int i = 12;i<22;i++)
    {
       queue.push(i);
    }
    cout<<"queue_front is "<<queue.front()<<endl;
    cout<<"queue_back is "<<queue.back()<<endl;
    queue.show();
    return 0;
}

运行结果如下：

full_check = 1
full_check = 1
queue_front is 1
queue_back is 21
length is 40
size is 21
queue_front is 39
queue_back is 20
第1个元素在数组的位置为0,其值为：
1
第2个元素在数组的位置为1,其值为：
2
第3个元素在数组的位置为2,其值为：
3
第4个元素在数组的位置为3,其值为：
4
第5个元素在数组的位置为4,其值为：
5
第6个元素在数组的位置为5,其值为：
6
第7个元素在数组的位置为6,其值为：
7
第8个元素在数组的位置为7,其值为：
8
第9个元素在数组的位置为8,其值为：
9
第10个元素在数组的位置为9,其值为：
10
第11个元素在数组的位置为10,其值为：
11
第12个元素在数组的位置为11,其值为：
12
第13个元素在数组的位置为12,其值为：
13
第14个元素在数组的位置为13,其值为：
14
第15个元素在数组的位置为14,其值为：
15
第16个元素在数组的位置为15,其值为：
16
第17个元素在数组的位置为16,其值为：
17
第18个元素在数组的位置为17,其值为：
18
第19个元素在数组的位置为18,其值为：
19
第20个元素在数组的位置为19,其值为：
20
第21个元素在数组的位置为20,其值为：
21
Bye
Program ended with exit code: 0

全文完。

如果您想了解更多C++/Java/机器学习相关的知识，欢迎扫描下方的二维码，关注“梁公子的备忘录”，每天一篇相关的技术分享，期待与您一起学习，共同进步！