[数据结构] 一种循环队列的C++实现方法

一种循环队列的C++实现方法，实现了创建、销毁、判空、判满、入队、出队、遍历的操作。

头文件：

#ifndef __QUEUE_H
#define __QUEUE_H

    
//环形队列的实现
class MyQueue
{
public:
    MyQueue(int queueCapacity=4); //InitQueue(&Q)创建队列
    virtual ~MyQueue();         //DestroyQueue(&Q)销毁队列
    void ClearQueue();          //ClearQueue(&Q)清空队列
    bool QueueEmpty() const;    //QueueEmpty(Q)判空队列
    bool QueueFull() const;     //QueueFull(Q)判满队列
    int QueueLenth() const;     //QueueLength(Q)队列长度
    bool EnQueue(int element);  //EnQueue(&Q ,element)新队列入队
    bool DeQueue(int &element); //DeQueue(&Q ,&element)首元素出队
    void QueueTraverse();       //QueueTraverse(Q,visit())遍历队列
    void Test_MyQueue();//测试用列
private:
    int *m_pQueue;      //队列数组指针
    int m_iQueueLen;    //队列元素个数
    int m_iQueueCapacity;   //队列数组容量

    int m_iHead; //头指针
    int m_iTail; //尾指针
};

#endif

源文件：

#include <iostream>
#include "queue.h"
using namespace std;

/*************************************************************
 * 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合
 * 队列:    先入先出，first in first out
 * 队列包含队列头、队列尾
 * 
 * 普通队列：【售票员】:【队列头】【】【】【】【】【】【】【队列尾】
 * 环形队列：【队列头】->[]->[]->[]->[]->[]->[]->[]->【队列尾】->[队列头]
 * ***********************************************************/

int main()
{
    std::cout<<"[ * queue test begin * ]"<<std::endl;

    MyQueue *pMyQueue = new MyQueue(4);

    pMyQueue->Test_MyQueue();//开始测试

    delete pMyQueue;
    pMyQueue = NULL;
    
    std::cout<<"[ * queue test end   * ]"<<std::endl;
    return 0;
}

MyQueue::MyQueue(int queueCapacity)
{
    std::cout<<"InitQueue(&Q):Length = "<<queueCapacity<<std::endl;
    m_iQueueCapacity = queueCapacity;
    m_pQueue = new int[m_iQueueCapacity];
    ClearQueue();
}

MyQueue::~MyQueue()
{
    std::cout<<"DestroyQueue"<<std::endl;
    delete []m_pQueue;
    m_pQueue = NULL;
}

void MyQueue::Test_MyQueue()
{
    std::cout<<" Test_MyQueue "<<std::endl;
    int test_lock = 1;//循环锁
    int your_operation = 0;//操作命令记录
    int elem = 0;
    int test_state = 0;//测试用状态机 状态
    while(test_lock)
    {
        switch(test_state) 
        {
            case 0: //创建完队列后进入菜单状态
                    std::cout<< "***********************************"<<std::endl;
                    std::cout<< "* please input your operation : "<<std::endl;
                    std::cout<< "* 1.QueueTraverse    2.EnQueue"<<std::endl;
                    std::cout<< "* 3.DeQueue          4.ClearQueue"<<std::endl;
                    std::cout<< "* 5.QueueEmpty       6.QueueFull"<<std::endl;
                    std::cout<< "* 7.QueueLenth       8.Exit"<<std::endl;
                    std::cout<< "***********************************"<<std::endl;
                    std::cin>>your_operation;
                    if(your_operation <=0 || your_operation > 8)
                    {
                        std::cout<<"Error operation , try again"<<std::endl;
                    }else
                    {
                        test_state = your_operation;
                    }
                    break;
            case 1: //遍历队列
                    QueueTraverse();test_state = 0;break;
            case 2: //新元素入队列
                    std::cout<<"please input a elem : ";
                    std::cin>>elem; 
                    EnQueue(elem);
                    test_state = 0;break;
            case 3: DeQueue(elem);
                    std::cout<<elem<<" out "<<std::endl; 
                    test_state = 0;break;
            case 4: //清空队列
                    ClearQueue();
                    test_state = 0;break;
            case 5: //判空队列
                    QueueEmpty();test_state = 0; break;
            case 6: //判满队列 
                    QueueFull();test_state = 0;break;
            case 7: //获取队列长度 
                    std::cout<<" Queulength = "<<QueueLenth()<<std::endl;
                    test_state = 0;
                    break;
            case 8: //退出循环
                    test_lock = 0;
                    break;
            default:
                    test_state = 0;
                    break;

        }
    }
}

void MyQueue::ClearQueue()
{
    std::cout<<"ClearQueue"<<std::endl;
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLen = 0;
}

bool MyQueue::QueueEmpty() const
{
    if(m_iQueueLen == 0)
    {
        std::cout<<" QueueEmpty : true "<<std::endl;
        return true;
    }
    else 
    {
        std::cout<<" QueueEmpty : false "<<std::endl;
        return false;
    }
}

bool MyQueue::QueueFull() const
{
    if(m_iQueueLen == m_iQueueCapacity)
    {
        std::cout<<" QueueFull : true "<<std::endl;
        return true;  
    }
    std::cout<<" QueueFull : false "<<std::endl;
    return false;
}

int MyQueue::QueueLenth() const
{
    return m_iQueueLen;
}

bool MyQueue::EnQueue(int element)
{
    if(QueueFull())
    {
        std::cout << "no space for EnQueue"<<std::endl;
        return false;
    }
    m_pQueue[m_iTail] = element;

    m_iTail++;
    m_iTail = m_iTail % m_iQueueCapacity;

    m_iQueueLen++;
    std::cout<<"m_iHead = "<<m_iHead<<" ,m_iTail = "<<m_iTail<<" ,m_iQueueLen = "<<m_iQueueLen<<std::endl;
    std::cout<<"EnQueue success"<<std::endl;
    return true;
}

bool MyQueue::DeQueue(int &element)
{
    if(QueueEmpty())
    {
        std::cout<<"no element for DeQueue"<<std::endl; 
        return false;
    }
    element = m_pQueue[m_iHead];

    m_iHead++;
    m_iHead = m_iHead % m_iQueueCapacity;

    m_iQueueLen--;
    std::cout<<"m_iHead = "<<m_iHead<<" ,m_iTail = "<<m_iTail<<" ,m_iQueueLen = "<<m_iQueueLen<<std::endl;
    std::cout<<"DeQueue success"<<std::endl;
    return true;   
}

void MyQueue::QueueTraverse()
{
    if(QueueEmpty())
    {
        //std::cout<<"QueueEmpty "<<std::endl;
    }else
    {
        for(int i = m_iHead;i<m_iQueueLen+m_iHead;i++)
        {
            std::cout<<"Q["<<i-m_iHead<<"]="<<" "<<m_pQueue[i % m_iQueueCapacity]<<" ,";
        }
        std::cout<<std::endl;
    }
}

代码编辑器：vscode

编译环境：windows (已安装C/C++编译器)

编译命令：g++ .\queue.cpp -o   [name_you_want].exe

(直接使用g++ .\queue.cpp 将默认得到a.exe)

如下所示：

运行截图如下：

注：此部分代码只是通过一个简单的Test_MyQueue()状态机来验证循环队列的实现正确与否，不必过于纠结状态机的严谨性。