代碼參考《妙趣橫生的算法.C語言實現》

---

前言

本章總結：鏈隊列定義，創建，出隊入隊操作，銷毀操作；循環隊列的定義以及循環隊列的一些基本操作

---

1、隊列定義

隊列是一種先進先出的線性表(FIFO),它要求所有的數據從隊列的一端進入，從隊列的另一端離開。
在隊列中，允許插入數據的一端角隊尾，允許數據離開的一端叫做隊頭。

隊列是一個線性表，既可以是一個順序表也可以是一個鏈表。這里重點介紹用鏈表實現一個隊列。

typedef char ElemType ;
//隊列元素類，隊列中的每個元素都是QNode類
typedef struct QNode{ElemType data;			//隊列結點的數據域struct QNode* next;		//隊列結點的指針域
}QNode, *QueuePtr;typedef struct {QueuePtr front;			//隊頭指針，用來存放隊頭元素的地址QueuePtr rear;			//隊尾指針，用來存放隊尾元素的地址
}LinkQueue;
//這里定義得隊列是一個鏈隊列，隊列之間的元素由指針相連，所以只要掌握了隊列的隊頭指針和隊尾指針，就可以對隊列進行各種

2、創建一個隊列

創建一個隊列要完成兩步：
1、在內存中創建一個頭結點，但該頭結點不是用來存放數據的，而是為了操作方便人為添加的。
2、將隊列的頭指針和尾指針都指向這個生成的頭結點，此時隊列中沒有任何隊列元素，該隊列為空隊列。
這樣判斷隊列為空的條件就是頭指針front和尾指針rear都同時指向頭結點。

//創建一個空隊列
void InitQueue(LinkQueue* q)
{q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));		//初始化一個隊列指針大小的空間，并將地址傳給頭指針和尾指針if (!q->front){printf("內存分配失敗");exit(0);}q->front->next = NULL;		//頭結點指針域指向空
}

此時空隊列的狀態如下：

3、入隊列

入隊列就是講一個QNode類型的結點從隊列尾部進入隊列。
每當一個隊列元素插入隊列，隊列的尾指針都要進行修改。
隊頭的指針不改變。

//入隊列
void EnQueue(LinkQueue* q,ElemType elem)
{QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));		//創建一個隊列元素結點，并將地址傳給指針pif (p == NULL){printf("分配內存失敗");exit(0);}p->data = elem;			//將數據elem放到隊列結點data域中p->next = NULL;q->rear->next = p;		//從隊尾插入元素q->rear = p;			//修改隊尾指針，注意，此時隊尾指針指向空(q->rear->next = p->next =NULL)
}

入隊列操作流程：

4、出隊列

出隊列操作就是將隊列中的元素從隊列的頭部移除。每次從隊列中一出數據時，隊頭指針front不改變，但是頭結點的next指針要發生改變。隊尾指針rear只有在(隊頭即隊尾)的情況下才會改變，否則也不改變。

//出隊列
void DeQueue(LinkQueue* q, ElemType *elem)
{QueuePtr p;//如果隊列不為空，刪除q的隊頭元素，用e返回其值if (q->front == q->rear) return;		//隊列為空，返回p = q->front->next;				//p指向隊列的第一個元素*elem = p->data;				//將隊首元素數據傳給eq->front->next = p->next;		//刪除當前頭結點if (q->rear == p) q->rear = q->front;		//如果此時隊列為空，則修改隊尾指針free(p);						//將原本隊頭結點銷毀
}

效果如下：
1、當隊伍中存在超過1個元素

2、當隊伍中只有一個元素時

5、銷毀一個隊列

由于隊列建立在內存動態區(堆內存)，因此當一個隊列不再有用時，應當把它及時銷毀掉，以免占用內存空間得不到釋放導致內存泄漏。
釋放一塊內存要做兩點：1.釋放指向它的指針。2.將該指針指向空

