??本篇介紹佇列的鏈式存盤，因為佇列是在兩頭插入和洗掉的邏輯結構，因此要用具體的物理存盤結構的時候，需要用到兩個指標，一個是頭指標，一個是尾指標，頭指標指向隊頭指標，尾指標指向隊尾指標，即單鏈表的最后一個結點，下面介紹有關鏈佇列的演算法實作，
一：佇列的鏈式存盤型別
typedef struct{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front,*rear;
}LinkQueue
??當Q.front == NULL且Q.rear == NULL，鏈式佇列為空，
??入隊時，先建立一個新結點，然后將新結點插入到鏈表的尾部，并讓Q.rear指向這個新插入的結點，若原佇列為空，讓Q.rear也指向這個結點，
??出隊時，先取隊頭元素，將其從鏈表中洗掉，并讓Q.front指向下一個結點，若該結點是最后一個結點，則置Q.front與Q.rear都為NULL，
??上面的是不帶頭結點的鏈佇列，如果需要簡單操作，則需要將佇列設計成一個帶頭結點的單鏈表，
??使用鏈佇列不會出現存盤分配不合理和"溢位"的問題，適合需要多個佇列的演算法問題，
二：鏈佇列的基本操作
1.初始化
void InitQueue(ListQueue &Q){
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
Q.front -> next = NULL;
}
2.判隊空
bool IsEmpyt(LinkQueue Q){
if(Q.front == Q.rear) return true;
else return false;
}
3.入隊
void EnQueue(LinkQueue &Q,ElemType x){
LinkQueue *s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = https://www.cnblogs.com/ITXiaoAng/p/x;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
}
4.出隊
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front == Q.rear) retun false;
LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next;
if(Q.rear == p)
Q.rear = Q.front; //若原佇列中只有一個結點，洗掉后變空
free(p);
return true;
}
三：佇列的應用
1.雙端佇列
??雙端佇列是指允許兩端都可以進行入隊和出隊的佇列，也有輸入受限的雙端佇列和輸出受限的雙端佇列，在實際應用中用到的地方也有很多，
2.其他應用
??堆疊在括號匹配和運算式求值中用處很多，以及所有用到遞回的演算法都可用堆疊來實作其非遞回演算法，
??對于佇列來說，佇列在二叉樹層次遍歷以及計算機系統中用處廣泛，在列印機列印和CPU資源競爭處理中用處也很廣泛，
3.矩陣的壓縮存盤
??陣列是線性表的推廣，所以可以用陣列類似堆疊或者佇列進行一些復雜操作，最常用的就是矩陣的壓縮存盤操作，可以類似堆疊或者佇列進行操作，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/50505.html
標籤：其他