3.2 隊列

3.2.1 隊列的定義及其基本運算

前面所講的棧是一種后進先出的數據結構，而在實際問題中還經常使用一種“先進先出”（First-In First-Out，FIFO）的數據結構：即插入在表一端進行，而刪除在表的另一端進行，這種數據結構被稱為隊或隊列（Queue），允許插入的一端稱為隊尾（rear），允許刪除的一端稱為隊頭（front）。如圖3.7所示是一個有5個元素的隊列。

入隊的順序依次為a1、a2、a3、a4、a5，出隊時的順序將依然是a1、a2、a3、a4、a5。

顯然，隊列也是一種運算受限制的線性表，所以又叫先進先出表，簡稱FIFO表。在日常生活中隊列的例子很多，如排隊買東西，排前面的買完后走掉，新來的排在隊尾。

在隊列上進行的基本操作有以下幾種。

（1）列初始化：Init_Queue(q)。

初始條件：隊列q不存在。

操作結果：構造了一個空隊列。

（2）入隊操作：In_Queue(q, x)。

初始條件：隊列q存在。

操作結果：對已存在的隊列q，插入一個元素x到隊尾，隊列發生變化。

（3）出隊操作：Out_Queue(q, x)。

初始條件：隊列q存在且非空。

操作結果：刪除隊首元素，并返回其值，隊列發生變化。

（4）讀隊頭元素：Front_Queue(q, x)。

初始條件：隊列q存在且非空。

操作結果：讀隊頭元素，并返回其值，隊列不變。

（5）判隊空操作：Empty_Queue(q)。

初始條件：隊列q存在。

操作結果：若q為空隊列則返回為1，否則返回為0。

3.2.2 隊列的存儲結構和基本運算的實現

與線性表、棧類似，隊列也有順序存儲和鏈式存儲兩種存儲方法。

1.順序隊

順序存儲的隊列稱為順序隊。因為隊列的隊頭和隊尾都是活動的，因此，除了隊列的數據區外還有隊頭、隊尾兩個指針。順序隊的類型定義如下：

define MAXSIZE  100                /*隊列的最大容量*/
typedef struct
      { datatype  data[MAXSIZE];   /*隊列的存儲空間*/
        int rear，front;           /*隊頭隊尾指針*/
      } SeQueue;

定義一個指向順序隊的指針變量：

SeQueue *sq;

申請一個順序隊的存儲空間，可使用C語言的存儲空間申請函數malloc，如下：

sq=malloc( sizeof ( SeQueue ) ) ;

隊列的數據存儲區為：

sq ->data[0] ~ sq ->data[MAXSIZE-1]

隊頭指針為：

sq ->front

隊尾指針為：

sq ->rear

設隊頭指針指向隊頭元素前面一個位置，隊尾指針指向隊尾元素（這樣的設置是為了某些運算的方便，并不是唯一的方法）。則置隊列為空，可用以下語句設置：

sq ->front=sq ->rear=-1;

在不考慮溢出的情況下，入隊操作隊尾指針加1，指向新位置后，元素入隊。操作如下：

sq ->rear++ ;
sq ->data[sq ->rear]=x;         /*將新元素x置入隊尾*/

在不考慮隊空的情況下，出隊操作隊頭指針加1，表明隊頭元素出隊。操作如下：

sq ->front++;
x=sq->data [sq->front];         /*原隊頭元素送x中*/

隊中元素的個數可以通過兩個指針的差來計算：

m=(sq -> rear) - (q ->front ) ;

顯然，隊滿時m= MAXSIZE；隊空時m=0。

按照上述思想建立的空隊、入隊、出隊過程如圖3.8所示，設MAXSIZE=10。

從圖3.8中可以看到，隨著入隊出隊的進行，會使整個隊列整體向后移動，這樣就出現了圖3.8（d）中的現象：隊尾指針已經移到了最后，再有元素入隊就會出現溢出，而事實上此時隊中并未真的“滿員”，這種現象為“假溢出”，這是由“隊尾入隊頭出”這種受限制的操作所造成。解決假溢出的方法之一是將隊列的數據區data[0..MAXSIZE-1]看成頭尾相接的循環結構，頭尾指針的關系不變，將其稱為“循環隊列”，其示意圖如圖3.9所示。

因為是頭尾相接的循環結構，入隊時的隊尾指針加1操作修改為：

sq ->rear=(sq ->rear+1) % MAXSIZE;

出隊時的隊頭指針加1操作修改為：

sq ->front=(sq ->front+1) % MAXSIZE;

設MAXSIZE=10，圖3.10是對循環隊列進行操作的示意圖。

從圖3.10所示的循環隊列可以看出，圖3.10（a）中具有a5，a6，a7，a8共4個元素，此時front=4，rear=8，隨著a9～a14相繼入隊，隊中具有10個元素——隊滿，此時front=4，rear=4，如圖3.10（b）所示，可見在隊滿情況下有front== rear。若在圖3.10（a）情況下，a5～a8相繼出隊，此時隊空，front=8，rear=8，如圖3.10（c）所示，即在隊空情況下也有front== rear。也就是說，“隊滿”和“隊空”的條件是相同的了。這顯然是必須要解決的一個問題。

方法一：設一個存儲隊列中數據元素個數的變量，如num。當num== 0時隊空，當num== MAXSIZE時為隊滿。