void DestroyQueue(LinkQueue* q)
{while (q->front)			//如果隊列頭指針還存在{q->rear = q->front->next;	//q->rear指向q->front的后繼結點free(q->front);				//釋放q->front,此時q->rear應該指向NULLq->front = q->rear;}
}

6、循環隊列的概念

用順序表實現的隊列稱為循環隊列，此隊列的空間是可以循環使用的。

循環隊列一般來說有固定的容量。

如果不斷地有元素入隊列，同時又不斷地有元素出隊列，那么對于一般的鏈隊列，只要隊列不為空，頭指針front和尾指針rear都不會改變，只有頭指針的next指針和尾指針的前一個結點的next指針會發生變化，而且鏈隊列的長度也會隨著入出度列元素而不斷變化。

循環隊列，容量固定，隊頭指針和隊尾指針都可以隨著元素的入出隊列而發生改變，這樣循環隊列邏輯上就是一個環形的存儲空間，只要隊列中有空單元未使用，就可以向隊列中存放元素

所以循環隊列可以作為緩沖池存儲結構來存放數據。

該隊列總容量為8B，實際長度為5B。這里規定循環隊列頭指針front始終指向隊頭元素，尾指針rear始終指向隊尾元素的下一個空間。
這里隊頭元素:f,隊尾元素:b，該隊列實際可用空間為7B。

將隊首元素f出隊列，在隊尾加入元素a，形成上面隊列。

所以，入隊列操作就是想rear指向的空間賦值，rear再指向隊尾元素的下一個空間。

出隊列就是將隊頭指針front向上移一個單元。整個循環隊列邏輯上就是一個首尾相接的環形緩沖區。

7、循環隊列的實現

現實中只有線性的存儲單元，不存在環形存儲單元。

只需要注意rear不斷加1后超過循環隊列的地址范圍，采用取模運算處理的結果。

因此，無論是入隊列的rear+1操作還是出隊列的front+1操作，實際都是模加運算，即

(rear+1)%len 和(front+1)%len

