892
數據結構學習筆記--隊列
引子：隻有學習才是激情的生命，才是燃燒的歲月，才是完美的人生
聲明：本筆記由《嵌入式係統軟件設計中的數據結構》產生，旨在提升自己的軟件設計水平，絕無侵權行為，望轉載者備注說明
一 隊列邏輯結構
1 是一種隻允許在表的一端-“隊尾“進行插入，而在另一端-”隊頭“進行刪除的線性表。實則為線性表的一種特例。也稱為先進先出表
2 當隊列中沒有結點時稱為空隊列。隊列的修改是依照先進先出的原則進行的
二 隊列的基本運算
置空隊 SetNull(Q)：將隊列 Q 置成空的隊列
判隊空 Empty(Q)：若 Q 為空隊列，返回”真“，否則為”假“
取頭結點 GetFront(Q)：讀取隊列 Q 的頭結點的值，隊列中的結點保持不變
入隊 InQuery(Q, x)：將結點 x 插入到隊列 Q 的隊尾
出隊 DeQuery(Q)：刪除隊列頭結點
三 隊列分類
1 順序隊列
采用順序存儲結構，實則為運算受限的順序表，可用一維數組來存放結點數據
front 指示隊列當前隊頭結點的數組下標的位置
rear 指示隊列當前隊尾結點的數組下標的位置
結構描述
+++++++++++++++++++++++++++++++++++++++++++++++
#define maxsize 1024
typedef int datatype;
typedef struct
{
datatype data[maxsize]; //存放數據元素的一維數組
int front; //頭結點
int rear; //尾結點
}sequery;
++++++++++++++++++++++++++++++++++++++++++++++++
順序隊列的隊頭和隊尾的標誌位置分析
front指向當前隊列頭結點的前一個位置
rear指向當前隊列尾結點的位置
隊列的溢出情況分析
出隊運算：front++；//頭指針 +1
當空隊時，front = rear，若再做出隊操作，會產生“下溢”
入隊運算：rear++；//尾指針 +1
data[rear] = x; //x 入隊
當隊滿時，再做入隊操作會產生“上溢”
假上溢 原因：被刪除的結點（出隊結點）的空間永遠不能再使用
2 循環隊列
將順序隊列首尾相連，即 data[0] 接在 data[max - 1] 之後
循環隊列克服假上溢：
若當前尾指針等於數組的上界（max - 1），再做入隊操作時，令尾指針等於數組的下界（0）
入隊：rear = (rear + 1) % max;
data[rear] = x;
出隊：front = (front + 1) % max;
循環隊列隊空隊滿情況：
少用一個結點空間，即頭結點指向的空間不使用
隊空：front = rear
隊滿：(rear + 1) % max = front;
循環隊列的運算
+++++++++++++++++++++++++++++++++++++++++++++++++++++
/* 置空隊 */
void SetNull(sequeue * sq)
{
sq->front = 0;
sq->rear = 0;
}
/* 判隊空 */
int Empty(sequeue * sq)
{
if (sq->rear == sq->front)
return 1;
else
return 0;
}
/* 取頭結點 */
datatype GetFront(sequeue *sq)
{
if (Empty(sq))
{
printf("queue is null");
return(NULL);
/**
* For GCC Warning
*/
}
else
return(sq->data[(sq->front+1)%max]);
}
/* 入隊 */
int InQueue(sequeue * sq, datatype x)
{
if ((rear + 1)%max == sq->front)
{
printf("queue is full");
return(NULL);
}
else
{
sq->rear = (sq->rear+1)%max;
sq->data[sq->rear] = x;
return 1;
}
}
/* 出隊 */
datatype DeQueue(sequeue * sq)
{
if (Empty(sq))
{
printf("queue is full");
return(NULL);
}
else
{
sq->front = (sq->front+1)%max;
return(sq->data[sq->front]);
}
}
+++++++++++++++++++++++++++++++++++++++++++++++++++++
3 鏈隊列
采用鏈式存儲的隊列，類似單鏈表，但其操作受限，隻允許在表頭刪除節點和在表為插入節點
未完待續
最後更新：2017-04-03 15:21:44