队列的顺序存储(循环队列) (C语言实现)

在前面一节中我们已经给出了队列的定义以及队列的C语言实现形式。欸欸欸、那在这里我为什么还要再搞一个顺序存储的概念和一个莫名其妙的循环队列的概念呢?

因为顺序结构简单阿,数组就可以了,多实用阿。那为什么还要一个循环队列呢?因为数组的顺序结构有问题呀,会出现假溢出。那什么是假溢出呢?就是你以为队列满了要溢出,其实还有一大堆空间空着阿。那为什么会出现这个现象呢?因为队列的头指针一直在运动阿。那怎么才能做到循环队列呢?

问得好!!!!

我不会。。。。。
但是前人会阿!!于是,我们就可以踩着前人的肩膀吃苹果了。

首先我们来具体解释解释为什么会有假溢出这个事情。
初始化队列时,令 front = rear =0;入队时,直接将新元素送入尾指针 rear 所指的单元,然后尾指针增 1;出队时,直接取出队头指针 front 所指的元素,然后头指针增 1。显然,在非空顺序队列中,队头指针始终指向当前的队头元素,而队尾指针始终指向真正队尾元素后面的单元。当 rear==MAXSIZE 时,认为队满。但此时不一定是真的队满,因为随着部分元素的出队,数组前面会出现一些空单元,如下图(d)所示。由于只能在队尾入队,使得上述空单元无法使用。把这种现象称为假溢出,真正队满的条件是 rear - front=MAXSIZE 。
这里放出一张图可以清楚的看出其中奥秘。

是不是很清楚了哈

然后我们再来说说这个循环队列到底是个什么东西。

为了解决假溢出现象并使得队列空间得到充分利用,一个较巧妙的办法是将顺序队列的数组看成一个环状的空间,即规定最后一个单元的后继为第一个单元,我们形象地称之为循环队列。假设队列数组为 Queue[MAXSIZE],当 rear+1=MAXSIZE 时,令 rear=0,即可求得最后一个单元 Queue[MAXSIZE-1]的后继:Queue[0]。更简便的办法是通过数学中的取模(求余)运算来实现:rear=(rear+1)mod MAXSIZE,显然,当 rear+1=MAXSIZE 时,rear=0,同样可求得最后一个单元 Queue[MAXSIZE-1]的后继:Queue[0]。所以,借助于取模(求余)运算,可以自动实现队尾指针、队头指针的循环变化。进队操作时,队尾指针的变化是:rear=(rear+1)mod MAXSIZE ;而出队操作时,队头指针的变化是:front=(front+1)mod MAXSIZE。

也就是说循环队列就是个环。这不就解决了假溢出的问题了嘛!

但是!

欸欸欸,好像有问题阿。当front=rear的时候到底是满的还是空的阿!!!!!emmmmmmm。。。还真不知道阿。所以在这里我们需要有一个挽救措施,那就是放弃一个存储空间。也就是当尾指针的后一个是头指针的时候,也就是(rear+1)mod MAXSIZE=front才是真正的判断条件。

最后来po出我们的队列基本操作把。这个其实以及不重要了,因为重要的是思想而不是代码。

【循环队列的类型定义】 
#define MAXSIZE 50  /*队列的最大长度*/ 
typedef struct 
{ 
     QueueElementType  element[MAXSIZE];  /* 队列的元素空间*/      
    int  front;  /*头指针指示器*/ 
    int  rear ;  /*尾指针指示器*/ 
}SeqQueue; 
【循环队列的基本操作】 

初始化操作 
void InitQueue(SeqQueue * Q) 
{  /* 将*Q 初始化为一个空的循环队列 */ 
 Q->front=Q->rear=0; 
} 

入队操作 
int EnterQueue(SeqQueue *Q, QueueElementType x) 
{  /*将元素 x 入队*/ 
    if((Q->rear+1)%MAXSIZE==Q->front)  /*队列已经满了*/       
        return(FALSE); 
    Q->element[Q->rear]=x; 
    Q->rear=(Q->rear+1)%MAXSIZE;  /* 重新设置队尾指针 */ 
    return(TRUE);  /*操作成功*/ 
} 

出队操作            
int DeleteQueue(SeqQueue *Q, QueueElementType * x) 
{ /*删除队列的队头元素,用 x 返回其值*/ 
      if(Q->front==Q->rear)  /*队列为空*/                     
       return(FALSE); 
     *x=Q->element[Q->front]; 
      Q->front=(Q->front+1)%MAXSIZE;  /*重新设置队头指针*/            
     return(TRUE);  /*操作成功*/ 
}