即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

数据结构之循环队列(面向对象思想c++实现)

编程语言 T_IS_BEHINGD_T 128℃ 0评论

队列是一种数据结构,它具有先进先出的特点,即FIFO(first in first out)。队列一般有普通队列和循环队列两种形式。我们用数组来实现队列, 使用一般的普通队列,当我们把队头元素out的时候,队头后的元素会逐一向前挪动,这样就大大降低了处理效率。

这里写图片描述


循环队列不仅提高了效率,而且也提升了空间利用率。循环队列的具体构造如下图。


循环队列


接下来,我们先定义循环队列中的属性和方法,然后重点分析两个方法。在此声明,我们用数组来实现一个队列,且该数组为int类型数组。


循环队列的具体代码如下:

class MyQueue{
public:
    MyQueue(int queueCapacity); //初始化构建循环队列
    virtual ~MyQueue(); //销毁队列
    void ClearQueue(); //清空队列
    bool QueueEmpty() const; //判断队列是否为空
    bool QueueFull(); //判断队列是否为满
    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; //队尾
};
#include 'MyQueue'
#include 
using namespace std;
MyQueue::MyQueue(int queueCapacity){
    m_iQueueCapacity = queueCapacity;
    m_pQueue = new int[m_iQueueCapacity];
    ClearQueue();
}
MyQueue::~MyQueue(){
    delete []m_pQueue;
    m_pQueue = NULL;
}
void MyQueue::ClearQueue(){
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLen = 0;
}
bool MyQueue::QueueEmpty() const{
    if(0 == m_iQueueLen){
        return true;
    }
    else{
        return false;
    }
}
int MyQueue::QueueLength() const{
    return m_iQueueLen;
}
bool MyQueue::QueueFull(){
    return m_iQueueLen == queueCapacity ? true : false;
}
bool MyQueue::EnQueue(int element){
    if (QueueFull())
    {
        return 0;
    }
    else{
        m_pQueue[m_iTail] = element;
        m_iTail++;
        m_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLen++;
        return true;
    }
}
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;
    }
}
void MyQueue::QueueTraverse(){
    for (int i = m_iHead; i < m_iQueueLen; i++)
    {
        cout<

我们详解EnQueue(int element)方法(DeQueue(int &element)同理)中的一个重点。


EnQueue(int element):


其中我们每向队列中添加一个元素的时候,m_iTail就会加1,这样下去m_iTail就会无限制的继续变大,而此时我们的处理办法就是m_iTail = m_iTail % m_iQueueCapacity,这样每当m_iTail指向超过m_iQueueCapacity的时候,就会得到纠正。

转载请注明:CodingBlog » 数据结构之循环队列(面向对象思想c++实现)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情