3.4 隊列

3.4.1 隊列的定義及運算

隊列簡稱為隊，是限定只能在表的一端進行插入運算，在另一端進行刪除運算的線性表。在表中，允許插入的一端稱為“隊尾”，允許刪除的另一端稱為“隊首”（或“隊頭”）。通常將元素插入隊尾的操作稱為入隊列（或入隊），稱刪除隊首元素的操作為出隊列（或出隊），如圖3-11所示。因為出隊時先入隊的元素先出，故隊列又被稱為是一種“先進先出”表，或稱為FIFO（First In First Out的縮寫）表。

隊列的基本運算如下。

（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，這種變化規律可以用除法取余運算（%）來實現。

入隊列操作，隊尾指示器指向下一位置：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-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;

以下是鏈隊列基本運算的算法實現。（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 */