一，队列的定义
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
图 1 队列的实现形式示意图
二，队列的实现形式
1，队列的链式存储结构
队列既可以用链表实现，也可以用顺序表实现。跟栈相反的是，栈一般我们用顺序表来实现，而队列我们常用链表来实现，简称链队列。
定义的结构体如下：
typedef struct QNode { ElemType data; struct QNode *next; }QNode, *QueuePrt; typedef struct { QueuePrt front,rear; // 队头、尾指针 }LinkQueue;我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。
图2 链队列的结构图
当为空队列的时候，front与rear都会指向头结点。
2，创建一个队列
创建一个队列要完成两个任务：一是在内存中创建一个头结点，二是将队列中的头结点和尾指针都指向这个生成的头结点，因为此时是空队列。
initQueue(LinkQueue *q) { q->front = q->rear = (QueuePrt)malloc(sizeof(QNode)); if(!q->front) exit(0); q->front->next = NULL; }
3，入队列操作
入队列的操作过程如图3所示，要插入的元素是e2结点，这个时候将rear指针指向e2结点，则p指针失去作用，就如第三步显示的那样成功入队列。
图3 入队列示意图
InsertQueue(LinkQueue *q, ElemType e) { QueuePrt p; P = (QueuePrt)malloc(sizeof(QNode)); if( p == NULL) exit(0); p->data = e; p->next =NULL; q->rear->next = p; q->rear = p; }4，出队列操作
出队列操作是将队列中的第一个元素移出，队头指针是不需要改变的，改变头结点的next指针即可。
图4 出队列的操作示意图
出队列有一个特殊情况，如果原队列只有一个元素，这个时候就需要处理一下尾部指针。
图5 只有一个元素的时候
DeleteQueue(LinkQueue *q, ElemType *e) { QueuePrt p; if( q->front == q->rear ) return; p = q->front->next; *e = p->data; q->front->next = p->next; if( q->rear == p) q->rear = q->front; free(p); }