/*****************************循環隊列******************************************/
//定義一個循環隊列
#define MAXQSIZE 100
typedef struct {ElemType* base;			//循環隊列內存分配基地址int front;				//隊頭int rear;				//隊尾
}cycleQueue;				//循環隊列類cycleQueue//初始化一個循環隊列
void InitcycleQueue(cycleQueue *q)
{q->base = (ElemType*)malloc(MAXQSIZE*sizeof(ElemType));//開辟MAXQSIZE個單元的順序表作為循環隊列的存儲空間if (!q->base){printf("循環隊列分配內存失敗");exit(0);}q->front = q->rear = 0;		//空隊列，front和rear都指向0號單元}
//入隊列操作
void EncycleQueue(cycleQueue* q, ElemType elem)
{if ((q->rear + 1) % MAXQSIZE == q->front)	return;	//循環隊列已滿q->base[q->rear] = elem;		//將元素elem入隊列，q->base為順序表的額首地址q->rear = (q->rear + 1) % MAXQSIZE;		//隊尾指針+1，注意這里的全部都是模加運算
}
//出隊列操作
void DecycleQueue(cycleQueue* q, ElemType* elem)
{if (q->front == q->rear)	return;				//循環隊列為空*elem = q->base[q->front];						//取出隊頭元素q->front = (q->front + 1) % MAXQSIZE;			//隊頭指針+1
}

8、實例分析

實現一個鏈隊列，任意輸入一串字符，以@為結束標志，然后將隊列中的元素逐一取出，打印出來

#include "stdio.h"
#include "malloc.h"
#include "conio.h"
#include <stdlib.h>
#include <math.h>
typedef char ElemType ;
/*****************************鏈隊列******************************************/
//隊列元素類，隊列中的每個元素都是QNode類
typedef struct QNode{ElemType data;			//隊列結點的數據域struct QNode* next;		//隊列結點的指針域
}QNode, *QueuePtr;typedef struct {QueuePtr front;			//隊頭指針，用來存放隊頭元素的地址QueuePtr rear;			//隊尾指針，用來存放隊尾元素的地址
}LinkQueue;
//這里定義得隊列是一個鏈隊列，隊列之間的元素由指針相連，所以只要掌握了隊列的隊頭指針和隊尾指針，就可以對隊列進行各種操作。、//創建一個空隊列
void InitQueue(LinkQueue* q)
{q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));		//初始化一個隊列指針大小的空間，并將地址傳給頭指針和尾指針if (!q->front){printf("內存分配失敗");exit(0);}q->front->next = NULL;		//頭結點指針域指向空
}
//入隊列
void EnQueue(LinkQueue* q,ElemType elem)
{QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));		//創建一個隊列元素結點，并將地址傳給指針pif (p == NULL){printf("分配內存失敗");exit(0);}p->data = elem;			//將數據elem放到隊列結點data域中p->next = NULL;q->rear->next = p;		//從隊尾插入元素q->rear = p;			//修改隊尾指針，注意，此時隊尾指針指向空(q->rear->next = p->next =NULL)
}
//出隊列
void DeQueue(LinkQueue* q, ElemType *elem)
{QueuePtr p;//如果隊列不為空，刪除q的隊頭元素，用e返回其值if (q->front == q->rear) return;		//隊列為空，返回p = q->front->next;				//p指向隊列的第一個元素*elem = p->data;				//將隊首元素數據傳給eq->front->next = p->next;		//刪除當前頭結點if (q->rear == p) q->rear = q->front;		//如果此時隊列為空，則修改隊尾指針free(p);						//將原本隊頭結點銷毀
}//銷毀一個隊列
//釋放一塊內存要做兩點：1.釋放指向它的指針。2.將該指針指向空
void DestroyQueue(LinkQueue* q)
{while (q->front)			//如果隊列頭指針還存在{q->rear = q->front->next;	//q->rear指向q->front的后繼結點free(q->front);				//釋放q->front,此時q->rear應該指向NULLq->front = q->rear;}
}/*****************************循環隊列******************************************/
//定義一個循環隊列
#define MAXQSIZE 100
typedef struct {ElemType* base;			//循環隊列內存分配基地址int front;				//隊頭int rear;				//隊尾
}cycleQueue;				//循環隊列類cycleQueue//初始化一個循環隊列
void InitcycleQueue(cycleQueue *q)
{q->base = (ElemType*)malloc(MAXQSIZE*sizeof(ElemType));//開辟MAXQSIZE個單元的順序表作為循環隊列的存儲空間if (!q->base){printf("循環隊列分配內存失敗");exit(0);}q->front = q->rear = 0;		//空隊列，front和rear都指向0號單元}
//入隊列操作
void EncycleQueue(cycleQueue* q, ElemType elem)
{if ((q->rear + 1) % MAXQSIZE == q->front)	return;	//循環隊列已滿q->base[q->rear] = elem;		//將元素elem入隊列，q->base為順序表的額首地址q->rear = (q->rear + 1) % MAXQSIZE;		//隊尾指針+1，注意這里的全部都是模加運算
}
//出隊列操作
void DecycleQueue(cycleQueue* q, ElemType* elem)
{if (q->front == q->rear)	return;				//循環隊列為空*elem = q->base[q->front];						//取出隊頭元素q->front = (q->front + 1) % MAXQSIZE;			//隊頭指針+1
}//測試函數
int main()
{ElemType e;LinkQueue q;InitQueue(&q);		//初始化一個隊列qprintf("請輸入一串字符到隊列中\n");scanf("%c",&e);while (e != '@'){EnQueue(&q,e);scanf("%c", &e);}printf("隊列為：\n");while (q.front != q.rear){DeQueue(&q, &e);printf("%c",e);}printf("\n");DestroyQueue(&q);		//銷毀隊列q_getche();return 0;
}

效果：