目錄
前言●資料結構作為計算機專業基礎課，綜合性強，抽象性高，在一定程度上增加了學習難度，本次我們共同從資料結構的基礎探討，由淺入深進行資料結構的學習， ●本文只淺顯的探討了佇列的基本知識，作者相信隨著學習課程的深入，我們將會對資料結構有更深的理解與識訓！
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教！———————————————— ——By 作者：新曉-故知
正文————————————————
一、佇列
——By 作者：新曉-故知 整理
1. 佇列的抽象資料型別：
佇列的抽象資料型別：
Data：
Operations:
佇列的抽象資料型別:
ADT Queue {
資料物件: ?
資料關系: ?
基本操作:
佇列的順序表示－－用一維陣列base[M]
front=0 rear=M時：
解決的方法－－回圈佇列：
? ——By 作者：新曉-故知 整理
2. 回圈佇列:
回圈佇列初始化:
求回圈佇列的長度:
回圈佇列入隊:
回圈佇列出隊：
q ——By 作者：新曉-故知 整理+創作
3.佇列的順序存盤及實作：
——By 作者：新曉-故知 整理+創作
佇列操作中的Rear和Front
——By 作者：新曉-故知 整理+創作
佇列及操作的實作
演算法時間復雜度分析： 各種操作的時間復雜度都為O(1)，
4.鏈式佇列：
(a) 空佇列
(b) 元素x入佇列
(c) 元素y入佇列
(d) 元素x出佇列
——By 作者：新曉-故知 整理+創作
鏈佇列初始化:
銷毀鏈佇列:
判斷鏈佇列是否為空:
求鏈佇列的隊頭元素:
鏈佇列入隊:
——By 作者：新曉-故知 整理+創作
鏈佇列出隊：
用鏈表存盤佇列中的元素，其中隊首指標 Front指向隊首結點，隊尾指標Rear指向隊尾結點，
?
5.優先佇列
——By 作者：新曉-故知 整理+創作
優先佇列有多種實作方式：
——By 作者：新曉-故知 整理+創作
演算法時間復雜度分析：進隊O(1), 出隊O(n)，
6.另一種策略：
6.1 順序回圈佇列：
6.2 鏈式存盤優先佇列:
總結：
本文共同探討了佇列的相關內容，在日常生活中有極其豐富的應用，作者認為要認真對待資料結構的學習，搭建基本知識框架，隨著榷訓月累的學習逐漸填補總結，從腳踏實地做起，祝愿大家能夠熟悉掌握這門課程，并將其能夠熟悉的應用！
——By 作者：新曉-故知
前言
●資料結構作為計算機專業基礎課，綜合性強，抽象性高，在一定程度上增加了學習難度，本次我們共同從資料結構的基礎探討，由淺入深進行資料結構的學習，
●本文只淺顯的探討了佇列的基本知識，作者相信隨著學習課程的深入，我們將會對資料結構有更深的理解與識訓！
●由于作者水平有限，文章難免存在謬誤之處，敬請讀者斧正，俚語成篇，懇望指教！
————————————————
——By 作者：新曉-故知
正文
————————————————
一、佇列
佇列是另外一種常用的線性結構，到達這種結構的元素越早，離開該結構的時間也越早，所以佇列通常被稱為先進先出(FIFO: First In First Out)佇列，
1.佇列可以看作是插入洗掉位置操作受限的線性表，它的插入和洗掉分別在表的兩端進行，
2.佇列的洗掉操作只能在隊首(front)進行而插入操作只能在隊尾(rear)進行，從而保證了佇列的先進先出特點，
3.元素從隊首洗掉的操作，稱之為出隊（deQueue），
4.元素在隊尾位置插入的操作，稱為進隊（enQueue），
——By 作者：新曉-故知 整理
1. 佇列的抽象資料型別：
佇列的抽象資料型別：
Data：
Operations:
佇列的抽象資料型別:
ADT Queue {
資料物件:
資料關系:
基本操作:
{ (1) InitQueue (&Q) 構造空佇列 (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佇列的順序表示－－用一維陣列base[M]
#define M 100 最大佇列長度 Typedef struct { QElemType *base; 初始化的動態分配存盤空間 int front; 頭指標 int rear; 尾指標 }SqQueue;
front=0 rear=M時：
front=0 rear=M 時 再入隊——真溢位 front≠0 rear=M 時 再入隊——假溢位解決的方法－－回圈佇列：
base[0]接在base[M-1]之后 若rear+1==M 則令rear=0; 實作：利用“模”運算 入隊： base[rear]=x; rear=(rear+1)%M; 出隊： x=base[front]; front=(front+1)%M;
——By 作者：新曉-故知 整理
2. 回圈佇列:
#define MAXQSIZE 100 最大佇列長度 Typedef struct { QElemType *base; 初始化的動態分配存盤空間 int front; 頭指標 int rear; 尾指標 }SqQueue;回圈佇列初始化:
Status InitQueue (SqQueue &Q) { Q.base =new QElemType[MAXQSIZE] if(!Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK; }求回圈佇列的長度:
int QueueLength (SqQueue Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }回圈佇列入隊:
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; }回圈佇列出隊：
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 作者：新曉-故知 整理+創作
3.佇列的順序存盤及實作：
a.佇列的順序存盤，用一組連續的空間存盤佇列中的元素及元素間關系，
b.可以使用隊首指標Front和隊尾指標Rear分別指示隊首元素和隊尾元素存放的下標地址，
c.讓Front指向真正的隊首元素，而Rear指向真正存放隊尾元素的后一陣列單元，這樣隊空的標志Front=Rear，
d.為了防止大批資料移動，當Rear=maxSize時，如果下標為0的空間未用，讓它轉回來，即Rear=Rear%MaxSize，形成回圈佇列，
——By 作者：新曉-故知 整理+創作
佇列操作中的Rear和Front
佇列操作中的Rear和Front
無論進隊、出隊，Rear和Front都向前移動，移動到右邊界時向左邊回圈， 為了區別隊空標志，當隊尾還有一個空間時即告隊滿，浪費了一個空間做代價，
佇列空的標志：Rear=Front
佇列滿的標志：（Rear+1）%maxSize =Front
進隊操作后：Rear= （Rear+1）%maxSize
出隊操作后：Front= （Front+1）%maxSize
——By 作者：新曉-故知 整理+創作
佇列及操作的實作
#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); 釋放佇列元素所占據的動態陣列
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) 釋放佇列元素所占據的動態陣列
{ free(que->array);}
——By 作者：新曉-故知 整理+創作演算法時間復雜度分析： 各種操作的時間復雜度都為O(1)，
4.鏈式佇列：
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 作者：新曉-故知 整理+創作
鏈佇列初始化:
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 作者：新曉-故知 整理+創作
鏈佇列出隊：
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指向隊首結點，隊尾指標Rear指向隊尾結點，
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，否則為0
int isFull(linkQueue *que); 判斷隊滿否，滿回傳1，否則為0
elemType front(linkQueue *que); 讀取隊首元素的值，隊首不變
void enQueue(linkQueue *que, elemType x); 將x進隊，成為新的隊尾
void deQueue(linkQueue *que); 將隊首元素出隊
void clear(linkQueue *que); 將佇列中所有元素清空，為空的佇列
void destroy(linkQueue *que); 釋放佇列元素所占據的動態空間
void initialize(linkQueue *que) 初始化為一個空隊
{ que->Front = que->Rear = NULL; }
void initialize(linkQueue *que); 初始化為一個空隊
int isEmpty(linkQueue *que); 判斷隊空否，慷訓傳1，否則為0
int isFull(linkQueue *que); 判斷隊滿否，滿回傳1，否則為0
elemType front(linkQueue *que); 讀取隊首元素的值，隊首不變
void enQueue(linkQueue *que, elemType x); 將x進隊，成為新的隊尾
void deQueue(linkQueue *que); 將隊首元素出隊
void clear(linkQueue *que); 將佇列中所有元素清空，為空的佇列
void destroy(linkQueue *que); 釋放佇列元素所占據的動態空間
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) 釋放佇列元素所占據的動態空間
{ clear(que); }
——By 作者：新曉-故知 整理+創作
5.優先佇列
有時要求進入佇列中的元素具有優先級，佇列中元素優先級越高出隊越早，優先級越低出隊越晚，
個人手頭事務的處理通常采取這樣的策略，作業系統中行程的調度、管理也是采用優先佇列進行控制的.
元素之間的關系是由元素的優先級決定的，這樣一種佇列稱為優先佇列，
——By 作者：新曉-故知 整理+創作
優先佇列有多種實作方式：
采用順序存盤結構實作，是最常用的一種，稱順序優先佇列；
其次也可以采用鏈式結構；
后面章節也有用堆來存盤，
為了避免整個佇列的后移，造成空間的浪費，當有元素出隊時將佇列中最后一個元素移到出隊元素所在的存盤位置，這樣佇列始終從0下標開始到某個下標終止，中間不會出現空隙，
因為佇列元素始終從0下標開始，所以不需要使用回圈，
隊空的條件為： Rear = Front;
隊滿的條件為：Rear = maxSize
——By 作者：新曉-故知 整理+創作
演算法時間復雜度分析：進隊O(1), 出隊O(n)，
6.另一種策略：
6.1 順序回圈佇列：
元素在佇列中按照優先數由小到大排列，當元素進隊時需要找到合適的插入位置，移動后面的元素，將新進元素插入，時間復雜度為O(n)； 當元素出隊時只需洗掉隊首元素，為了避免后面元素的移動，可以采用順序回圈佇列，時間復雜度為O(1)，
6.2 鏈式存盤優先佇列:
元素優先級最高的結點就是首結點，所以結點出隊即洗掉首結點，O(1)
進隊結點首先要查找插入位置，比較從首結點開始，逐個進行，當找到第一個結點的優先數大于新結點的優先數時，將新結點插入該結點前面，O(n)
總結：
本文共同探討了佇列的相關內容，在日常生活中有極其豐富的應用，作者認為要認真對待資料結構的學習，搭建基本知識框架，隨著榷訓月累的學習逐漸填補總結，從腳踏實地做起，祝愿大家能夠熟悉掌握這門課程，并將其能夠熟悉的應用！
耐心看到這里的小伙伴一定很棒！加油！路在腳下，夢在前方！
————————————————
——By 作者：新曉-故知
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/357111.html
標籤：其他
上一篇：C++程式呼叫libcurl開源庫實作發送郵件的功能
下一篇：Linux就該這么學【基礎指令】