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 */