隊(duì)列

與棧不同，他就是現(xiàn)實(shí)中排隊(duì)一樣，講究先來后到，即 先進(jìn)先出。

隊(duì)列@2x.png

我們也可以使用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)來實(shí)現(xiàn)隊(duì)列。

一、順序存儲(chǔ)循環(huán)隊(duì)列

為了防止假溢出現(xiàn)象，在設(shè)計(jì)隊(duì)列的時(shí)候需要將棧設(shè)計(jì)成環(huán)結(jié)構(gòu)。如下圖：

循環(huán)隊(duì)列@2x.png

在存儲(chǔ)的時(shí)候我們通過犧牲一個(gè)存儲(chǔ)單元，來區(qū)分判斷到底是隊(duì)滿還是隊(duì)空的狀態(tài)。

• 隊(duì)空：Q.front = Q.rear;
• 隊(duì)滿：(Q.rear+1)%MAXSIZE == Q.front;
  代碼實(shí)現(xiàn)：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */

typedef int Status;
typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

/* 循環(huán)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) */
typedef struct
{
    QElemType data[MAXSIZE];
    int front;        /* 頭指針 */
    int rear;        /* 尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置 */
}SqQueue;


//6.1 初始化一個(gè)空隊(duì)列Q
Status InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

//6.2 將隊(duì)列清空
Status ClearQueue(SqQueue *Q){
    
    Q->front = Q->rear = 0;
    return OK;
}

//6.3 若隊(duì)列Q為空隊(duì)列,則返回TRUR,否則返回FALSE;
Status QueueEmpty(SqQueue Q){
    //隊(duì)空標(biāo)記
    if (Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}


//6.4 返回Q的元素個(gè)數(shù),也就是隊(duì)列的當(dāng)前長度
int QueueLength(SqQueue Q){
    return (Q.rear - Q.front + MAXSIZE)%MAXSIZE;
}

//6.5 若隊(duì)列不空,則用e返回Q的隊(duì)頭元素,并返回OK,否則返回ERROR;
Status GetHead(SqQueue Q,QElemType *e){
    //隊(duì)列已空
    if (Q.front == Q.rear)
        return ERROR;
    
    *e = Q.data[Q.front];
    return OK;
    
}

//6.6 若隊(duì)列未滿,則插入元素e為新隊(duì)尾元素
Status EnQueue(SqQueue *Q,QElemType e){
    
    //隊(duì)列已滿
    if((Q->rear+1)%MAXSIZE == Q->front)
        return ERROR;
    
    //將元素e賦值給隊(duì)尾
    Q->data[Q->rear] = e;
    
    //rear指針向后移動(dòng)一位,若到最后則轉(zhuǎn)到數(shù)組頭部;
    Q->rear = (Q->rear+1)%MAXSIZE;
    
    return OK;
}

//6.7 若隊(duì)列不空,則刪除Q中隊(duì)頭的元素,用e返回值
Status DeQueue(SqQueue *Q,QElemType *e){
   
    //判斷隊(duì)列是否為空
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    //將隊(duì)頭元素賦值給e
    *e = Q->data[Q->front];
    
    //front 指針向后移動(dòng)一位,若到最后則轉(zhuǎn)到數(shù)組頭部
    Q->front = (Q->front+1)%MAXSIZE;
    
    return OK;
}


//6.8 從隊(duì)頭到隊(duì)尾依次對(duì)隊(duì)列的每個(gè)元素?cái)?shù)組
Status QueueTraverse(SqQueue Q){
    int I;
    i = Q.front;
    while ((i+Q.front) != Q.rear) {
        printf("%d   ",Q.data[I]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
    return OK;
}

二、鏈?zhǔn)酱鎯?chǔ)

鏈?zhǔn)疥?duì)列@2x.png

鏈?zhǔn)酱鎯?chǔ)的代碼實(shí)現(xiàn)

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存儲(chǔ)空間初始分配量 */

typedef int Status;

typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

typedef struct QNode    /* 結(jié)點(diǎn)結(jié)構(gòu) */
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct            /* 隊(duì)列的鏈表結(jié)構(gòu) */
{
    QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */
}LinkQueue;


/*6.1 初始化隊(duì)列*/
Status InitQueue(LinkQueue *Q){
    

    //1. 頭/尾指針都指向新生成的結(jié)點(diǎn)
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));

    //2.判斷是否創(chuàng)建新結(jié)點(diǎn)成功與否
    if (!Q->front) {
        return ERROR;
    }

    //3.頭結(jié)點(diǎn)的指針域置空
    Q->front->next = NULL;
    
    return OK;
}


/*6.2 銷毀隊(duì)列Q*/
Status DestoryQueue(LinkQueue *Q){
    
    //遍歷整個(gè)隊(duì)列,銷毀隊(duì)列的每個(gè)結(jié)點(diǎn)
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
    
}

/*6.3 將隊(duì)列Q置空*/
Status ClearQueue(LinkQueue *Q){
    
    QueuePtr p,q;
    Q->rear = Q->front;
    p = Q->front->next;
    Q->front->next = NULL;
    
    while (p) {
        
        q = p;
        p = p->next;
        free(q);
        
    }
    
    return OK;
}

/*6.4 判斷隊(duì)列Q是否為空*/
Status QueueEmpty(LinkQueue Q){
    if (Q.front == Q.rear)
        return TRUE;
    else
        return FALSE;
}

/*6.5 獲取隊(duì)列長度*/
int QueueLength(LinkQueue Q){
    int i= 0;
    QueuePtr p;
    p = Q.front;
    while (Q.rear != p) {
        i++;
        p = p->next;
    }
    return i;
}

/*6.6 插入元素e為隊(duì)列Q的新元素*/
Status EnQueue(LinkQueue *Q,QElemType e){
    
    //為入隊(duì)元素分配結(jié)點(diǎn)空間,用指針s指向;
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    
    //判斷是否分配成功
    if (!s) {
         return ERROR;
    }
    
    //將新結(jié)點(diǎn)s指定數(shù)據(jù)域.
    s->data = e;
    s->next = NULL;
    
    //將新結(jié)點(diǎn)插入到隊(duì)尾
    Q->rear->next = s;
    
    //修改隊(duì)尾指針
    Q->rear = s;
    
    return OK;
}


/*6.7 出隊(duì)列*/
Status DeQueue(LinkQueue *Q,QElemType *e){
    
    QueuePtr p;
    
    //判斷隊(duì)列是否為空;
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    //將要?jiǎng)h除的隊(duì)頭結(jié)點(diǎn)暫時(shí)存儲(chǔ)在p
    p = Q->front->next;
    
    //將要?jiǎng)h除的隊(duì)頭結(jié)點(diǎn)的值賦值給e
    *e = p->data;
    
    //將原隊(duì)列頭結(jié)點(diǎn)的后繼p->next 賦值給頭結(jié)點(diǎn)后繼
    Q->front->next = p ->next;
    
    //若隊(duì)頭就是隊(duì)尾,則刪除后將rear指向頭結(jié)點(diǎn).
    if(Q->rear == p) Q->rear = Q->front;
    
    free(p);
    
    return OK;
}

/*6.8 獲取隊(duì)頭元素*/
Status GetHead(LinkQueue Q,QElemType *e){
   
    //隊(duì)列非空
    if (Q.front != Q.rear) {
        //返回隊(duì)頭元素的值,隊(duì)頭指針不變
        *e =  Q.front->next->data;
        return TRUE;
    }
    
    return  FALSE;
    
}

/*6.9 遍歷隊(duì)列*/
Status QueueTraverse(LinkQueue Q){
    
    QueuePtr p;
    p = Q.front->next;
    while (p) {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

以上是對(duì)隊(duì)列學(xué)習(xí)的一些總結(jié)。