鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 编程语言开发 > erlang > >

环形队列

来源:互联网 作者:佚名 时间:2016-07-17 21:12
生活中有很多队列的例子,比如说到火车站买票什么的,当然先到先买,派头的买完票就可以出队列了,而想上车的人就要到队列尾排队。我们都是新世纪的好青年,所以我们也不会也不允许插队。而从生活中,我们可以抽象出队列的概念。队列就是一个能够实现“先进

  生活中有很多队列的例子,比如说到火车站买票什么的,当然先到先买,派头的买完票就可以出队列了,而想上车的人就要到队列尾排队。我们都是新世纪的好青年,所以我们也不会也不允许插队。而从生活中,我们可以抽象出队列的概念。队列就是一个能够实现“先进先出”(FIFO(first in first out))的存储结构。队列分为普通队列和环形队列。先讲一讲普通队列,这样有助于理解环形队列的好处。

普通队列

普通队列一般由数组构成。都是先进先出,队列中容量有限制。但是主要不同是在处理方式上。

第一种处理方式:计算机由队头开始处理,前面的处理完,后面的数据移到前面继续处理。这样很明显效率很慢。(如下图)
这里写图片描述
第二种处理方式:计算机从队头开始处理,前面的处理完后,计算机移到下一个单元处理 。这样的话,前面的存储单元用完后就空着,要知道队列容量是有限的,这样便造成了队列的空间浪费。(如下图)
这里写图片描述

环形队列

环形队列能够很好的解决这个问题,它有如下特点。它是一个首尾相连的FIFO的数据结构,采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。因为有简单高效的原因,甚至在硬件都实现了环形队列。环形队列广泛用于网络数据收发,和不同程序间数据交换(比如内核与应用程序大量交换数据,从硬件接收大量数据)均使用了环形队列。

环形队列原理内存上没有环形的结构,因此环形队列实上是数组的线性空间来实现。那当数据到了尾部如何处理呢?它将转回到0位置来处理。这个的转回是通过取模操作来执行的。 因此环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接,形成一个存放队列的环形空间。为了方便读写,还要用数组下标来指明队列的读写位置。head/tail.其中head指向可以读的位置,tail指向可以写的位置。

先看环形队列头文件了解大概需要实现的内容。

//文件:   Circinal Queue.h

class CirQueue
{
public:
    CirQueue(int queueCapacity);    //队列初始化
    ~CirQueue();                   //构销函数

    int QueueLenth();               //得到队列长度

//元素入队和出队是两个重要的函数。
    bool EnQueue(int element);      //元素入队
    bool DeQueue(int &element);     //元素出队
    bool QueueEmpty();              //队列判空
    bool QueueFull();               //队列判满
    void ClearQueue();              //清空队列

//遍历需要注意循环条件
    void QueueTravel();             //队列遍历

private:
    int *m_pQueue;                  //队列指针
    int m_iHead;                    //队列头       
    int m_iTail;                    //队列尾
    int m_iQueueLenth;              //队列长度
    int m_iQueueCapacity;           //队列容量
};

判断队列空或队列满函数:在类里面定义了队列容量和队列长度这两个成员。判断队列是否为空,则便判断队列长度是否为0,如果是则为空。而判断队列是否为满,则判断队列长度是否等于队列容量,如果是则为满。

接下来看入队和出队这两个重要的函数:

bool CirQueue::EnQueue(int element)
{
    if (QueueFull())
    {
        return false;
    }
    else
    {
        m_pQueue[m_iTail] = element;
        m_iTail++;
        //因为队列是环形,所以tail需要通过取模来实现转回到0位置
        m_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLenth++;
        return true;
    }
}
//元素出队
bool CirQueue::DeQueue(int &element)
{
    if (QueueEmpty())
    {
        return false;
    }
    else
    {
        element = m_pQueue[m_iHead];
        m_iHead++;
        //因为队列是环形,所以head需要通过取模来实现转回到0位置
        m_iHead = m_iHead % m_iQueueCapacit;
        m_iQueueLenth--;    
        return true;
    }

}

一,入队时需要注意判断队列是否满,满则不能加入。出队时需判断队列是否空,空则不能出队。
二,入队和出队都差不多,尾部的空间得到入队的元素,然后tail往下一个储存空间移动。而出队时是头部的空间储存的值将赋给引用的值,然后head也是往下一个储存空间移动。
三,入队,队列长度增加。出队,队列长度减小。

入队与出队(如图)

入队
出队

这里需要注意的是入队和出队完后,head和tail的下标改变。
入队下标改变
出队也如此。
所以由于环形队列是循环利用空间,即上面环形队列的原理,则下标增加时也需要有循环。这里用取余来使tail或head在到环形尾后又转回到0。

