c++ - 实现环形队列

简介

队列的核心思想是FIFO(First In First Out)，即先入先出。

入队（新增元素）必须从队尾加入，出队（删除元素）必须从队首出去。

实现

1、需要实现的方法

#pragma once
#include<iostream>
using namespace std;
#ifndef MYQUEUE_H
#define MYQUEUE_H
//环形队列的实现
class MyQueue
{
public:
    MyQueue(int queueCapacity);//创建队列
    virtual ~MyQueue();//销毁队列
    void ClearQueue();//清空队列
    bool QueueEmpty() const;//判空队列
    bool QueueFull() const;//判满队列
    int QueueLength() const;//队列长度
    bool EnQueue(int element);//新元素入队
    bool DeQueue(int &element);//首元素出队
    void QueueTraverse();//遍历队列
private:
    int *m_pQueue;//队列数组指针
    int m_iQueueLen;//队列元素个数
    int m_iQueueCapacity;//队列数组容量
    int m_iHead;
    int m_iTail;
};

2、构造函数

队列容量作为参数传入；

声明指向数组的指针，赋予容量；

清空队列的方法如“3.清空队列的实现”

MyQueue::MyQueue(int queueCapacity)
{
    m_iQueueCapacity = queueCapacity;
    m_pQueue = new int[m_iQueueCapacity];
    ClearQueue();
}

3、析构函数

 删除指针，并置空。因为是指向数组的指针，使用delete[]

MyQueue::~MyQueue()
{
    delete[] m_pQueue;
    m_pQueue = NULL;
}

4、清空队列

将队首置为0，队尾置0，队列长度置0

void MyQueue::ClearQueue()
{
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLen = 0;
}

5、判断空与满

判空：长度等于0返回正确的结果，否则错误
判满：长度等于容量返回正确的结果，否则错误

bool MyQueue::QueueEmpty() const
{
    return m_iQueueLen == 0 ?  true : false;
}

bool MyQueue::QueueFull() const
{
    return m_iQueueLen == m_iQueueCapacity ? true : false;
}

6、长度

bool MyQueue::QueueEmpty() const
{
    return m_iQueueLen == 0 ?  true : false;
}

7、入队

如果队列已满，不允许入队
如果队列未满，传入需要加入的参数
将数组[队尾]置为传入的元素
队尾++
队列长度++
队尾对容量进行取余，防止队尾溢出，一旦队尾大于等于4，就会回归到0-4之间的数，从而达到环形队列的目的

bool MyQueue::EnQueue(int element)
{
    if (QueueFull())
    {
        return false;
    }
    else {
        m_pQueue[m_iTail] = element;
        m_iTail++;
        m_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLen++;
        return true;
    }
}

8、出队

如果队列为空，不允许出队
如果队列不为空，允许出队
把即将删除的数组[队首]赋值给引用，队首++，出队的元素下一个成为新的队首元素
队首对容量进行取余操作，防止溢出队列容量
队列长度--
PS:这里的引用是为了获取到实参的值，这个参数并不会影响到队列数据，实际上是为了返回这个实参，相当于int MyQueue::Dequeue(){return element}，但是这里需要返回类型是bool，又想得到实参的值，只能传入引用了，这个特性在Java里面不存在。

bool MyQueue::DeQueue(int &element) //传入引用是为了可以直接修改实参的值，
{
    if (QueueEmpty())
    {
        return false;
    }
    else {
        element = m_pQueue[m_iHead] ;
        m_iHead++;
        m_iHead = m_iHead % m_iQueueCapacity;
        m_iQueueLen--;
        return true;
    }
}

9、遍历

因为要循环m_iQueueLen次，所以队列长度要加上m_iHead(队首)，i对容量取余防止队列容量溢出

void MyQueue::QueueTraverse()
{
    for (int i = m_iHead; i < m_iQueueLen + m_iHead; i++)
    {
        cout << m_pQueue[i%m_iQueueCapacity] << endl;
    }
}

转载自：https://www.cnblogs.com/Java-Starter/p/9389752.html