3.5 队列典型题例

【例3-11】已知循环队列存储空间为数组a[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度是多少?

【分析与解答】循环队列长度=(q.rear+MaxSize – q.front) % MaxSize=3+21-8=16。亦即当前队列元素位于：

a[9],a[10],a[11],…,a[19],a[20],a[0],a[1],a[2],a[3]

【例3-12】简述下列算法的功能。

void Inverse(CirQueue *q )
{  SeqStack s;
   while (!QueueEmpty(*q))
      Push(s,DeleteQueue (q));
   while(!StackEmpty(s))
      AddQueue(q,Pop(s));
} /* Inverse */

【分析与解答】第1个while循环将q队列的全部元素出队，出队后进入堆栈s。第2个while循环则将s的全部元素出栈后又进入q队列，q中存放的是原来元素的逆序。所以算法借用堆栈s实现了q队列的逆置。

【例3-13】假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点，试编写入队列算法。

【分析与解答】图3-15所示是仅有队尾指针的循环链队列，入队算法如下。

Void AddQueue(LinkQueue *q,ElementType e)
{
   p=(QueueNode *)malloc(sizeof(QueueNode));/*生成新结点，并由p指向它*/
   p->data=e;
   p->next=q->rear->next;/*p->next指向头结点*/
   q->rear->next=p;/*成为新的队尾元素*/
   q->rear=p;/*改变队尾指针*/
} /* AddQueue */

【例3-14】如果用一个数组q[0..m-1]表示循环队列，该队列只有一个队列头指针front，不设队列尾指针rear，而改设计数器count用以记录队列中元素的个数。

（1）编写入队算法；

（2）此种队列能容纳元素的最大个数是多少？

【分析与解答】用此种方法表示队列时，为空的条件是count=0，为满的条件是count=m，入队算法如下。

Void AddQueue(CirQueue *q,ElementType e)
{  if (count==m) /*队满*/
       printf(“Full”);
   else
   {
       q->elem[(q->front+count]% m]=e ;
       count++;
   }
} /* AddQueue */

此种队列能容纳元素的最大个数是m。

【例3-15】n条循环队列构成一组，用一个数组存放该队列组中每条队列的头指针与尾指针，试给出该组队列的数据类型定义，若队列编号分别为：0,1,2,…,n-1，试写算法：

（1）求i队列的长度；

（2）i队列首元素出队列。

【分析与解答】一条循环队列中的元素是用一个一维数组存放的，一组（n条）循环队列的元素则可用一个二维数组存放。一条队列对应头、尾两个指针，一组（n条）队列的n个头指针与n个尾指针亦应用一个二维数组表示。其数据类型定义如下。

#define MaxSize 队列可能达到的最大长度
typedef struct
{
       ElementType Queue[n][MaxSize]; /*n条循环队列*/
       int Position[n][2]; /* n条循环队列的队首、队尾位置指示器*/
} GroQueue  /*队列组*/
int QueueLength(GroQueue gq,int i) /*求i队列的长度*/
{
     if (i<0 || i>=n)
     {
          printf(“Error”);
          return(-1);
      }
      return((gq. Position[i][1]+MaxSize –gq. Position[i][0]) % MaxSize);
}/* QueueLength */
ElementType DeleteQueue(GroQueue *gq,int i) /* i队列首元素出队列*/
{
     if (i<0 || i>=n)
     {
          printf(“Error”);
          return(nil); /* 返回空值*/
      }
      if (gq-> Position[i][0]==gq-> Position[i][1])   /*队空*/
          return(nil);
      else
      {    e=gq-> Queue[(gq. Position[i][0]+1) % MaxSize];
           gq. Position[i][0]=(gq. Position[i][0]+1) % MaxSize;
           return (e);
      }
}/* DeleteQueue */