队列的定义

与栈相反，队列(queue)是一种**先进先出**(first in first out,缩写为FIFO)的线性表。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做**队尾**(rear)，允许删除的一端叫做**队头**(front)。

抽象数据类型定义

ADT Queue{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }
约定a1为队列头，an为队列尾。
}

队列的代码实现

顺序队列(SqQueue)

#include <stdio.h>
#include <stdlib.h>
#define MAXQSIZE 100 //队列最大长度
#define OK 1
#define ERROR 0
typedef int QElemType;
typedef int Status;
//队列定义
typedef struct
{
    QElemType *base;
    int front;
    int rear;
}SqQueue;
//初始化空队列
Status Init(SqQueue *Q)
{
    Q->base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if(!Q->base) return ERROR;
    Q->front = Q->rear = 0;
    return OK;
}
//队满
Status IsFull(SqQueue *Q)
{
    if((Q->rear+1)%MAXQSIZE == Q->front)
        return OK;
    return ERROR;
}
//队空
Status IsEmpty(SqQueue *Q)
{
    if(Q->front == Q->rear)
        return OK;
    return ERROR;
}
//入队
Status EnQueue(SqQueue *Q,QElemType e)
{
    if(IsFull(Q))
        return ERROR;
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear+1)%MAXQSIZE;
    return OK;
}
//出队
Status DeQueue(SqQueue *Q,QElemType *e)
{
    if(IsEmpty(Q))
        return ERROR;
    (*e) = Q->base[Q->front];
    Q->front = (Q->front+1)%MAXQSIZE;
    return OK;
}

queue

链队列(LinkQueue)

#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
typedef int QElemType;
typedef int Status;
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front; //队头指针
    QueuePtr rear; //队尾指针
    int length;
}LinkQueue;
//初始化
Status Init(LinkQueue *Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q->front) return ERROR;
    Q->front->next = NULL;
    length = 0;
    return OK;
}
//入队
Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if(!p) return ERROR;
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    length++;
    return OK;
}
//出队
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if(IsEmpty(Q)) return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(p == Q->rear) Q->front = Q->rear;
    free(p);
    length--;
    return OK;
}
//队空
Status IsEmpty(LinkQueue Q)
{
    if(Q->front ==     Q->rear) return OK;
    return ERROR;
}
//销毁
Status Destroy(LinkQueue Q)
{
    while(Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

LinkQueue

DONE！

所示代码如有错误请多加指正，谢谢