隊列——鏈隊列和循環隊列
鏈隊列
轉載：http://www.noobyard.com/article/p-zwjpgmjx-o.htmlhtml
1 鏈隊列的存儲結構編程
將對頭指針front指向鏈隊列的頭結點，隊尾指針rear指向終端結點。數組
空隊列時，頭指針front和尾指針rear都指向頭結點。spa
鏈隊列的存儲結構爲：.net
typedef int QElemType;
typedef struct QNode { //結點結構
QElemType data;
struct QNode *next;
}QNode;
typedef struct QNode * QueuePtr;
typedef struct { //隊列的鏈表結構
QueuePtr rear;
QueuePtr front;
}LinkQueue;
2 入隊操做指針
//插入元素e爲Q的新的隊尾結點
Status EnQueue(QueuePtr Q, QElemType e) {
QueuePtr q = (QueuePtr)malloc(sizeof(QNode));
if (!q) { //存儲分配失敗
exit(OVERFLOW);
}
q->data = e;
q->next = NULL;
Q->rear->next = q;
Q->rear = q;
return OK;
}
3 出隊操做code
出隊操做，就是頭結點的後繼結點出隊，將頭結點的後繼改成它後面的結點。htm
若鏈表除頭結點外只剩一個元素時，則需將rear指針指向頭結點。blog
//若隊列不空，刪除Q的隊頭元素，用e返回其值，並返回OK，不然返回ERROR。
Status DeQueue(QueuePtr Q, QElemType *e) {
QueuePtr q;
if (Q->rear == Q->front) { //空隊列
return ERROR;
}
q = Q->front->next; //q指向第一個結點
*e = q->data;
Q->front->next = q->next;
if (Q->rear == p) { //若隊頭就是隊尾，刪除後，須要將rear指針指向頭結點
Q->rear = Q->front;
}
free(q);
return OK;
}
4 循環隊列與鏈隊列的比較隊列
從時間上考慮，循環隊列和鏈隊列的基本操做都是O(1),不過循環隊列是事先已申請好空間，使用期間不會釋放。而對於鏈隊列，每次申請和釋放結點也會存在一些時間開銷。若是入隊和出隊頻繁，二者仍是有細微差別的。
從空間來講，循環隊列必須有一個固定的長度，因此就有了存儲元素個數和空間浪費的問題。而鏈隊列不存在這個問題，儘管它須要一個指針域，會產生一些空間上的開銷，可是是能夠接受的。因此從空間上說，鏈隊列更加靈活。
總的來講，在能夠肯定鏈隊列最大長度的狀況下，建議使用循環隊列。若是沒法預估隊列的長度，則使用鏈隊列。
循環隊列
轉載：https://www.cnblogs.com/hughdong/archive/2017/05/11/6841970.html
（做者說的挺有意思的話：You know something and I know nothing.）
和順序棧相相似，在隊列的順序存儲結構中，除了用一組地址連續的存儲單元依次存放從隊頭到隊尾的元素外，尚需敷設兩個指針front和rear分別指示隊列頭元素位置和隊列尾元素的位置。
若是使用順序表做爲隊列的話，當處於右圖狀態則不能繼續插入新的隊尾元素，不然會由於數組越界而致使程序代碼被破壞。
由此產生了由鏈表實現的循環隊列，只有隊列未滿時才能夠插入新的隊尾元素。
下面內容，轉載：http://www.noobyard.com/article/p-konwsnvh-gw.html
1.圖中有兩個指針(其實就是兩個整數型變量，由於在這裏有指示做用，因此這裏理解爲指針)front、rear,一個指示隊頭，一個指示隊尾。
2.rear和front互相追趕着，這個追趕過程就是隊列添加和刪除的過程，若是rear追到head說明隊列滿了，若是front追到rear說明隊列。
說明：令隊列空間中的一個單元閒置，使得隊列非空時，Q.rear與Q.front之間至少間隔一個空閒單。（思考爲何空一格）
3.咱們把它掰彎，用的是求餘，這樣兩個值就不會跑出最大範圍，而且能夠實現彎曲的效果，因此說對於循環隊列咱們必須給定最大值MAXQSIZE。
這實際上是咱們臆想的，反正咱們要作的就是利用循環來解決空間浪費的問題。
循環隊列的實現過程（important）
☆當添加一個元素時,(rear+1)%MAXQSIZE; //理解爲何求餘？
☆當刪除一個元素時,(front+1)%MAXQSIZE；//理解爲何求餘？
☆當rear=front的時候，隊列多是滿，也多是空。（這也是爲何空一格的緣由）
由於存在滿和空兩種狀況，咱們須要分別判斷：
☆滿：當隊列添加元素到rear的下一個元素是head的時候，也就是轉圈子要碰頭了，咱們就認爲隊列滿了。(Q.rear+1)%MAXSIZE=Q.front
☆空：當隊列刪除元素到head=rear的時候，咱們認爲隊列空了。Q.rear==Q.front,不必定爲0
上面這一段要好好理解，在其餘編程的地方，也會用到相似的思想。
下面的代碼思想很重要。
2.1對節點的定義
#define MAXQSIZE 100
typedef int QElemtype;
typedef int status;
typedef struct{
QElemtype *base;
int front;
int rear;
}SqQueue;
2.2初始化隊列
SqQueue* InitQueue()
{
SqQueue *q;
q=new SqQueue;
q->base=new int[MAXQSIZE];
q->rear=q->front=0;
return q;
}
2.3添加操做
status EnQueue(SqQueue *q,QElemtype e)
{
//插入到隊尾
if((q->rear+1)%MAXQSIZE==q->front)
return 0;
q->base[q->rear]=e;
q->rear=(q->rear+1)%MAXQSIZE;
return 1;
}
2.4刪除操做
status DeQueue(SqQueue *q)
{
if(q->front==q->rear)
return 0;
printf("%d",q->base[q->front]);
q->front =(q->front+1)%MAXQSIZE;
return 1;
}
備註，這插入和刪除的操做，相似於標記。（這也很重要）
2.5獲取隊列長度
int QueueLength(SqQueue *q)
{
return (q->rear-q->front+MAXQSIZE)%MAXQSIZE;
}
補：還有些其餘的隊列，好比優先隊列，雙端隊列。（用的時候能夠查STL）
隊列練習: