一、隊列的定義

隊列是啥？

數(shù)據(jù)從表的一端進(jìn)，從另一端出，且遵循 "先進(jìn)先出" 原則的線性存儲結(jié)構(gòu)就是隊列。

隊列的兩個基本操作：入隊將一個數(shù)據(jù)放到隊列尾部；出隊從隊列的頭部取出一個元素。

隊列的應(yīng)用：循環(huán)隊列、阻塞隊列、并發(fā)隊列、優(yōu)先級隊列等。

棧和隊列不要混淆，棧結(jié)構(gòu)是一端封口，特點是"先進(jìn)后出"；而隊列的兩端全是開口，特點是"先進(jìn)先出"。

隊列存儲結(jié)構(gòu)的實現(xiàn)有以下兩種方式：

1. 順序隊列：在順序表的基礎(chǔ)上實現(xiàn)的隊列結(jié)構(gòu)；
2. 鏈隊列：在鏈表的基礎(chǔ)上實現(xiàn)的隊列結(jié)構(gòu)；

兩者的區(qū)別僅是順序表和鏈表的區(qū)別，即在實際的物理空間中，數(shù)據(jù)集中存儲的隊列是順序隊列，分散存儲的隊列是鏈隊列。

隊列的操作

入隊（尾部入隊）
　?、賹⒅荡嫒雛ear所代表的位置。
　?、趓ear = (rear+1)%數(shù)組的長度。
出隊（頭部出隊）
　　front = (front+1)%數(shù)組的長度。
隊列是否為空
　　front和rear的值相等，則該隊列就一定為空。

假溢出

隨著入隊、出隊的進(jìn)行，會使整個隊列整體向后移動，就會出現(xiàn)上圖中的現(xiàn)象：隊尾指針已經(jīng)移到了最后，即隊尾出現(xiàn)溢出，無法再進(jìn)行入隊操作，然而實際上，此時隊列中還有空閑空間，這種現(xiàn)象稱為“假溢出”。

解決“假溢出”的三種辦法：

方法一：每次刪除隊頭元素后，把整個隊列向前移動一個位置，這樣可保證隊頭元素在存儲空間的最前面。但每次刪除元素時，都要把表中所有元素向前移動，效率太低。

方法二：當(dāng)隊尾指針出現(xiàn)溢出時，判斷隊頭指針位置，如果前部有空閑空間，則把當(dāng)前隊列整體前移到最前方。這種方法移動元素的次數(shù)大為減少。

方法三：將隊列看成頭尾相接的循環(huán)結(jié)構(gòu)，當(dāng)隊尾指針到隊尾后，再從隊頭開始向后指，這樣就不需要移動隊列元素了，顯然，第三種方法最經(jīng)濟(jì)、應(yīng)用最多，這種順序隊列被稱為“循環(huán)隊列”或“環(huán)形隊列”。

二、循環(huán)隊列

采用了這種頭尾相接的循環(huán)隊列后，入隊的隊尾指針加1操作及出隊的隊頭指針加1操作必須做相應(yīng)的修改，以確保下標(biāo)范圍為0~Max_Size-1。對指針進(jìn)行取模運算，就能使指針到達(dá)最大下標(biāo)位置后回到0，符合“循環(huán)”隊列的特點。

因此入隊時隊尾指針加1操作改為： pQueue->tail = (pQueue->tail+1) % MAX_SIZE;

入隊時隊尾指針加1操作改為： pQueue->head = (pQueue->head+1) % MAX_SIZE。

1.結(jié)構(gòu)

/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef struct
{
   QElemType data[MAXSIZE];
   int front;        /* 頭指針 */
   int rear;        /* 尾指針，若隊列不空，指向隊列尾元素的下一個位置 */
}SqQueue

2.初始化

int InitSqQueue(SqQueue *Q){
   Q->front = 0;
   Q->rear = 0;
   return 1;
}

3.清空

int ClearSqQueue(SqQueue *Q){
   
   Q->front = Q->rear = 0;
   return 1;
}

4.是否為空

int IsSqQueueEmpty(SqQueue Q){
   //隊空標(biāo)記
   if (Q.front == Q.rear)
       return 1;
   else
       return 0;
}

5.獲取隊列長度

(Q.rear - Q.front + MAXSIZE)%MAXSIZE;

6.獲取隊列頭元素

int GetSqQueueHead(SqQueue Q,QElemType *e){
   if (Q.front == Q.rear)
       return 0;
       *e = Q.data[Q.front];
   return 1;
}

7.插入元素

int EnterSqQueue(SqQueue *Q,QElemType e){
       if((Q->rear+1)%MAXSIZE == Q->front)
       return 0;
       Q->data[Q->rear] = e;
       Q->rear = (Q->rear+1)%MAXSIZE;
   return 1;
}

8.刪除元素

int DeleteSqQueue(SqQueue *Q,QElemType *e){
      if (Q->front == Q->rear) {
       return 0;
   }
   *e = Q->data[Q->front];
   Q->front = (Q->front+1)%MAXSIZE;
       return 1;
}

9.遍歷隊列

int ReadSqQueue(SqQueue Q){
   int I;
   i = Q.front;
   while (i != Q.rear) {
       printf("%d   ",Q.data[i]);
       i = (i+1)%MAXSIZE;
   }
   printf("\n");
   return 1;
}

三、鏈?zhǔn)疥犃?/h1>

隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其實就是線性表的單鏈表，只不過它只能尾進(jìn)頭出而已，我們把它簡稱為鏈隊列。

為了操作上的方便，我們將隊頭指針指向鏈隊列的頭結(jié)點，而隊尾指針指向終端結(jié)點。鏈隊列示意圖：

鏈隊列.jpeg

當(dāng)隊列為空時，front和rear都指向頭結(jié)點。

隊列為空.jpeg

1.結(jié)構(gòu)

/* 循環(huán)隊列的順序存儲結(jié)構(gòu) */
typedef int Status;

typedef int QElemType; /* QElemType類型根據(jù)實際情況而定，這里假設(shè)為int */

typedef struct QNode    /* 結(jié)點結(jié)構(gòu) */
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct            /* 隊列的鏈表結(jié)構(gòu) */
{
   QueuePtr front,rear; /* 隊頭、隊尾指針 */
}LinkQueue;

2.初始化

int InitLinkQueue(LinkQueue *Q){
       Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
   if (!Q->front) {
       return 0;
   }
   Q->front->next = NULL;
   return 1;
}

3. 銷毀隊列

int DestoryLinkQueue(LinkQueue *Q){
       while (Q->front) {
       Q->rear = Q->front->next;
       free(Q->front);
       Q->front = Q->rear;
   }
   return 1;   
}

4.置空

int ClearLinkQueue(LinkQueue *Q){
   QueuePtr p,q;
   Q->rear = Q->front;
   p = Q->front->next;
   Q->front->next = NULL;
   while (p) {
       q = p;
       p = p->next;
       free(q);  
   }
   return 1;
}

5.是否為空

int IsLinkQueueEmpty(LinkQueue Q){
   if (Q.front == Q.rear)
       return 1;
   else
       return 0;
}

6.獲取隊列長度

int LinkQueueLength(LinkQueue Q){
   int i= 0;
   QueuePtr p;
   p = Q.front;
   while (Q.rear != p) {
       i++;
       p = p->next;
   }
   return i;
}

7.獲取隊列頭元素

int GetLinkQueueHead(LinkQueue Q,QElemType *e){
   if (Q.front != Q.rear) {
       *e =  Q.front->next->data;
       return 1;
   }
   return  0;
}

8.插入元素

int EnterLinkQueue(LinkQueue *Q,QElemType e){
   QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
   if (!s) {
        return 0;
   }
   s->data = e;
   s->next = NULL;
   Q->rear->next = s;
   Q->rear = s;
   return 1;
}

9.刪除元素

int DeleteLinkQueue(LinkQueue *Q,QElemType *e){
   QueuePtr p;
   if (Q->front == Q->rear) {
       return 0;
   }
   p = Q->front->next;
   *e = p->data;
   Q->front->next = p ->next;
   if(Q->rear == p) Q->rear = Q->front;
   free(p);
   return 1;
}

10.遍歷隊列

int ReadLinkQueue(LinkQueue Q){
   QueuePtr p;
   p = Q.front->next;
   while (p) {
       p = p->next;
   }
   return 1;
}