用单链表表示的链队列

队列

和栈相反，队列（Queue）是一种先进先出（First In First Out，缩写为FIFO）的线性表。

它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出输出操作。凡是申请输出的作业都从队尾进入队列。

在队列中，允许插入的一端叫队尾（rear），允许删除的一端则称为队头（front）。

除了栈和队列之外，还有一种限定性数据结构是双端队列（Deque）。
双端队列是限定插入和删除操作在表的两端进行的线性表。
在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。
而如果限定双端队列从某个端点插入的元素只能从该端点删除，则双端队列就蜕变为两个栈底相邻的栈了。

尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应用程序中远不及栈和队列有用。

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

运行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!