(三）队列（queue)

队列也是具有一定操作约束的线性表。它和堆栈不同，它只可在一端插入（Add），另一端删除（Delete）

其主要特征是先进先出

一、队列的抽象数据类型描述

        数据对象集：一个有零个或多个元素的有穷线性表

        操作集：生成一个队列、判断队列是否已满、插入、判断队列是否为空、删除、

二、队列的顺序存储

        队列的顺序存储最简单的方法是用数组进行存储，可以用一个一维数组还有两个变量front和rear来存储数组。但是这种方法随着出队入队操作的进行，会使整个队列整体想前、后移动。有时候可能会造成“假溢出”的现象。

为解决这个问题我们在队列的顺序存储中一般采用循环队列的方式：rear和front到达数组端点时，能折回到数组开始处。

采用这种方法第一个要考虑的问题时如何初始化front和rear

可以将front和rear都初始化为0，插入一个元素时rear加1，删除一个元素时front加1

但是这种方法又存在了一个问题，当front等于rear时是表示队列为空还是队列为满呢

为解决这个问题可以用两个方法，第一种，可以增加一个变量tag来标记最后一次操作是删除还是插入；第二种，可以只存储n-1个元素，最后一个元素不用考虑，这样一来队列空的条件仍然是：rear等于front，队列满的条件就会是：（rear+1）%数组长度等于front

实现结构的代码表述如下：

#define MaxSize <100>

typedef struct
{
    ElementType Data[MaxSize];
    int rear;
    int front;
}Queue;

插入操作代码实现：

void AddQ(Queue *PtrQ,ElementType item)
{
    if ((PtrQ->rear+1)%MaxSize==PtrQ->front)     //判断队列是否已满
    {
        printf("队列已满");
        return;
    }
    PtrQ->rear = (PtrQ->rear+1)%MaxSize;    //队尾加1
    PtrQ->Data[PtrQ->rear] = item;     //数据存入Data中
}

删除操作代码实现：

ElementType DeleteQ(Queue *PtrQ)
{
    if (PtrQ->rear == PtrQ->front)     //判断队列是否为空
    {
        printf("队列为空")；
        return ERROR;
    }
    else
    {
        PtrQ->front = (PtrQ->front-1)%MaxSize;    //队首减1
        return PtrQ->Data[PtrQ->front];
    }
}

三、队列的链式存储

        队列链式存储时，队列的头必须指向链表的头结点，队列的尾必须指向链表的尾节点

        代码实现：

typedef struct Node *PtrToNode;
struct Node { /* 队列中的结点 */
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode Position;
 
struct QNode {
    Position Front, Rear;  /* 队列的头、尾指针 */
    int MaxSize;           /* 队列最大容量 */
};
typedef struct QNode *Queue;
 
bool IsEmpty( Queue Q )
{
    return ( Q->Front == NULL);
}
 
ElementType DeleteQ( Queue Q )
{
    Position FrontCell; 
    ElementType FrontElem;
     
    if  ( IsEmpty(Q) ) {
        printf("队列空");
        return ERROR;
    }
    else {
        FrontCell = Q->Front;
        if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
            Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
        else                     
            Q->Front = Q->Front->Next;
        FrontElem = FrontCell->Data;
 
        free( FrontCell );  /* 释放被删除结点空间  */
        return  FrontElem;
    }
}