C利用語言實現數據結構之隊列

Posted on by

前言：

隊列在生活中也比較常見，例如購物排隊——新來的成員總是加入隊尾,每次離開的成員總是隊列頭上的。

隊列按存儲方式可以分為兩種：順序隊列和鏈隊列。

一、鏈隊列

鏈式隊列中每個元素定義成一個結點，含數據域與指針域（指向下一結點），並設頭尾指針。用圖表示就是。

二、鏈隊的表示

前面的鏈式結構，總是使用一個結點的結構來表示鏈表，但是在這裡使用新的存儲結構。定義一個結點結構，和一個隊列結構。兩個結構嵌套。

//定義節點結構
typedef struct QNode
{
    QElemType   data;   /*數據域*/
    struct QNode   * next;   /*指針域*/
 }QNode, *QueuePtr;
//定義隊列結構
 typedef struct
 {
    QueuePtr front;
    QueuePtr rear;
 }LinkQueue;

三、鏈隊的基本操作

1. 鏈隊的初始化

Status initQueue(LinkQueue *Q)
{ 
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front) exit(OVERFLOW);
    Q.front->next = NULL;
    return OK;
}

2. 鏈隊的銷毀

Status destroyQueue(LinkQueue *Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
   return OK;
}

3. 入隊

Status enQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) exit(OVERFLOW);
    //插入數據
    p->data = e;
    p->next = NULL;
    //Q.rear一直指向隊尾
    Q.rear->next = p;
    Q.rear = p;
    return OK;
 }

4. 出隊

Status deQueue(LinkQueue *Q, QElemType e)
{
    if(Q.front == Q.rear) return ERROR;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;   //隊頭元素p出隊
    if(Q.rear == p)   //如果隊中隻有一個元素p, 則p出隊後成為空隊
    Q.rear = Q.front;     //給隊尾指針賦值
    free(p);   //釋放存儲空間
    return OK;
}

四、順序隊列

用一組連續的存儲單元依次存放隊列的元素，並設兩個指針front、rear分別指示隊頭和隊尾元素的位置。
front：指向實際的隊頭；rear：指向實際隊尾的下一位置。
初態：front＝rear＝0；隊空：front＝rear;隊滿：rear＝M;
入隊：q[rear]=x; rear＝ rear+1; 出隊：x=q[front];front=front+1;

順序隊列的表示： 

#define MAXQSIZE  100
typedef struct
{
    QElemType *base;
    int  front;   //頭指針指示器 
    int  rear;  //尾指針指示器
} SqQueue;

存在的問題：

隨著入隊、出隊操作的進行，整個隊列會整體向後移動，這樣就出現瞭下圖的現象：隊尾指針雖然已經移到瞭最後，而隊列卻未真滿的“假溢出”現象，使得隊列的空間沒有得到有效的利用

那我們該如何解決假溢出的問題呢？

有以下兩種方法：

  • 將隊中元素向隊頭移動：當移動數據較多時將會影響隊列的操作速度。
  • 采用循環隊列：Q[0]接在Q[MAXQSIZE-1]之後，一個更有效的方法是將隊列的數據區Q[0 .. MAXQSIZE-1]看成是首尾相連的環，即將表示隊首的元素Q[0]與表示隊尾的元素Q[MAXQSIZE–1]連接起來，形成一個環形表，這就成瞭循環隊列。當Q.rear=MAXQSIZE-1時再入隊，令Q.rear=0, 則可以利用已被刪除的元素空間。如下圖。

五、循環隊列

在循環隊列中，不可以根據等式front == rear可以判別隊滿和隊空。因為此時條件是相同的，解決這種問題的方法一般有兩種。

少用（損失）一個空間,以尾指針加1等於頭指針作為隊滿的標志。因此：當front==rear，表示循環隊列為空；當front ==（rear+1）% MAXLEN，表示循環隊列為滿。
在定義結構體時，附設一個存儲循環隊列中元素個數的變量n，當n==0時表示隊空；當n==MAXLEN時為隊滿。

循環隊列的基本操作：

1. 初始化

Status initQueue (SqQueue *Q)
{
    Q.base=(QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q.base) exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}

2. 求隊列長度

int queueLength(SqQueue *Q)
{
    return (Q.rear - Q.front+MAXQSIZE) % MAXQSIZE;
}

3. 入隊

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;
}

4. 出隊

Status deQueue (SqQueue *Q, QElemType e)
{
    if(Q.front == Q.rear)
    return ERROR;
    e = Q.base[Q.front];
    Q.front = (Q.front+1)%MAXQSIZE;
    return OK;
}

到此這篇關於C利用語言實現數據結構之隊列的文章就介紹到這瞭,更多相關C語言實現數據結構 隊列內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：