前言：

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

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

一、鏈隊(duì)列

鏈?zhǔn)疥?duì)列中每個元素定義成一個結(jié)點(diǎn)，含數(shù)據(jù)域與指針域（指向下一結(jié)點(diǎn)），并設(shè)頭尾指針。用圖表示就是。

二、鏈隊(duì)的表示

前面的鏈?zhǔn)浇Y(jié)構(gòu)，總是使用一個結(jié)點(diǎn)的結(jié)構(gòu)來表示鏈表，但是在這里使用新的存儲結(jié)構(gòu)。定義一個結(jié)點(diǎn)結(jié)構(gòu)，和一個隊(duì)列結(jié)構(gòu)。兩個結(jié)構(gòu)嵌套。

//定義節(jié)點(diǎn)結(jié)構(gòu)
typedef struct QNode
{
    QElemType   data;   /*數(shù)據(jù)域*/
    struct QNode   * next;   /*指針域*/
 }QNode, *QueuePtr;
//定義隊(duì)列結(jié)構(gòu)
 typedef struct
 {
    QueuePtr front;
    QueuePtr rear;
 }LinkQueue;

三、鏈隊(duì)的基本操作

1. 鏈隊(duì)的初始化

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

2. 鏈隊(duì)的銷毀

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

3. 入隊(duì)

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

4. 出隊(duì)

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;   //隊(duì)頭元素p出隊(duì)
    if(Q.rear == p)   //如果隊(duì)中只有一個元素p, 則p出隊(duì)后成為空隊(duì)
    Q.rear = Q.front;     //給隊(duì)尾指針賦值
    free(p);   //釋放存儲空間
    return OK;
}

四、順序隊(duì)列

用一組連續(xù)的存儲單元依次存放隊(duì)列的元素，并設(shè)兩個指針front、rear分別指示隊(duì)頭和隊(duì)尾元素的位置。
front：指向?qū)嶋H的隊(duì)頭；rear：指向?qū)嶋H隊(duì)尾的下一位置。
初態(tài)：front＝rear＝0；隊(duì)空：front＝rear;隊(duì)滿：rear＝M;
入隊(duì)：q[rear]=x; rear＝ rear+1; 出隊(duì)：x=q[front];front=front+1;

順序隊(duì)列的表示：

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

存在的問題：

隨著入隊(duì)、出隊(duì)操作的進(jìn)行，整個隊(duì)列會整體向后移動，這樣就出現(xiàn)了下圖的現(xiàn)象：隊(duì)尾指針雖然已經(jīng)移到了最后，而隊(duì)列卻未真滿的“假溢出”現(xiàn)象，使得隊(duì)列的空間沒有得到有效的利用

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

有以下兩種方法：

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

五、循環(huán)隊(duì)列

在循環(huán)隊(duì)列中，不可以根據(jù)等式front == rear可以判別隊(duì)滿和隊(duì)空。因?yàn)榇藭r條件是相同的，解決這種問題的方法一般有兩種。

少用（損失）一個空間,以尾指針加1等于頭指針作為隊(duì)滿的標(biāo)志。因此：當(dāng)front==rear，表示循環(huán)隊(duì)列為空；當(dāng)front ==（rear+1）% MAXLEN，表示循環(huán)隊(duì)列為滿。
在定義結(jié)構(gòu)體時，附設(shè)一個存儲循環(huán)隊(duì)列中元素個數(shù)的變量n，當(dāng)n==0時表示隊(duì)空；當(dāng)n==MAXLEN時為隊(duì)滿。

循環(huán)隊(duì)列的基本操作：

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. 求隊(duì)列長度

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

3. 入隊(duì)

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. 出隊(duì)

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

到此這篇關(guān)于C利用語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之隊(duì)列的文章就介紹到這了,更多相關(guān)C語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu) 隊(duì)列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論