队列

队列的定义及基本运算

　　栈是一种后进先出的数据结构，在实际问题中还经常使用一种“先进先出”的数据结构： 即插入在表一端进行，而删除在表的另一端进行，将这种数据结构称为队或队列，把允许插入的一端叫队尾(rear) ，把允许删除的一端叫队头(front)。

队列的存储实现及运算实现

与线性表、栈类似，队列也有顺序存储和链式存储两种存储方法。

基本操作：

（1） InitQueue(&Q)：初始化操作。设置一个空队列。

（2） IsEmpty(Q)：判空操作。若队列为空，则返回 TRUE，否则返回 FALSE。

（3） IsFull(Q)：判满操作。若队列为满，则返回 TRUE，否则返回 FALSE。

（4） EnterQueue(&Q，x)：进队操作。在队列 Q 的队尾插入 x。操作成 功，返回值为 TRUE，否则返回值为 FALSE。

（5） DeleteQueue(&Q,&x)：出队操作。使队列 Q 的队头元素出队，并 用 x 带回其值。操作成功，返回值为 TRUE，否则返回值为 FALSE。

（6） GetHead（Q,&x）：取队头元素操作。用 x 取得队头元素的值。操 作成功，返回 TRUE，否则返回值为 FALSE。

（7） ClearQueue(&Q)：队列置空操作。将队列 Q 置为空队列。

（8） DestroyQueue(&Q)： 队列销毁操作。释放队列的空间。

1．顺序队列

循环队列的类型定义如下：

#define MAXQSIZE  100     //大队列长度 typedef struct {       QElemType  *base;     //动态分配存储空间       int  front;           //头指针，若队列不空，指向队列头元素       int  rear;            //尾指针，若队列不空，指向队列尾元素的下一个位置 } SqQueue;

（1）入队：

int EnQueue (SqQueue &Q, QElemType e) {     if((Q.rear+1)%MAXQSIZE == Q.front) return ERROR;        Q.base[Q.rear] = e;         Q.rear = (Q.rear+1) % MAXQSIZE;         return OK; }

（2）出队：

int DeQueue (SqQueue &Q, QElemType &e) {     if (Q.front = = Q.rear)  return ERROR;         e = Q.base[Q.front];         Q.front = (Q.front+1) % MAXQSIZE;         return OK; }

（3）求循环队列元素个数：

int QueueLength（SqQueue Q）{     return (Q.rear-Q.front+MAXQSIZE) %MAXQSIZE；    }

2．链队列

　　链式存储的队称为链队列。和链栈类似，用单链表来实现链队列，根据队的先进先出原 则，为了操作上的方便，分别需要一个头指针和尾指针。队头指针始终指向头结点，队尾指针指向当前最后一个元素。空的链队列的队头指针和队尾指针均指 向头结点。

　　链队列的形式描述如下：

typedef struct QNode { // 结点类型         QElemType   data;         struct QNode  *next; } QNode, *QueuePtr; typedef struct {      //链队列类型         QueuePtr  front;  //队头指针         QueuePtr  rear;   //队尾指针 } LinkQueue;

　　定义一个指向链队列的指针：LinkQueue Q;

下面是链队列的基本运算的实现。

（1）初始化

int InitQueue(LinkQueue * Q)   { /* 将 Q 初始化为一个空的链队列 */       Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode));        if(Q->front!=NULL)            {                Q->rear=Q->front;                 Q->front->next=NULL; return(TRUE); } else return(FALSE); /* 溢出！*/ }

（2）入队

int EnQueue (LinkQueue &Q, QElemType e) {     QNode *p;     p = （QNode *）malloc（sizeof（QNode））;     p->data = e;        p->next = NULL;     Q.rear->next = p;     Q    .rear = p;        return OK; }

（3）出队

int DeQueue (LinkQueue &Q, QElemType &e) {    if (Q.front == Q.rear)  return ERROR; //队空，出队失败       p = Q.front->next;        e = p->data;                       //队头元素放 e 中       Q.front->next = p->next;       if(Q.rear==p)   Q.rear= Q.front;   //只有一个元素时，此时还要修改队尾指针     free (p);    return OK;  }

3．除了栈和队列之外，还有一种限定性数据结构是双端队列。

（1）双端队列：可以在双端进行插入和删除操作的线性表。

（2）输入受限的双端队列：线性表的两端都可以输出数据元素，但是只能在一端输入数 据元素。

（3）输出受限的双端队列：线性表的两端都可以输入数据元素，但是只能在一端输出数 据元素。

队列的顺序存储（循环队列）

1． 顺序队列的假溢出现象

队列的一种顺序存储称为顺序队列。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素，如一维数组 Queue[MAXSIZE]。

由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针 front 和 rear。

front:指示队头元素在数组中的位置；

rear:指示真实队尾元素相邻的下一个位置。

　　初始化队列时，令 front = rear =0；入队时，直接将新元素送入尾指针 rear 所指的单元， 然后尾指针增 1；出队时，直接取出队头指针 front 所指的元素，然后头指针增 1。显然，在 非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后 面的单元。当 rear==MAXSIZE 时，认为队满。但此时不一定是真的队满，因为随着部分元 素的出队，数组前面会出现一些空单元。由于只能在队尾入队，使得上述 空单元无法使用。把这种现象称为假溢出，真正队满的条件是 rear - front=MAXSIZE 。

2． 循环队列

　　为了解决假溢出现象并使得队列空间得到充分利用，一个较巧妙的办法是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，我们形象地称之为循环队列。假设队列数组为 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。 下图给出了循环队列的几种情况。

【循环队列判空判满问题】

　　与一般的非空顺序队列相同，在非空循环队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。在下图 (c)所示 循环队列中，队列头元素是 e3，队列尾元素是 e5，当 e6、e7和 e8相继入队后，队列空间均被占满，如上图 (b)所示， 此时队尾指针追上队头指针，所以有：front =rear。反之，若 e3、e4 和 e5相继从上图 (c)的 队列中删除，则得到空队列，如上图 (a)所示，此时队头指针追上队尾指针，所以也存在关 系式：front = rear。可见，只凭 front = rear 无法判别队列的状态是“空”还是“满”。

有两种处理方法：

　　一种方法是少用一个元素空间。当队尾指针所指向的空单元 的后继单元是队头元素所在的单元时，则停止入队。这样一来，队尾指针永远追不上队头指 针，所以队满时不会有 front =rear。现在队列“满”的条件为（rear+1）mod MAXSIZE=front。 判队空的条件不变，仍为 rear=front。

另一种是增设一个标志量的方法，以区别队列是“空” 还是“满”。主要介绍损失一个存储空间以区分队列空与满的方法。

循环队列的类型定义

#define MAXSIZE 50  /*队列的最大长度*/ typedef struct{      QueueElementType  element[MAXSIZE];  /* 队列的元素空间*/      int  front;  /*头指针指示器*/      int  rear ;  /*尾指针指示器*/ }SeqQueue;

循环队列的基本操作

（1） 初始化操作

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

（2） 入队操作

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);  /操作成功/ }

（3）出队操作

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);  /*操作成功*/     }

　　这里采用了第一种处理假溢出问题的方法。如果采用第二种方法，则需要设置一个标志 量 tag。初始化操作即产生一个空的循环队列，此时 Q->front = Q->rear=0，tag=0；当空 的循环队列中有第一个元素入队时，则 tag=1，表示循环队列非空；当 tag=1 且 Q->front=Q->rear 时，表示队满。