隊列

和棧相反，隊列（Queue）是一種先進(jìn)先出（First In First Out，縮寫為FIFO）的線性表。

它只允許在表的一端進(jìn)行插入，而在另一端刪除元素。這和我們?nèi)粘Ｉ钪械呐抨犑且恢碌模钤邕M(jìn)入隊列的元素最早離開。隊列在程序設(shè)計中也經(jīng)常出現(xiàn)。一個最典型的例子就是操作系統(tǒng)中的作業(yè)排隊。在允許多道程序運(yùn)行的計算機(jī)系統(tǒng)中，同時有幾個作業(yè)運(yùn)行。如果運(yùn)行的結(jié)果都需要通過通道輸出，那就要按請求輸出的先后次序排隊。每當(dāng)通道傳輸完畢可以接受新的輸出任務(wù)時，隊頭的作業(yè)先從隊列中退出輸出操作。凡是申請輸出的作業(yè)都從隊尾進(jìn)入隊列。

在隊列中，允許插入的一端叫隊尾（rear），允許刪除的一端則稱為隊頭（front）。

除了棧和隊列之外，還有一種限定性數(shù)據(jù)結(jié)構(gòu)是雙端隊列（Deque）。
雙端隊列是限定插入和刪除操作在表的兩端進(jìn)行的線性表。
在實(shí)際使用中，還可以有輸出受限的雙端隊列（即一個端點(diǎn)允許插入和刪除，另一個端點(diǎn)只允許插入的雙端隊列）和輸入受限的雙端隊列（即一個端點(diǎn)允許插入和刪除，另一個端點(diǎn)只允許刪除的雙端隊列）。
而如果限定雙端隊列從某個端點(diǎn)插入的元素只能從該端點(diǎn)刪除，則雙端隊列就蛻變?yōu)閮蓚€棧底相鄰的棧了。

盡管雙端隊列看起來似乎比棧和隊列更靈活，但實(shí)際上在應(yīng)用程序中遠(yuǎn)不及棧和隊列有用。

github源碼

SingleLinkedListQueue.c文件

#include <stdio.h>
#include <malloc.h>
#include "SingleLinkedListQueue.h"

static void clear(SingleLinkedListQueue *This);
static int isEmpty(SingleLinkedListQueue *This);
static int length(SingleLinkedListQueue *This);
static QNode *getHead(SingleLinkedListQueue *This);
static int enQueue(SingleLinkedListQueue *This,QNode *n);
static int deQueue(SingleLinkedListQueue *This,QNode *n);
static int traverse(SingleLinkedListQueue *This,int (*visit)(QNode *n));

SingleLinkedListQueue *InitSingleLinkedListQueue(){
    SingleLinkedListQueue *Q = (SingleLinkedListQueue *)malloc(sizeof(SingleLinkedListQueue));
    QNode *p = (QNode *)malloc(sizeof(QNode));
    Q->This = p;
    Q->front = p;
    Q->tear = Q->front;
    p->next = NULL;
    Q->clear = clear;
    Q->isEmpty = isEmpty;
    Q->length = length;
    Q->getHead = getHead;
    Q->enQueue = enQueue;
    Q->deQueue = deQueue;
    Q->traverse = traverse;
    return Q;
}

void DestroySingleLinkedListQueue(SingleLinkedListQueue *Q){
    Q->clear(Q);
    free(Q->This);
    free(Q);
    Q = NULL;
}

static void clear(SingleLinkedListQueue *This){
    QNode *p = This->This->next;
    QNode *temp = NULL;
    while(p){
        temp = p;
        p = p->next;
        free(temp);
    } 
    p = This->This;
    p->next = NULL;
    This->front = p;
    This->tear = This->front;
}

static int isEmpty(SingleLinkedListQueue *This){
    QNode *p = This->This;
    if(p->next){
        return 0;
    }else{
        return 1;
    }
}

static int length(SingleLinkedListQueue *This){
    int j = 0;
    QNode *p = This->This->next;
    while(p){
        j++;
        p = p->next;
    } 
    return j;
}

static QNode *getHead(SingleLinkedListQueue *This){
    return This->front->next;
}

static int enQueue(SingleLinkedListQueue *This,QNode *n){
    if(!n) return -1;
    This->tear->next = n;
    n->next = NULL;
    This->tear = n;
    return 0;
}

static int deQueue(SingleLinkedListQueue *This,QNode *n){
    if(This->front == This->tear){
        n = NULL;
        return -1;
    }
    QNode *temp = This->front->next;
    *n = *(temp);
    This->front->next = temp->next; 
    if(This->tear == temp) This->tear = This->front;
    free(temp);
    return 0;
}

