資料結構學習筆記--隊列

引子：隻有學習才是激情的生命，才是燃燒的歲月，才是完美的人生

聲明：本筆記由《嵌入式系統軟體設計中的資料結構》産生，旨在提升自己的軟體設計水準，絕無侵權行為，望轉載者備注說明

一 隊列邏輯結構

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

         */

    }

        return(sq->data[(sq->front+1)%max]);

/* 入隊 */

int inqueue(sequeue * sq, datatype x)

    if ((rear + 1)%max == sq->front)

        printf("queue is full");

        sq->rear = (sq->rear+1)%max;

        sq->data[sq->rear] = x;

/* 出隊 */

datatype dequeue(sequeue * sq)

        sq->front = (sq->front+1)%max;

        return(sq->data[sq->front]);

3 鍊隊列

采用鍊式存儲的隊列，類似單連結清單，但其操作受限，隻允許在表頭删除節點和在表為插入節點

未完待續