本文轉自 https://blog.csdn.net/lym152898/article/details/52202606 ### 隊列的基本概念 隊列 (Queue) :也是運算受限的線性表。是一種先進先出 (First In First Out ,簡稱 FIFO) 的線性表。只允許在表的一端進行插入,而在另一端進行刪除。 隊首 (front) :允許進行刪除的一端稱為隊首。 隊尾 (rear) :允許進行插入的一端稱為隊尾。 隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素 a 1 , a 2 , …, a n 之后, a 1 是隊首元素, a n 是隊尾元素。顯然退出隊列的次序也只能是 a 1 , a 2 , …, a n ,即隊列的修改是依先進先出的原則進行的下圖所示。  ### 隊列的基本操作 1. 創建新隊列 2. 判空 3. 進隊 4. 出隊 5. 清空隊 6. 獲得隊頭元素 7. 遍歷隊 8. 銷毀隊 9. 隊長 ### 順序隊列 利用一組連續的存儲單元 ( 一維數組 ) 依次存放從隊首到隊尾的各個元素,稱為順序隊列。對于隊列,和順序棧相類似,也有動態和靜態之分。 這里介紹靜態順序隊列.其類型定義如下: typedef int datatype; #define MAX_QUEUE_SIZE 100 typedef struct queue { datatype queue_array[MAX_QUEUE_SIZE]; int front; int rear; }sp_queue; 設立一個隊首指針 front ,一個隊尾指針rear ,分別指向隊首和隊尾元素。 * 初始化: front=rear =0。 * 入隊:將新元素插入 rear 所指的位置,然后rear 加 1 。 * 出隊:刪去 front 所指的元素,然后加 1 并返回被刪元素。 * 隊列為空: front=rear 。 * 隊滿: rear = MAX_QUEUE_SIZE - 1 或front=rear 。 在非空隊列里,隊首指針始終指向隊頭元素,而隊尾指針始終指向隊尾元素的下一位置。順序隊列中存在“假溢出”現象。因為在入隊和出隊操作中,頭、尾指針只增加不減小,致使被刪除元素的空間永遠無法重新利用。因此,盡管隊列中實際元素個數可能遠遠小于數組大小,但可能由于尾指針巳超出向量空間的上界而不能做入隊操作。該現象稱為假溢出。如圖 3-6 所示是數組大小為 5 的順序隊列中隊首、隊尾指針和隊列中元素的變化情況。  ### 代碼實現 /* 順序隊列接口定義頭文件*/ #define true 1 #define false 0 /* 隊的最大長度 */ #define MAX_QUEUE_SIZE 100 /* 隊列的數據類型 */ typedef int datatype; /* 靜態鏈的數據結構 */ typedef struct queue{ datatype sp_queue_array[MAX_QUEUE_SIZE]; /* 隊頭 */ int front; /* 隊尾 */ int rear; }sp_queue; /* 靜態順序鏈的接口定義 */ /* 靜態鏈的初始化 */ sp_queue queue_init(); /* 判斷隊列是否為空,若為空 * 返回true * 否則返回false */ int queue_empty(sp_queue q); /* 插入元素e為隊q的隊尾新元素 * 插入成功返回true * 隊滿返回false */ int queue_en(sp_queue *q, datatype e); /* 隊頭元素出隊 * 用e返回出隊元素,并返回true * 若隊空返回false */ int queue_de(sp_queue *q, datatype *e); /* 清空隊 */ void queue_clear(sp_queue *q); /* 獲得隊頭元素 * 隊列非空,用e返回隊頭元素,并返回true * 否則返回false */ int get_front(sp_queue, datatype *e ); /* 獲得隊長 */ int queue_len(sp_queue q); /* 遍歷隊 */ void queue_traverse(sp_queue q, void(*visit)(sp_queue q)); void visit(sp_queue s); /* 接口實現文件 */ #include<stdio.h> #include<stdlib.h> #include"sp_queue.h" sp_queue queue_init() { sp_queue q; q.front = q.rear = 0; return q; } int queue_empty(sp_queue q) { return q.front == q.rear; } int queue_en(sp_queue *q, datatype e) { /* 隊滿 */ if (q -> rear == MAX_QUEUE_SIZE) return false; /* 入隊 */ q -> sp_queue_array[q -> rear] = e; printf("q.sp_queue_array[%d]=%d\n", q -> rear, e); q -> rear += 1; return true; } int queue_de(sp_queue *q, datatype *e) { /* 隊空 */ if(queue_empty(*q)) return false; /* 出隊 */ q -> rear -= 1; *e = q -> sp_queue_array[q -> rear]; return true; } void queue_clear(sp_queue *q) { q -> front = q -> rear = 0; } int get_front(sp_queue q, datatype *e) { /* 隊空 */ if(q.front == q.rear) return false; /* 獲取隊頭元素 */ *e = q.sp_queue_array[q.front]; return true; } int queue_len(sp_queue q) { return (q.rear - q.front); } void queue_traverse(sp_queue q, void (*visit)(sp_queue q)) { visit(q); } void visit(sp_queue q) { /* 隊空 */ if (q.front == q.rear) printf("隊列為空\n"); int temp = q.front; while(temp != q.rear) { printf("%d ",q.sp_queue_array[temp]); temp += 1; } printf("\n"); } int main() { sp_queue q = queue_init(); queue_en(&q, 1); queue_en(&q, 2); printf("length=%d\n", queue_len(q)); queue_en(&q, 3); printf("length=%d\n", queue_len(q)); queue_en(&q, 4); printf("length=%d\n", queue_len(q)); queue_en(&q, 5); printf("length=%d\n", queue_len(q)); queue_en(&q, 6); printf("length=%d\n", queue_len(q)); queue_traverse(q,visit); datatype *e = (datatype *)malloc(sizeof(*e)); queue_de(&q,e); printf("queue_de(),e=%d length=%d\n", *e, queue_len(q)); queue_traverse(q, visit); queue_clear(&q); queue_traverse(q, visit); printf("length:%d\n", queue_len(q)); } 注意:結構體變量作為函數的參數和其他普通變量一樣,值只會在函數體內被修改,想要通過函數更改結構體的值,可以通過結構體指針作為函數的參數實現. ### 隊列的鏈式表示和實現 隊列的鏈式存儲結構簡稱為鏈隊列,它是限制僅在表頭進行刪除操作和表尾進行插入操作的單鏈表。需要兩類不同的結點:數據元素結點,隊列的隊 首指針和隊尾指針的結點,如圖 3-8 所示。  數據元素結點類型定義: typedef struct q_node{ datatype data; struct q_node *next; }q_node; 指針結點類型: typedef struct { q_node *front; q_node *rear; }link_queue; ### 鏈隊運算及指針變化 鏈隊的操作實際上是單鏈表的操作,只不過是刪除 在表頭進行,插入在表尾進行。插入、刪除時分別修改 不同的指針。鏈隊運算及指針變化如圖 3-9 所示。  ### 代碼實現 /* 鏈式棧接口的定義頭文件 */ #define true 1 #define false 0 /* 隊列的數據類型 */ typedef int datatype; /* 靜態鏈的數據結構 */ typedef struct q_node{ datatype data; struct q_node *next; }q_node,*link_node; typedef struct l_queue{ /* 隊頭指針 */ q_node *front; /* 隊尾指針 */ q_node *rear; }*link_queue; /* 靜態順序鏈的接口定義 */ /* 靜態鏈的初始化 */ link_queue queue_init(); /* 判斷隊列是否為空,若為空 * 返回true * 否則返回false */ int queue_empty(link_queue q); /* 插入元素e為隊q的隊尾新元素 * 插入成功返回true * 隊滿返回false */ int queue_en(link_queue q, datatype e); /* 隊頭元素出隊 * 用e返回出隊元素,并返回true * 若隊空返回false */ int queue_de(link_queue q, datatype *e); /* 清空隊 */ void queue_clear(link_queue q); /* 銷毀隊 */ void queue_destroy(link_queue q); /* 獲得隊頭元素 * 隊列非空,用e返回隊頭元素,并返回true * 否則返回false */ int get_front(link_queue q, datatype *e ); /* 獲得隊長 */ int queue_len(link_queue q); /* 遍歷隊 */ void queue_traverse(link_queue q, void(*visit)(link_queue q)); void visit(link_queue q); /* 接口的實現文件 */ #include<stdio.h> #include<stdlib.h> #include"lp_queue.h" link_queue queue_init() { /* 新建頭結點 */ link_node new_node = (link_node)malloc(sizeof(q_node)); new_node -> next = NULL; /* 指針結點 */ link_queue q = (link_queue)malloc(sizeof(*q)); q -> front = q -> rear = new_node; return q; } int queue_empty(link_queue q) { return q -> front == q -> rear; } int queue_en(link_queue q, datatype e) { /* 新建數據結點 */ link_node new_node = (link_node)malloc(sizeof(q_node)); /* 內存分配失敗 */ if(!new_node) return false; new_node -> data = e; q -> rear -> next = new_node; q -> rear = new_node; return true; } int queue_de(link_queue q, datatype *e) { /* 隊列為空 */ if (q -> front == q -> rear) return false; *e = q -> front -> next -> data; link_node temp = q -> front -> next; q -> front -> next = temp -> next; /* 防止丟失尾指針 */ if (temp == q.rear -> next) q -> rear = q -> front; free(temp); temp = NULL; return true; } void queue_clear(link_queue q) { /* 頭結點 */ link_node head = q -> front -> next; head -> next = NULL; q -> front = q -> rear = head; /* 第一個結點 */ link_node temp = head -> next; while(temp) { link_node p = temp; temp = p -> next; free(p); p = NULL; } } void queue_destroy(link_queue q) { queue_clear(q); free(q); q = NULL; } int get_front(link_queue q, datatype *e) { /* 隊為空 */ if (q -> front == q -> rear) return false; *e = q -> front -> next -> data; link_node temp = q -> front -> next; q -> front -> next = temp -> next; free(temp); temp = NULL; return true; } int queue_len(link_queue q) { /* 頭結點 */ link_node p = q -> front -> next; /* 計數器 */ int count = 0; while(p) { count += 1; p = p -> next; } return count; } void queue_traverse(link_queue q, void(*visit)(link_queue q)) { visit(q); } void visit(link_queue q) { /* 頭結點 */ link_node p = q -> front -> next; if(!p) { printf("隊列為空"); } while(p) { printf("%d ", p -> data); p = p -> next; } printf("\n"); } int main() { link_queue q = queue_init(); queue_en(q, 1); queue_en(q, 2); printf("length=%d\n", queue_len(q)); queue_en(q, 3); printf("length=%d\n", queue_len(q)); queue_en(q, 4); printf("length=%d\n", queue_len(q)); queue_en(q, 5); printf("length=%d\n", queue_len(q)); queue_en(q, 6); printf("length=%d\n", queue_len(q)); queue_traverse(q,visit); datatype *e = (datatype *)malloc(sizeof(*e)); queue_de(q,e); printf("queue_de(),e=%d length=%d\n", *e, queue_len(q)); queue_traverse(q, visit); queue_clear(q); queue_traverse(q, visit); printf("length:%d\n", queue_len(q)); } 執行結果: