循环队列的实现

队列的一个非常重要的特点就是：只允许在队列的头部进行删除操作，只允许在队列的尾部进行插入操作。

公司主营业务：网站设计制作、成都网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联公司是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联公司推出韶山免费做网站回馈大家。

所以，很明显，队列这种结构需要两个指针，一个指针指向队列的头部，一个指针指向队列的尾部。既然队列这种结构也是用来存放数据的，当有一个数据存入队列中时，指向尾部的指针就向后加1，当删除一个元素时，头指针就向后加1，由于我们定义当队列为空时，指向头部的指针和指向尾部的指针重合，所以，当删除到剩余最后一个元素时，头指针front和尾指针rear就重合了，这样会和我们定义的队列为空两指针重合相矛盾。所以，我们要做的就是，将尾指针rear指向队列尾部的下一个位置。这样，问题就解决了。

如果有数据插入，我们可以将rear+1，当数据不需要而要将其删除时，我们将front+1,直到rear指向队列尾部的下一个位置，已经没有位置可以放新的元素了，那么此时队列真的已经满了吗？当然没有，因为删除一个元素时，front++，所以，在front前面还有位置可以放元素，所以此时，这种虚假的队列满的情况，称之为“假溢出”。

那么如何解决这个假溢出的现象呢？当然有办法，就是通过循环队列，当rear指针指向最后一个位置时，就将它置为0，指向队列头部。那假设我们有了一个循环队列，当rear向后自增，又从0开始接着向后自增，直到和front重合时，队列满。这样一来，我们又带来一个问题，我们怎么判断rear==front到底是队列为空还是队列是满的呢？解决的办法就是空出一个单元，不存放任何数据，也就是当rear+1 == front时，就意味着满队列了。所以，判断满队列的条件就是:

( reat + 1 ) % QueueSize == front;

此时，就认为是满队列状态。

那么我该如何计算队列的长度呢？因为rear有可能比front大也有可能比front小，我该如何确定队列的元素个数呢？第一种情况，rear > front。此时，只要将rear - front就可以计算出队列的长度了。

循环队列的实现

由图所示，图中有2个元素，a3和a4。所以，我们要计算队列长度，只需将rear-front，就可以得出结果了。第二种情况，rear < front。如图所示：

循环队列的实现

当碰到这种出现假溢出形式的时候，我们该如何计算队列的长度呢？很明显，此时，队列长度的计算分为两段，一段是front之后的元素，一段是rear之前的元素，计算A3和A4这两个元素，我们只需(QueueSize - front)这样以来，就算出来了，此时QueueSize的值为5，那么(5 - 3 )的值为2，所以，第一段元素的长度为2，第二段元素长度，只需要(0 + rear ) 就可以了，也就是(0 + 2 ),此时值为2，所以，队列真正的长度就为(2 + 2 = 4 ), 那么队列的长度就计算出来了。

因为有两种情况，所以，为了实现通用，就有一个标准的计算队列长度的公式：

( rear - front + QueueSize ) % QueueSize

接下来，就来定义一个循环队列的结构：

typedef int QElemType;

typedef struct{

    QElemType data[MAXSIZE];
    int front;
    int  rear;
}SqQueue;

如果要初始化一个队列，我们该如何做呢？

Status InitQueue ( SqQueue *Q ){

    Q->front = 0;
    Q->rear = 0;
    
    return OK;
}

求循环队列的长度

int QueueLength ( SqQueue Q ){

    return ( Q.rear - Q.front + MAXSIZE ) % MAXSIZE;

}

循环队列元素的插入

Status EnQueue ( SqQueue *Q, QElemType e ){

    if ( ( Q->rear + 1 ) % MAXSIZE == front )
        return ERROR;
    
    Q->data[Q->rear] = e;
    Q->rear = ( Q->rear + 1 ) % MAXSIZE;
    
    return OK; 

}

循环队列元素的删除

Status DeQueue ( SqQueue *Q, QElemType *e ){

    if ( Q->rear == Q->front )
        return ERROR;
        
    *e = Q->data[Q->front];
    Q->front = ( Q->front + 1 ) % MAXSIZE;
    
    return OK;

}

网站名称：循环队列的实现
网站URL：http://azwzsj.com/article/gjpdog.html

循环队列的实现

其他资讯