队列（Queue）

队列是具有一定操作约束的线性表，只能在一端插入，而在另一端删除。长度为MaxSize的队列，队列元素item
数据插入：入队（AddQ）
数据删除：出队（DeleteQ）
先来先服务，先进先出（FIFO）
【队列的顺序存储实现】

/* 队列的顺序存储结构通常是由一个一维数组
和一个记录队列头元素位置的变量front
以及一个记录队列尾元素的变量rear组成 */
/* 定义队列 */
#define MaxSize 100
struct QNode{
    ElementType Data[MaxSize];
    int rear;   //数组下标，队列头元素下标-1
    int front;  //数组下标，队列尾元素下标
};
typedef struct QNode * Queue;


/* 入队 */
void AddQ(Queue PtrQ,ElementType item)
{
    if((PtrQ->rear+1)%MaxSize==PtrQ->front){
        printf("the Queue full");
        return;
    }
    PtrQ->rear=(PtrQ->rear+1)%MaxSize;
    PtrQ->Data[PtrQ->rear]=item;
}

/* 出队 */
ElementType DeleteQ(Queue PtrQ)
{
    if(PtrQ->front==PtrQ->rear){
        printf("the Queue empty");
        return ERROR;
    }else{
        PtrQ->front=(PtrQ->front+1)%MaxSize;
        return PtrQ->Data[PtrQ->front];
    }
}

【队列的链式存储实现】

/* 队列的链式存储结构也可以用一个单链表实现，
插入和删除操作分别在链表的两头进行
front 指向链表的头 rear指向链表的尾 */
/* 定义链表队列 */
struct Node{
    ElementType Data;
    struct Node * Next;
};
struct QNode{          //链队列结构
    struct Node *rear; //指向队尾节点
    struct Node *front; //指向队头节点
};
typedef struct QNode * Queue;
Queue PtrQ;

/* 不带头节点的链式队列出队操作 */
ElementType DeleteQ(Queue PtrQ)
{
    struct Node *FrontCell;
    ElementType FrontElem;

    if(PtrQ->front == NULL){
        printf("the Queue empty");
        return ERROR;
    }
    FrontCell=PtrQ->front;
    if(PtrQ->front==PtrQ->rear) //队列只有一个元素
        PtrQ->front=PtrQ->rear=NULL; //删除后队列置空
    else
        PtrQ->front=PtrQ->front->Next;
    FrontElem=FrontCell->Data;
    free(FrontCell);
    return FrontElem;
}