什么是隊列

隊列是一種操作受限的線性表，其限制條件為允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。插入的一端叫做隊尾，刪除的一端叫做隊頭。向隊列中插入新元素的行為稱為進(jìn)隊，從隊列中刪除元素的行為稱為出隊。

隊列的特點

隊列的特點是先進(jìn)先出。舉例：火車從山洞一端開進(jìn)，從山洞另一端開出，車廂好比一個個元素，最先進(jìn)入山洞的車廂先出，后進(jìn)山洞的車廂后出。

循環(huán)隊列

循環(huán)隊列的結(jié)構(gòu)：

20170305131448402.jpg

typedef struct SqQueue{  
    int data[maxsize];  
    int front;//隊首指針  
    int rear;//隊尾指針  
}SqQueue;

循環(huán)隊列的狀態(tài)

（1）隊空狀態(tài)：

qu.front ==qu.rear

（2）隊滿狀態(tài)

(qu->rear+1)%maxsize ==qu->front 

循環(huán)隊列的操作

（1）進(jìn)隊列

qu->rear=(qu->rear+1)%maxsize;  
qu->data[qu->rear]=x; 

（2）出隊列

*y=qu->data[qu->front];  
qu->front=(qu->front+1)%maxsize;

循環(huán)隊列的實現(xiàn)

#include<stdio.h>  
#include<stdlib.h>  
#define maxsize 50  
typedef struct SqQueue{  
    int data[maxsize];  
    int front;//隊首指針  
    int rear;//隊尾指針  
}SqQueue;  
//創(chuàng)建循環(huán)隊列  
SqQueue initQueue(){  
    SqQueue *sq=(SqQueue *)malloc(sizeof(SqQueue));  
    if(sq ==NULL){  
        return;  
    }  
    sq->rear=sq->front=0;  
    return *sq;  
}  
//判斷循環(huán)隊列是否為空  
int isEmpty(SqQueue qu){  
    return (qu.front ==qu.rear?1:0);  
}  
//元素進(jìn)循環(huán)隊列  
int enQueue(SqQueue *qu,int x){  
    if((qu->rear+1)%maxsize ==qu->front){  
        return 0;  
    }  
    qu->rear=(qu->rear+1)%maxsize;  
    qu->data[qu->rear]=x;  
    return 1;  
}  
//元素出循環(huán)隊列  
int deQueue(SqQueue *qu,int *y){  
    if(qu->rear ==qu->front){  
        return 0;  
    }  
    *y=qu->data[qu->front];  
    qu->front=(qu->front+1)%maxsize;  
    return 1;  
}  
//打印循環(huán)隊列  
int printQueue(SqQueue qu){  
    if(qu.rear ==qu.front){  
        return 0;  
    }  
    while(qu.rear !=qu.front){  
        qu.front=(qu.front+1)%maxsize;  
        printf("當(dāng)前隊列值=%d\n",qu.data[qu.front]);  
    }  
    return 1;  
}  
void main(){  
    int y=0;  
    SqQueue sq =initQueue();  
    enQueue(&sq,1);  
    enQueue(&sq,2);  
    enQueue(&sq,3);  
    enQueue(&sq,4);  
    deQueue(&sq,&y);  
    printQueue(sq);  
    printf("當(dāng)前的front=%d\n",sq.front);  
    printf("當(dāng)前的rear=%d\n",sq.rear);  
      
}  

20170305131117687.png

鏈隊列

鏈隊列的結(jié)構(gòu):

20170305151137321.jpg

//鏈隊列結(jié)點結(jié)構(gòu)  
typedef struct QNode{  
    int data;  
    struct QNode *next;  
}QNode;  
//鏈隊列結(jié)構(gòu)  
typedef struct LiQueue{  
    QNode *front;  
    QNode *rear;  
}LiQueue;  

鏈隊列的狀態(tài)

（1）隊空

lq->front==NULL || lq->rear==NULL

鏈隊列的操作

（1）進(jìn)隊列

lq->rear->next=p;  
lq->rear=p;

（2）出隊列

p=lq->front;  
lq->front=p->next;  
x=p->data;  
free(p); 

鏈隊列的實現(xiàn)

#include<stdio.h>  
#include<stdlib.h>  
//鏈隊列結(jié)點結(jié)構(gòu)  
typedef struct QNode{  
    int data;  
    struct QNode *next;  
}QNode;  
//鏈隊列結(jié)構(gòu)  
typedef struct LiQueue{  
    QNode *front;  
    QNode *rear;  
}LiQueue;  
//創(chuàng)建鏈隊列  
LiQueue initQueue(){  
    LiQueue *lq=(LiQueue *)malloc(sizeof(LiQueue));  
    if(lq ==NULL){  
        return;  
    }  
    lq->front=lq->rear=NULL;  
    return *lq;  
}  
//判斷鏈隊列是否為空  
int isEmpty(LiQueue *lq){  
    if(lq->front==NULL || lq->rear==NULL){  
        return 0;  
    }else{  
        return 1;  
    }  
}  
//元素進(jìn)鏈隊列  
void enQueue(LiQueue *lq,int x){  
    QNode *p;  
    p=(QNode *)malloc(sizeof(QNode));  
    p->data=x;  
    p->next=NULL;  
    if(lq->rear==NULL){  
        lq->front=lq->rear=p;//如果第一次插入則設(shè)置頭指針和尾指針為p  
    }else{  
        lq->rear->next=p;//鏈隊列的尾部插入p  
        lq->rear=p;//設(shè)置鏈隊列的尾指針指向p  
    }  
}  
//元素出鏈隊列  
int deQueue(LiQueue *lq,int *y){  
    QNode *p=lq->front;  
    if(lq->rear==NULL || lq->front==NULL){  
        return 0;  
    }  
    if(lq->front==lq->rear){  
        lq->front=lq->rear=NULL;  
    }else{  
        lq->front=lq->front->next;  
    }  
    *y=p->data;  
    free(p);  
    return 1;  
}  
//打印鏈隊列  
void printQueue(LiQueue lq){  
    if(lq.front==NULL || lq.rear==NULL){  
        return;  
    }  
    while(lq.front!=NULL){  
        printf("%d\n",lq.front->data);  
        lq.front=lq.front->next;  
    }  
}  
void main(){  
    int y=0;  
    LiQueue lq=initQueue();  
    enQueue(&lq,1);  
    enQueue(&lq,2);  
    enQueue(&lq,3);  
    enQueue(&lq,4);  
    enQueue(&lq,5);  
    deQueue(&lq,&y);  
    printQueue(lq);  
    printf("出隊列元素=%d\n",y);  
}  

20170305151547136.png