另外一个重点是队列的遍历:

void CirQueue::QueueTravel()
{
    for (int i = m_iHead; i < m_iQueueLenth + m_iHead; i++) 
    //从头部开始
    //循环条件应为元素个数(为补偿i从头部数开始,则循环条件需加上m_iHead)
        cout << m_pQueue[i%m_iQueueCapacity] << endl;   
        //因为队列是环形,则元素下标也应该像环形一样循环
    }
    cout << endl;
}

一,遍历当然是从头部开始,循环次数应该为队列长度。为了补偿i=head的数,则i要小于队列长度加上头部数。
二,打印元素:与上面入队和出队下标改变的一样。元素下标也应能够到队列环形的尾部时,又转回到0再进行下去。

以下为所有.cpp源码

文件: Circinal Queue.cpp

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

//队列初始化,确认队列容量,申请内存。头尾和长度为0
CirQueue::CirQueue(int queueCapacity)
{
    m_iQueueCapacity = queueCapacity;
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLenth = 0;
    m_pQueue = new int[queueCapacity];

}
//队列构销
CirQueue::~CirQueue()
{
    delete[]m_pQueue;
    m_pQueue = NULL;
}
//得到队列长度
int CirQueue::QueueLenth()
{
    return m_iQueueLenth;       //返回队列的长度
}
//清空队列,但内存仍不变。只是头尾和长度归0
void CirQueue::ClearQueue()
{
    m_iHead = 0;
    m_iTail = 0;
    m_iQueueLenth = 0;
}
//队列判空,如果长度=0则为空,这时没有元素可以出队
bool CirQueue::QueueEmpty()
{
    if (m_iQueueLenth == 0)
    {
        return true;
    }
    return false;
}
//队列判满,如果长度=容量,则此时不能有元素入队
bool CirQueue::QueueFull()
{
    if (m_iQueueLenth == m_iQueueCapacity)
    {
        return true;
    }
    else
    {
        return false;
    }
}
//元素入队
bool CirQueue::EnQueue(int element)
{
    if (QueueFull())
    {
        return false;
    }
    else
    {
        m_pQueue[m_iTail] = element;
        m_iTail++;
        //因为队列是环形,则m_iTail也应该像环形一样循环
        m_iTail = m_iTail % m_iQueueCapacity;
        m_iQueueLenth++;
        return true;
    }
}
//元素出队
bool CirQueue::DeQueue(int &element)
{
    if (QueueEmpty())
    {
        return false;
    }
    else
    {
        element = m_pQueue[m_iHead];
        m_iHead++;
        //因为队列是环形,则m_iHead也应该像环形一样循环
        m_iHead = m_iHead % m_iQueueCapacity;
        m_iQueueLenth--;    
        return true;
    }

}
//队列遍历
void CirQueue::QueueTravel()
{
    for (int i = m_iHead; i < m_iQueueLenth + m_iHead; i++) 
    //从头部开始
  //循环条件应为元素个数(为补偿i从头部数开始,则循环条件需加上m_iHead)
        cout << m_pQueue[i%m_iQueueCapacity] << endl;   
        //因为队列是环形,则元素下标也应该像环形一样循环
    }
    cout << endl;
}
文件:main.cpp

#include <iostream>
#include "Circinal Queue.h"

using namespace std;

int main()
{
    CirQueue *p = new CirQueue(4);
    //元素入队
    p->EnQueue(1);
    p->EnQueue(2);
    p->EnQueue(3);
    p->EnQueue(4);
    //得到此时队列长度为4
    cout <<"queue lenth 1: "<< p->QueueLenth() << endl;
    //遍历队列,此时可以将1,2,3,4都打印出来
    p->QueueTravel();

    //元素出队
    int e = 0;
    p->DeQueue(e);
    //此时队列中的1出队,e得到值1,将打印出1
    cout<< "out 1:"<< e << endl;

    //此时队列中的2出队,e得到值2,将打印出2
    p->DeQueue(e);
    cout <<"out 2: "<< e << endl;

    //得到此时队列长度为2
    cout <<"queue lenth 2: " << p->QueueLenth() << endl;
    //清空队列
    p->ClearQueue();
    //什么都打不出来
    p->QueueTravel();

    //调用构销函数
    delete p;
    p = NULL;

    system("pause");
}

参考博客及拓展阅读:

http://blog.csdn.net/sking002007/article/details/6584590#
http://blog.csdn.net/lpp0900320123/article/details/20694409

上一篇:ajax总结
下一篇:线程(代码实现)详解
网友评论
<