数据结构与实训
上QQ阅读APP看本书，新人免费读10天
设备和账号都新为新人
上一章目录下一章

3.4 队列

3.4.1 队列的定义及运算

队列简称为队，是限定只能在表的一端进行插入运算，在另一端进行删除运算的线性表。在表中，允许插入的一端称为“队尾”，允许删除的另一端称为“队首”（或“队头”）。通常将元素插入队尾的操作称为入队列（或入队），称删除队首元素的操作为出队列（或出队），如图3-11所示。因为出队时先入队的元素先出，故队列又被称为是一种“先进先出”表，或称为FIFO（First In First Out的缩写）表。

图3-11 队列

队列的基本运算如下。

（1）InitQueue()，初始化队列。

（2）QueueEmpty(q)，判定队列q是否为空。

（3）QueueLength(q)，求队列q的长度。

（4）GetHead(q)，获取队列q队首元素的值。

（5）AddQueue (q,e)，将元素e入队列。

（6）DeleteQueue (q)，删除队首元素（队首元素出队列）。

3.4.2 队列的顺序存储结构

与线性表类似，队列也有两种存储表示，其顺序存储结构称为顺序队列。对于顺序队列也需要事先为它分配一个可以容纳最多元素的存储空间，即一维数组，以及队首指示器和队尾指示器，它们分别表示队首元素、队尾元素在队列中的位置值（序号）。

如图3-12所示是MaxSize=5的队列的动态变化示意图，图3-12（a）表示初始的空队列；图3-12（b）表示入队5个元素后队列的状态；图3-12（c）所示是队首元素出队1次后队列的状态；图3-12（d）所示是队首元素出队4次后队列的状态。

从图3-12中可以看出，图3-12（a）所示为队列的初始空状态，有front==rear成立，该条件可以作为队列空的条件。那么能不能用rear==MaxSize-1作为队列满的条件呢？显然不能，图3-12（d）所示队列为空，但满足该条件。如果对图3-12（d）继续执行入队列操作，则会出现“上溢出”，这种溢出并不是真正的溢出，因为在elem数组中存在可存放元素的空位置（实际上elem为空数组），所以这是一种假溢出。为了能充分地利用数组空间，就可以将数组的首尾相接，形成一个环状结构，即把存储队列元素的表从逻辑上看成一个环，称其为循环队列。

循环队列首尾相连，当rear=MaxSize-1时，若再对该队列进行入队操作，则rear的值应为0，这种变化规律可以用除法取余运算（%）来实现。

图3-12 队列操作

入队列操作，队尾指示器指向下一位置：rear=(rear+1) % MaxSize。

出队列操作，队首指示器指向下一位置：front=(front+1) % MaxSize。

循环队列的类型描述如下。

#define MaxSize 队列可能达到的最大长度
typedef struct
{ ElementType elem[MaxSize];
  int front,rear;  /*队首、队尾指示器*/
} CirQueue;

有如下循环队列：

CirQueue q；

初始化时，q.front=q.rear=-1，那么队列q为空和为满的条件是什么呢？显然循环队列为空的条件是q.front==q.rear。如果入队列的速度快于出队列的速度，队尾指示器的值就会赶上队首指示器的值，即q.front==q.rear，此时循环队列为满。这样就无法区分循环队列是空还是满。为了对循环队列空、满加以区分，常采用的方法之一是始终让front指示队首元素的前一位置（front所指位置不存放队列元素），这样就有一个存储单元被浪费，如图3-13所示。如此约定后就有：

初始化时：q.front=q.rear=0。

循环队列为空的条件是：q.front==q.rear。

循环队列为满的条件是：q.front==(q.rear+1) % MaxSize。

循环队列基本运算的实现算法如下。

（1）初始化队列，InitQueue(q)。

CirQueue InitQueue()
{  CirQueue q;
   q.front=q.rear=0;
   return(q);
}/* InitQueue */

（2）判定队列q是否为空，QueueEmpty(q)。

int QueueEmpty(CirQueue q)
{
      return(q.front==q.rear);
}/* QueueEmpty */

（3）求队列q的长度，QueueLength(q)。

int QueueLength(CirQueue q)
{
      return((q.rear+MaxSize – q.front) % MaxSize);
}/* QueueLength */

（4）获取队列q队首元素的值，GetHead(q)。

ElementType GetHead(CirQueue q)
{  if (QueueEmpty(q))  /*空队列*/
        return(nil);/* nil表示与ElementType对应的空值*/
    return(q.elem[(q.front+1) % MaxSize]);
}/* GetHead */

（5）将元素e入队列，AddQueue (q,e)。

