一、隊(duì)列

隊(duì)列是一種限定性的線性表，只能在隊(duì)尾進(jìn)行插入，在隊(duì)頭刪除操作。先進(jìn)先出的線性表。

二、順序隊(duì)列

上圖所示，入隊(duì)和出隊(duì)的操作中，頭、尾指針只增加不減小，導(dǎo)致被刪除元素的空間永遠(yuǎn)無法重新利用。盡管數(shù)組中的元素個數(shù)遠(yuǎn)遠(yuǎn)小于數(shù)組大小，但由于尾指針已經(jīng)指向向量空間的上限，導(dǎo)致不能進(jìn)行入隊(duì)操作，這種現(xiàn)象稱為“假溢出”現(xiàn)象。
為了解決“假溢出”的問題，我們往往在定義一個順序隊(duì)列時，定義的是一個循環(huán)隊(duì)列，即：將隊(duì)列分配的空間看成是一個首尾相接的圓環(huán)。如下圖所示：

循環(huán)隊(duì)列為空時，對頭指針和隊(duì)尾指針的位置是相同的，為了解決循環(huán)隊(duì)列無法區(qū)分隊(duì)空和隊(duì)滿的情況，讓循環(huán)隊(duì)列中隊(duì)尾指針永遠(yuǎn)指向一個空白區(qū)域：

1. 順序隊(duì)列的結(jié)構(gòu)體設(shè)計

#define MAXSIZE 10//線性表長度的最大值

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0

typedef int Status;//狀態(tài)值
typedef int ElemType;//結(jié)點(diǎn)的數(shù)據(jù)類型，視實(shí)際情況而定。在此以int為例。

typedef struct SqQueue{
    ElemType data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

2.初始化一個空隊(duì)列

Status InitSqQueue(SqQueue *Q){
    
    Q->front = Q->rear = 0;
    return OK;
}

3.清空隊(duì)列

Status ClearSqQueue(SqQueue *Q) {
    
    Q->rear = Q->front = 0;
    return OK;
}

4.隊(duì)列是否為空

//判斷循環(huán)隊(duì)列是否為空
int isSqQueueClear(SqQueue Q) {
    
    if (Q.rear == Q.front) {
        return 1;
    }else {
        return 0;
    }
}

5.獲取隊(duì)列的長度

int GetSqQueueLength(SqQueue Q) {
    
    int length = Q.rear-Q.front;
    return length;
}

6.出隊(duì)

Status PopSqQueue(SqQueue *Q, ElemType *e) {
    //隊(duì)列為空不能出隊(duì)
    if (Q->front == Q->front) {
        return ERROR;
    }
    //返回出隊(duì)元素
    *e = Q->data[Q->front];
    
    Q->front = (Q->front+1)%MAXSIZE;
    
    return OK;
}

7.入隊(duì)

Status PushSqQueue(SqQueue *Q, ElemType e) {
    
    //隊(duì)滿不能入隊(duì)
    if ((Q->rear+1)%MAXSIZE == Q->front) {
        return ERROR;
    }
    
    Q->data[Q->rear] = e;
    
    Q->rear = (Q->rear+1)%MAXSIZE;
    
    return OK;
}

8.遍歷

void TraverseSqQueue(SqQueue Q) {
    
    int i = Q.front;
    
    while (i != Q.rear) {
        
        printf("%d ",Q.data[i]);
        
        i = (i+1)%MAXSIZE;
    }
    
    printf("\n");
}

二、鏈?zhǔn)疥?duì)列

1. 鏈?zhǔn)疥?duì)列的結(jié)構(gòu)體設(shè)計

//結(jié)點(diǎn)
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node *NodePtr;

//隊(duì)列鏈表
typedef struct LinkQueue{
    NodePtr front;
    NodePtr rear;
}LinkQueue;

2.初始化一個空隊(duì)列

Status InitLinkQueue(LinkQueue *Q){
    
    Q->rear = Q->front = (NodePtr)malloc(sizeof(Node));
    
    if (Q->front == NULL) {
        return ERROR;
    }
    Q->front->next = NULL;
    
    return OK;
}

3.清空隊(duì)列

//清空隊(duì)列
Status ClearLinkQueue(LinkQueue *Q){
    
    NodePtr 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;
}

4.隊(duì)列是否為空

int IsEmpty(LinkQueue Q){
    
    if (Q.front->next == Q.rear->next) {
        return 1;
    }
    return 0;
}

5.獲取隊(duì)列的長度

int LinkQueueLength(LinkQueue Q){
    
    int i = 0;
    NodePtr p = Q.front;
    
    while (p != Q.rear) {
        i++;
        p = p->next;
    }
    
    return i;
}

6.出隊(duì)

Status PopLinkQueue(LinkQueue *Q){
    
    if (Q->front == Q->rear) {
        return ERROR;
    }
    
    NodePtr temp = Q->front->next;
    Q->front->next = temp->next;
    
    free(temp);
    
    return OK;
}

7.入隊(duì)

Status PushLinkQueue(LinkQueue *Q, ElemType e) {
    
    NodePtr p = (NodePtr)malloc(sizeof(Node));
    if (p == NULL) {
        return ERROR;
    }
    p->data = e;
    p->next = NULL;
    
    Q->rear->next = p;
    Q->rear = Q->rear->next;
    
    return OK;
}

8.遍歷

void TranverseLinkQueue(LinkQueue Q){
    
    NodePtr p = Q.front->next;
    
    while (p) {
        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n");
    
}

9.銷毀隊(duì)列

//銷毀隊(duì)列
Status DeletLinkQueue(LinkQueue *Q){
    
    while (Q->front) {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    
    return OK;
}