方法二：少用一個元素空間，把圖3.10（d）所示的情況視為隊滿，此時的狀態是隊尾指針加1就會從后面趕上隊頭指針，這種情況下隊滿的條件是：(rear+1) % MAXSIZE== front，也能和隊空區別開。下面的循環隊列及操作按方法一實現。循環隊列的類型定義及基本運算如下：

typedef struct { datatype data[MAXSIZE];     /*數據的存儲區*/
                 int front, rear;            /*隊頭隊尾指針*/
                 int num;                    /*隊中元素的個數*/
               } c_SeQueue;                  /*循環隊列*/

（1）置空隊。

c_SeQueue* Init_SeQueue( )
             { q=malloc (sizeof (c_SeQueue));
               q ->front=q ->rear=-1;  q->num=0;
               return  q;
}

（2）入隊。

int  In_SeQueue ( c_SeQueue *q , datatype x)
    { if ( num==MAXSIZE )
        { printf ("隊滿");  return – 1;     /*隊滿不能入隊*/
         }
        else { q ->rear=(q ->rear+1) % MAXSIZE;
               q ->data[q ->rear]=x;    num++ ;
               return 1;                    /*入隊完成*/
             }
}

（3）出隊。

int  Out_SeQueue (c_SeQueue *q , datatype *x)
   { if ( num==0 )
        { printf ("隊空")；
          return – 1;                     /*隊空不能出隊*/
        }
       else { q->front=(q->front+1) % MAXSIZE;
              *x=q->data[q ->front];      /*讀出隊頭元素*/
              num - -;
              return  1;                  /*出隊完成*/
}
}

（4）判隊空。

int  Empty_SeQueue ( c_SeQueue *q )
    { if (num==0) return 1;
       else return 0;
    }

2.鏈隊列

鏈式存儲的隊稱為鏈隊列。和鏈棧類似，鏈隊列可以用單鏈表來實現，根據隊的FIFO原則，為了操作上的方便，可以分別設置一個頭指針和一個尾指針，如圖3.11所示。

圖3.11中頭指針front和尾指針rear是兩個獨立的指針變量，從結構性上考慮，通常將二者封裝在一個結構中。

鏈隊列的定義如下：

typedef struct node
    { datatype  data ;
      struct node next ;
    } QNode;          /*鏈隊列結點的類型*/
typedef struct
    {  QNode  *front, *rear;
      } LQueue;        /*將頭尾指針封裝在一起的鏈隊*/

定義一個指向鏈隊列的指針：

LQueue *q ;

按這種思想建立的帶頭結點的鏈隊列如圖3.12所示。

鏈隊列的基本運算如下所述。

（1）創建一個帶頭結點的空隊。

LQueue *Init_LQueue( )
     { LQueue *q, *p;
       q=malloc (sizeof(LQueue));      /*申請頭尾指針結點*/
       p=malloc (sizeof(QNode));       /*申請鏈隊頭結點*/
       p ->next=NULL;
       q ->front=p; q->rear=p;
       return q;
}

（2）入隊。

void In_LQueue(LQueue *q , datatype x)
    { QNode *p;
      p=malloc(sizeof (QNode));     /*申請新結點*/
      p ->data=x;  p ->next=NULL;
      q ->rear ->next=p;
      q ->rear=p;
}

（3）判隊空。

int Empty_LQueue( LQueue *q)
   { if (q ->front==q->rear)  return 0;
     else return 1;
}

（4）出隊。

int Out_LQueue(LQueue *q , datatype *x)
   { QNode *p;
     if (Empty_LQueue(q) )
     { printf ("隊空")；
        return 0;                 /*隊空，出隊失敗*/
     }
     else
         { p=q ->front ->next;
           q->front ->next=p ->next;
           *x=p ->data;           /*隊頭元素放x中*/
           free ( p );
           if (q ->front ->next== NULL)  q ->rear=q ->front;
                    /*只有一個元素時，出隊后隊空，此時還需要修改隊尾指針，參考圖3.12(c)*/
           return 1;
           }
    }

3.2.3 隊列應用舉例

【例3.4】 隊列管理的模擬算法（隊列采用帶頭結點的鏈表結構）。

用鍵盤輸入數據來模擬隊列操作，采用如下管理模式：

（1）隊列初始化為空隊列；

（2）鍵盤輸入奇數時，奇數從隊尾入隊列；

（3）鍵盤輸入偶數時，隊頭指針指向的奇數出隊列；

（4）鍵盤輸入0時，退出算法；

（5）每輸入一個整數，顯示操作后隊列中的值。

void outlinkqueue (LQueue *q)
    {                /*顯示隊列q中所有元素的值*/
       QNode *p；
       p=q ->front;
       printf("Queue：")；
       while (p!= q->rear)
           { p=p ->next；
            printf ("%d"，p->data);
           }
        printf("＼n")；
      }
   main( )
   { LQueue lq，*p;
       int j ;
       p=&lq；
       Init_ LQueue( p )；
       printf ("Input a integer: ");
       scanf ("%d"，&j)；
       while ( j != 0 )
          { if ( j % 2==1)
             In_ LQueue ( p，j );      /*輸入奇數：奇數入隊列*/
            else
             j=Out_ LQueue ( p )；     /*輸入偶數：隊頭奇數出隊列*/      outlinkqueue ( p )；
             printf("＼n Input a integer: " );
             scanf ("%d"，&j )；
          }
       }