数据结构（C语言版）之队列
目錄
前言●數(shù)據(jù)結(jié)構(gòu)作為計算機專業(yè)基礎(chǔ)課，綜合性強，抽象性高，在一定程度上增加了學(xué)習(xí)難度，本次我們共同從數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)探討，由淺入深進行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。?●本文只淺顯的探討了隊列的基本知識，作者相信隨著學(xué)習(xí)課程的深入，我們將會對數(shù)據(jù)結(jié)構(gòu)有更深的理解與收獲！
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教！————————————————? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????????????????????????????????????????????????????——By?作者：新曉-故知
正文————————————————
一、隊列
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ??? ? ? ?——By?作者：新曉-故知?整理
1. 隊列的抽象數(shù)據(jù)類型：
隊列的抽象數(shù)據(jù)類型：
Data：?
?Operations:
隊列的抽象數(shù)據(jù)類型:
ADT Queue {
數(shù)據(jù)對象:?? ???
數(shù)據(jù)關(guān)系:? ? ??
基本操作:
隊列的順序表示－－用一維數(shù)組base[M]
?front=0 rear=M時：
解決的方法－－循環(huán)隊列：
??? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新曉-故知?整理
2. 循環(huán)隊列:?
?循環(huán)隊列初始化:
?求循環(huán)隊列的長度:
??循環(huán)隊列入隊:
??循環(huán)隊列出隊：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? q???????????????????????——By?作者：新曉-故知?整理+創(chuàng)作
3.隊列的順序存儲及實現(xiàn)：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新曉-故知?整理+創(chuàng)作
?隊列操作中的Rear和Front
????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????——By?作者：新曉-故知?整理+創(chuàng)作
隊列及操作的實現(xiàn)
? 算法時間復(fù)雜度分析： 各種操作的時間復(fù)雜度都為O(1)。
4.鏈?zhǔn)疥犃?#xff1a;
?(a) 空隊列
?(b) 元素x入隊列
(c) 元素y入隊列
(d) 元素x出隊列
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新曉-故知? 整理+創(chuàng)作?
?鏈隊列初始化:
?銷毀鏈隊列:
?判斷鏈隊列是否為空:
?求鏈隊列的隊頭元素:
??鏈隊列入隊:
?????????????????????????????????????????????????????? ? ? ? ? ? ? ????——By?作者：新曉-故知?整理+創(chuàng)作
?鏈隊列出隊：
用鏈表存儲隊列中的元素。其中隊首指針 Front指向隊首結(jié)點，隊尾指針Rear指向隊尾結(jié)點。
??
5.優(yōu)先隊列
????????????????????????????????????????????????????????????? ? ? ??? ?——By?作者：新曉-故知?整理+創(chuàng)作
優(yōu)先隊列有多種實現(xiàn)方式：
????????????????????????????????????????????????????????????????????????——By?作者：新曉-故知?整理+創(chuàng)作
?算法時間復(fù)雜度分析：進隊O(1), 出隊O(n)。
6.另一種策略：
6.1?順序循環(huán)隊列：
?6.2?鏈?zhǔn)酱鎯?yōu)先隊列:
?總結(jié)：
本文共同探討了隊列的相關(guān)內(nèi)容，在日常生活中有極其豐富的應(yīng)用，作者認(rèn)為要認(rèn)真對待數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，搭建基本知識框架，隨著日積月累的學(xué)習(xí)逐漸填補總結(jié)，從腳踏實地做起，祝愿大家能夠熟悉掌握這門課程，并將其能夠熟悉的應(yīng)用！
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?——By?作者：新曉-故知??
前言
●數(shù)據(jù)結(jié)構(gòu)作為計算機專業(yè)基礎(chǔ)課，綜合性強，抽象性高，在一定程度上增加了學(xué)習(xí)難度，本次我們共同從數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)探討，由淺入深進行數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)。?
●本文只淺顯的探討了隊列的基本知識，作者相信隨著學(xué)習(xí)課程的深入，我們將會對數(shù)據(jù)結(jié)構(gòu)有更深的理解與收獲！
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教！
————————————————
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????????????????????????????????????????????????????????????——By?作者：新曉-故知
正文
————————————————
一、隊列
?隊列是另外一種常用的線性結(jié)構(gòu)，到達這種結(jié)構(gòu)的元素越早，離開該結(jié)構(gòu)的時間也越早，所以隊列通常被稱為先進先出(FIFO: First In First Out)隊列。
1.隊列可以看作是插入刪除位置操作受限的線性表，它的插入和刪除分別在表的兩端進行。
2.隊列的刪除操作只能在隊首(front)進行而插入操作只能在隊尾(rear)進行，從而保證了隊列的先進先出特點。
3.元素從隊首刪除的操作，稱之為出隊（deQueue）。
4.元素在隊尾位置插入的操作，稱為進隊（enQueue）。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ??? ? ? ?——By?作者：新曉-故知?整理
?
?
1. 隊列的抽象數(shù)據(jù)類型：
隊列的抽象數(shù)據(jù)類型：
Data：?
?Operations:
隊列的抽象數(shù)據(jù)類型:
ADT Queue {
數(shù)據(jù)對象:?? ??
數(shù)據(jù)關(guān)系:? ? ?
基本操作:
{ (1) InitQueue (&Q) 構(gòu)造空隊列(2) DestroyQueue (&Q) 銷毀隊列(3) ClearQueue (&S) 清空隊列(4) QueueEmpty(S) 判空. 空--TRUE,(5) QueueLength(Q) 取隊列長度(6) GetHead (Q,&e) 隊頭元素,(7) EnQueue (&Q,e) 入隊列(8) DeQueue (&Q,&e) 出隊列(9) QueueTraverse(Q,visit()) 遍歷 }ADT Queue隊列的順序表示－－用一維數(shù)組base[M]
#define M 100 最大隊列長度 Typedef struct {QElemType *base; 初始化的動態(tài)分配存儲空間int front; 頭指針 int rear; 尾指針 }SqQueue;??
?
?front=0 rear=M時：
front=0 rear=M 時 再入隊——真溢出front≠0 rear=M 時 再入隊——假溢出解決的方法－－循環(huán)隊列：
?
base[0]接在base[M-1]之后 若rear+1==M 則令rear=0;實現(xiàn)：利用“模”運算 入隊：base[rear]=x;rear=(rear+1)%M; 出隊：x=base[front];front=(front+1)%M;?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新曉-故知?整理
2. 循環(huán)隊列:?
#define MAXQSIZE 100 最大隊列長度 Typedef struct {QElemType *base; 初始化的動態(tài)分配存儲空間int front; 頭指針 int rear; 尾指針 }SqQueue;?循環(huán)隊列初始化:
Status InitQueue (SqQueue &Q) {Q.base =new QElemType[MAXQSIZE] if(!Q.base) exit(OVERFLOW);Q.front=Q.rear=0;return OK; }?求循環(huán)隊列的長度:
int QueueLength (SqQueue Q) {return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }??循環(huán)隊列入隊:
Status EnQueue(SqQueue &Q,QElemType e) {if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK; }??循環(huán)隊列出隊：
Status DeQueue (LinkQueue &Q,QElemType &e) {if(Q.front==Q.rear) return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK; }? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? q???????????????????????——By?作者：新曉-故知?整理+創(chuàng)作
3.隊列的順序存儲及實現(xiàn)：
a.隊列的順序存儲，用一組連續(xù)的空間存儲隊列中的元素及元素間關(guān)系。
b.可以使用隊首指針Front和隊尾指針Rear分別指示隊首元素和隊尾元素存放的下標(biāo)地址。
c.讓Front指向真正的隊首元素，而Rear指向真正存放隊尾元素的后一數(shù)組單元。這樣隊空的標(biāo)志Front=Rear。
d.為了防止大批數(shù)據(jù)移動，當(dāng)Rear=maxSize時，如果下標(biāo)為0的空間未用，讓它轉(zhuǎn)回來，即Rear=Rear%MaxSize。形成循環(huán)隊列。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新曉-故知?整理+創(chuàng)作
?隊列操作中的Rear和Front
?隊列操作中的Rear和Front
無論進隊、出隊，Rear和Front都向前移動，移動到右邊界時向左邊循環(huán)。 為了區(qū)別隊空標(biāo)志，當(dāng)隊尾還有一個空間時即告隊滿，浪費了一個空間做代價。
隊列空的標(biāo)志：Rear=Front
隊列滿的標(biāo)志：（Rear+1）%maxSize =Front
?進隊操作后：Rear= （Rear+1）%maxSize?
?出隊操作后：Front= （Front+1）%maxSize?
????????????????????????????????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????——By?作者：新曉-故知?整理+創(chuàng)作
隊列及操作的實現(xiàn)
#include <stdio.h> #include <stdlib.h>typedef int elemType;typedef struct {int Front, Rear;int maxSize;elemType *array; }Queue; void initialize(Queue *que, int size); 初始化隊列元素的存儲空間 int isEmpty(Queue *que); 判斷隊空否，空返回1，否則為0 int isFull(Queue *que); 判斷隊滿否，滿返回1，否則為0 elemType front(Queue *que); 讀取隊首元素的值，隊首不變 void enQueue(Queue *que, elemType x); 將x進隊，成為新的隊尾 void deQueue(Queue *que); 將隊首元素出隊 void doubleSize(Queue *que); 擴展隊隊列元素的存儲空間為原來的2倍 void clear(Queue *que); 將隊列中所有元素清空，為空的隊列 void destroy(Queue *que); 釋放隊列元素所占據(jù)的動態(tài)數(shù)組 void initialize(Queue *que, int size) 初始化隊列元素的存儲空間 { que->maxSize = size;//申請實際的隊列存儲空間que->array = (elemType *)malloc(sizeof(elemType)*size); if (!que->array) exit(1);que->Front = que->Rear = 0; }int isEmpty(Queue *que) 判斷隊空否，空返回1，否則為0 {return que->Front == que->Rear;}int isFull(Queue *que) 判斷隊滿否，滿返回1，否則為0 {return (que->Rear+1)%que->maxSize == que->Front;}elemType front(Queue *que) 讀取隊首元素的值，隊首不變 { if (isEmpty(que)) exit(1);return que->array[que->Front]; }void enQueue(Queue *que, elemType x) 將x進隊，成為新的隊尾 { if (isFull(que)) doubleSize(que);que->array[que->Rear]=x;que->Rear = (que->Rear+1)%que->maxSize; }void deQueue(Queue *que) 將隊首元素出隊 { if (isEmpty(que)) exit(1);que->Front = (que->Front+1)%que->maxSize; }void clear(Queue *que) //將隊列中所有元素清空，為空的隊列 { que->Front = que->Rear = 0;}void destroy(Queue *que) 釋放隊列元素所占據(jù)的動態(tài)數(shù)組 { free(que->array);}——By?作者：新曉-故知?整理+創(chuàng)作? 算法時間復(fù)雜度分析： 各種操作的時間復(fù)雜度都為O(1)。
4.鏈?zhǔn)疥犃?#xff1a;
typedef struct QNode{QElemType data;struct Qnode *next; }Qnode, *QueuePtr; typedef struct {QueuePtr front; 隊頭指針 QueuePtr rear; 隊尾指針 }LinkQueue;?(a) 空隊列
?(b) 元素x入隊列
(c) 元素y入隊列
(d) 元素x出隊列
??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?——By?作者：新曉-故知? 整理+創(chuàng)作?
?鏈隊列初始化:
Status InitQueue (LinkQueue &Q) {Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW);Q.front->next=NULL;return OK; }?銷毀鏈隊列:
Status DestroyQueue (LinkQueue &Q) {while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear; } return OK; }?判斷鏈隊列是否為空:
Status QueueEmpty (LinkQueue Q) {return (Q.front==Q.rear); }?求鏈隊列的隊頭元素:
Status GetHead (LinkQueue Q, QElemType &e) {if(Q.front==Q.rear) return ERROR;e=Q.front->next->data;return OK; }??鏈隊列入隊:
Status EnQueue(LinkQueue &Q,QElemType e) {p=(QueuePtr)malloc(sizeof(QNode));if(!p) exit(OVERFLOW);p->data=e; p->next=NULL;Q.rear->next=p;Q.rear=p;return OK; }?????????????????????????????????????????????????????? ? ? ? ? ? ? ????——By?作者：新曉-故知?整理+創(chuàng)作
?鏈隊列出隊：
Status DeQueue (LinkQueue &Q,QElemType &e) {if(Q.front==Q.rear) return ERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;free(p);return OK; }用鏈表存儲隊列中的元素。其中隊首指針 Front指向隊首結(jié)點，隊尾指針Rear指向隊尾結(jié)點。
?
typedef int elemType; typedef struct {elemType data;struct Node *next; } Node; typedef struct {Node *Front,*Rear; }linkQueue; void initialize(linkQueue *que); 初始化為一個空隊int isEmpty(linkQueue *que); 判斷隊空否，空返回1，否則為0int isFull(linkQueue *que); 判斷隊滿否，滿返回1，否則為0elemType front(linkQueue *que); 讀取隊首元素的值，隊首不變void enQueue(linkQueue *que, elemType x); 將x進隊，成為新的隊尾void deQueue(linkQueue *que); 將隊首元素出隊void clear(linkQueue *que); 將隊列中所有元素清空，為空的隊列void destroy(linkQueue *que); 釋放隊列元素所占據(jù)的動態(tài)空間void initialize(linkQueue *que) 初始化為一個空隊 { que->Front = que->Rear = NULL; }void initialize(linkQueue *que); 初始化為一個空隊int isEmpty(linkQueue *que); 判斷隊空否，空返回1，否則為0int isFull(linkQueue *que); 判斷隊滿否，滿返回1，否則為0elemType front(linkQueue *que); 讀取隊首元素的值，隊首不變void enQueue(linkQueue *que, elemType x); 將x進隊，成為新的隊尾void deQueue(linkQueue *que); 將隊首元素出隊void clear(linkQueue *que); 將隊列中所有元素清空，為空的隊列void destroy(linkQueue *que); 釋放隊列元素所占據(jù)的動態(tài)空間void initialize(linkQueue *que) 初始化為一個空隊 { que->Front = que->Rear = NULL; }void enQueue(linkQueue *que, elemType x) 將x進隊，成為新的隊尾 { Node *tmp;tmp = (Node *)malloc(sizeof(Node));tmp->data = x;tmp->next = NULL;if (isEmpty(que)) que->Front = que->Rear = tmp;else{ que->Rear->next = tmp;que->Rear = tmp;} }void deQueue(linkQueue *que) 將隊首元素出隊 { Node *tmp;if (isEmpty(que)) exit(1);tmp = que->Front;que->Front = que->Front->next;free(tmp); }void clear(linkQueue *que) 將隊列中所有元素清空，為空的隊列 { Node *tmp;tmp = que->Front;} while (tmp){ que->Front = que->Front->next;free(tmp);tmp=que->Front;}que->Front = que->Rear = NULL; }void destroy(linkQueue *que) 釋放隊列元素所占據(jù)的動態(tài)空間 { clear(que); }——By?作者：新曉-故知?整理+創(chuàng)作5.優(yōu)先隊列
有時要求進入隊列中的元素具有優(yōu)先級，隊列中元素優(yōu)先級越高出隊越早，優(yōu)先級越低出隊越晚。
個人手頭事務(wù)的處理通常采取這樣的策略，操作系統(tǒng)中進程的調(diào)度、管理也是采用優(yōu)先隊列進行控制的.
元素之間的關(guān)系是由元素的優(yōu)先級決定的，這樣一種隊列稱為優(yōu)先隊列。
????????????????????????????????????????????????????????????? ? ? ??? ?——By?作者：新曉-故知?整理+創(chuàng)作
優(yōu)先隊列有多種實現(xiàn)方式：
采用順序存儲結(jié)構(gòu)實現(xiàn)，是最常用的一種，稱順序優(yōu)先隊列；
其次也可以采用鏈?zhǔn)浇Y(jié)構(gòu)；
后面章節(jié)也有用堆來存儲。
?為了避免整個隊列的后移，造成空間的浪費，當(dāng)有元素出隊時將隊列中最后一個元素移到出隊元素所在的存儲位置，這樣隊列始終從0下標(biāo)開始到某個下標(biāo)終止，中間不會出現(xiàn)空隙。
因為隊列元素始終從0下標(biāo)開始，所以不需要使用循環(huán)。
隊空的條件為： Rear = Front;
隊滿的條件為：Rear = maxSize
????????????????????????????????????????????????????????????????????????——By?作者：新曉-故知?整理+創(chuàng)作
?算法時間復(fù)雜度分析：進隊O(1), 出隊O(n)。
6.另一種策略：
6.1?順序循環(huán)隊列：
元素在隊列中按照優(yōu)先數(shù)由小到大排列，當(dāng)元素進隊時需要找到合適的插入位置，移動后面的元素，將新進元素插入，時間復(fù)雜度為O(n)； 當(dāng)元素出隊時只需刪除隊首元素，為了避免后面元素的移動，可以采用順序循環(huán)隊列，時間復(fù)雜度為O(1)。
?6.2?鏈?zhǔn)酱鎯?yōu)先隊列:
元素優(yōu)先級最高的結(jié)點就是首結(jié)點，所以結(jié)點出隊即刪除首結(jié)點。O(1)
?進隊結(jié)點首先要查找插入位置。比較從首結(jié)點開始，逐個進行，當(dāng)找到第一個結(jié)點的優(yōu)先數(shù)大于新結(jié)點的優(yōu)先數(shù)時，將新結(jié)點插入該結(jié)點前面。O(n)
?總結(jié)：
本文共同探討了隊列的相關(guān)內(nèi)容，在日常生活中有極其豐富的應(yīng)用，作者認(rèn)為要認(rèn)真對待數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，搭建基本知識框架，隨著日積月累的學(xué)習(xí)逐漸填補總結(jié)，從腳踏實地做起，祝愿大家能夠熟悉掌握這門課程，并將其能夠熟悉的應(yīng)用！
耐心看到這里的小伙伴一定很棒！加油！路在腳下，夢在前方！
————————————————
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ?——By?作者：新曉-故知??
總結(jié)
以上是生活随笔為你收集整理的数据结构（C语言版）之队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 手把手教物体检测——M2Det
- 下一篇： cad编辑节点快捷键是什么_cad模型库