static int traverse(SingleLinkedListQueue *This,int (*visit)(QNode *n)){
    if(This->front == This->tear){
        return -1;
    }
    QNode *temp = This->front->next;
    while(temp){
        if(visit(temp) != 0) break;
        temp = temp->next;
    } 
    return 0;
}

SingleLinkedListQueue.h文件

/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef _SINGLELINKEDLISTQUEUE_H
#define _SINGLELINKEDLISTQUEUE_H
/* Includes ------------------------------------------------------------------*/
/* Exported types ------------------------------------------------------------*/
typedef struct QElemType{
    int id;
    char name[20];
}QElemType;     

typedef struct QNode{
    QElemType elem;  //存儲空間
    struct QNode *next;
}QNode,*Queueptr;

typedef struct SingleLinkedListQueue{
    QNode *This;
    Queueptr front; //隊頭
    Queueptr tear; //隊尾
    void (*clear)(struct SingleLinkedListQueue *This);
    int (*isEmpty)(struct SingleLinkedListQueue *This);
    int (*length)(struct SingleLinkedListQueue *This);
    QNode *(*getHead)(struct SingleLinkedListQueue *This);
    int (*enQueue)(struct SingleLinkedListQueue *This,QNode *n);
    int (*deQueue)(struct SingleLinkedListQueue *This,QNode *n);
    int (*traverse)(struct SingleLinkedListQueue *This,int (*visit)(QNode *n));
}SingleLinkedListQueue;

/* Exported macro ------------------------------------------------------------*/
SingleLinkedListQueue *InitSingleLinkedListQueue();
void DestroySingleLinkedListQueue(SingleLinkedListQueue *Q);

#endif

testSingleLinkedListQueue.c文件

#include <stdio.h>
#include <malloc.h>
#include "SingleLinkedListQueue.h"

char name[][3] = {"xw","xh","xm","xg","xl","xz"};

void strCopy(char *str_a,char *str_b){
    while(*str_b != '\0'){
        *str_a++ = *str_b++;
    }
    *str_a = '\0';
}

int printQnode(QNode *node){
    printf("id:%d,name:%s\n",node->elem.id,node->elem.name);
    return 0;
}

int main(void){
    int i;
    QNode *node = NULL;
    SingleLinkedListQueue *queue = InitSingleLinkedListQueue();
    printf("queue is empty:%d\n",queue->isEmpty(queue));
    for(i=0;i<6;i++){
        node = (QNode *)malloc(sizeof(QNode));
        node->elem.id = i;
        strCopy(node->elem.name,name[i]);
        queue->enQueue(queue,node);
    }
    queue->traverse(queue,printQnode);
    printf("queue is empty:%d\n",queue->isEmpty(queue));
    printf("queue length:%d\n",queue->length(queue));
    queue->clear(queue);
    for (i = 10; i < 16; i++){
        node = (QNode *)malloc(sizeof(QNode));
        node->elem.id = i;
        strCopy(node->elem.name,name[i-10]);
        queue->enQueue(queue,node);
    }   
    queue->traverse(queue,printQnode);
    while(queue->length(queue)){
        node = queue->getHead(queue);
        printf("present client: id=%d, name=%s\n",node->elem.id,node->elem.name);
        node = (QNode *)malloc(sizeof(QNode));
        queue->deQueue(queue,node);
        printf("client :id=%d,name=%s finish!\n",node->elem.id,node->elem.name);
        free(node);
        node = NULL;
    }
    DestroySingleLinkedListQueue(queue);
    return 0;
}

編譯：

gcc SingleLinkedListQueue.c SingleLinkedListQueue.h testSingleLinkedListQueue.c -o testSingleLinkedListQueue

運(yùn)行testSingleLinkedListQueue：

queue is empty:1
id:0,name:xw
id:1,name:xh
id:2,name:xm
id:3,name:xg
id:4,name:xl
id:5,name:xz
queue is empty:0
queue length:6
id:10,name:xw
id:11,name:xh
id:12,name:xm
id:13,name:xg
id:14,name:xl
id:15,name:xz
present client: id=10, name=xw
client :id=10,name=xw finish!
present client: id=11, name=xh
client :id=11,name=xh finish!
present client: id=12, name=xm
client :id=12,name=xm finish!
present client: id=13, name=xg
client :id=13,name=xg finish!
present client: id=14, name=xl
client :id=14,name=xl finish!
present client: id=15, name=xz
client :id=15,name=xz finish!