Void AddQueue(CirQueue *q,ElementType e)
{  if (q->front==(q->rear+1) % MaxSize) /*队满*/
         printf(“\nFull”);
   else
   {  q->rear=(q->rear+1) % MaxSize;
      q->elem[q->rear]=e ;
   }
} /* AddQueue */

（6）删除队首元素，DeleteQueue (q)。

ElementType DeleteQueue(CirQueue *q)
{  if (q->front==q->rear)   /*队空*/
        return(nil);/* 返回空值*/
   else
   {  e=q->elem[(q->front+1) % MaxSize];
      q-> front=(q-> front+1) % MaxSize;
      return (e);
   }
}/* DeleteQueue */

图3-13 循环队列操作

【例3-9】若在循环队列的两端都可以进行插入和删除操作（这样的队列被称为双端队列），试给出双端队列的队首插入、队尾删除操作的算法。

双端队列仍然可使用前面所定义的CirQueue类型，其队首插入、队尾删除算法如下。

void AddQueueInFront(CirQueue *q,ElementType e)
/* 将元素e插入双端队列q队首 */
{  if (q->front==(q->rear+1) % MaxSize) /*队满*/
         printf(“Full”);
   else
   {  q->elem[q->front]=e;
      q-> front=(q-> front -1+MaxSize) % MaxSize ;
}
} /* AddQueue */
ElementType DeleteQueueInRear(CirQueue *q)
/* 将双端队列q队尾元素出队列 */
{  if (q->front==q->rear)   /*队空*/
         return(nil);  /*返回空值*/
   else
   {  e=q->elem[q->rear];
      q->rear=(q->rear - 1+MaxSize) % MaxSize;
      return (e);
   }
}/* DeleteQueue */

3.4.3 队列的链式存储结构

与线性表的链式存储结构相对应，队列的链式存储称为链队列。它是插入和删除受限的单链表，即插入只能在表尾，删除只能在表头进行，相应地需要设置两个指针：队首指针与队尾指针。基于算法实现的方便性，再附加一头结点，队首指针指向头结点，队尾指针指向尾结点，如图3-14所示。对链队列的类型描述如下。

typedef struct Qnode
{ ElementType data;
  struct Qnode *next;
}QueueNode;
typedef struct
{ QueueNode *front,*rear;
}LinkQueue;

图3-14 链队列

以下是链队列基本运算的算法实现。（1）初始化队列，InitQueue()。

LinkQueue InitQueue()
{
    p=(QueueNode *)malloc(sizeof(QueueNode));
    p->next=NULL;
    q.front=q.rear=p;
    return(q);
}/* InitQueue */

（2）判定队列q是否为空，QueueEmpty(q)。

int QueueEmpty(LinkQueue q)
{
     return(q.front==q.rear);
}/* QueueEmpty */

（3）获取队列q队首元素的值，GetHead(q)。

ElementType GetHead(LinkQueue q)
{
    if (QueueEmpty(q))  /*空队列*/
        return(nil);/* nil表示与ElementType对应的空值*/
    return(q.front->next->data);
}/* GetHead*/

（4）将元素e入队列，AddQueue (q,e)。

Void AddQueue(LinkQueue *q,ElementType e)
{
   p=(QueueNode *)malloc(sizeof(QueueNode));/*生成新结点，并由p指向它*/
   p->data=e;
   p->next=NULL;
   q->rear->next=p;
   q->rear=p;
} /* AddQueue */

（5）出队列，DeleteQueue (q)。

ElementType DeleteQueue(LinkQueue *q)
{  if (QueueEmpty(q)) /*队列空*/
        return(nil);/*返回空值*/
   else
   {  p=q->front->next;
      q->front->next=p->next;
      e=p->data;
      if (p==q->rear) q->rear=q->front;
      free(p)
      return(e);
}
} /* DeleteQueue */

【例3-10】链队列q中存放有一批整数，写一算法，试将该队列中的正整数、零及负整数分别存放在两条不同的链队列q1、q2中，并且q1、q2中的值要求保持原来的相对顺序。

链队列q1、q2中的值来源于q队列，并且其中的值要保持原来的相对顺序，那么就需要对q连续地执行出队列操作，并每次对q中出队列的元素x进行判断：若x>0，进q1；若x≤0，进q2。直到q为空。

算法具体描述如下。

int Splitting(LinkQueue q,LinkQueue *q1,LinkQueue *q2 )
/*将存放整数的链队列q拆分为两条队列q1（存放正整数）与q2（零及负整数），且q1、q2中的
值要保持原来的相对顺序*/
{  while (!QueueEmpty(q))
   {  x=DeleteQueue (&q);
      if (x>0)
            AddQueue(q1,x);
      else
            AddQueue(q2,x)
      }
} /* Splitting */
上一章目录下一章