一、什么是队列

队列（Queue）是具有一定约束的线性表，它只能在 一端插入（入队，AddQ）而在 另一端删除（出队，DeleteQ）。它具有 先进先出（FIFO）的特性。

队列的抽象类型描述：

类型名称：队列（Quene）
数据对象集：一个有 0 个或多个元素的有穷线性表
操作集：长度为 MaxSize 的队列 Q ∈ Quene，队列元素 item ∈ ElementType

Queue CreateQuene(int MaxSzie);         // 生成长度为MaxSize的空队列
int IsFullQ(Queue Q,int MaxSize);       // 判断队列Q是否已满
void AddQ(Queue Q,ElementType item);    // 将数据元素item插入队列Q中
int IsEmptyQ(Quenu Q);                  // 判断队列Q是否为空
ElementType DeleteQ(Queue Q);           // 将队头数据元素从队列中删除并返回

二、队列的顺序存储实现

队列的顺序存储结构通用由一个一维数组和一个记录 队列头元素位置 的变量 front 以及一个记录 队列尾元素位置 的变量 rear 组成。

#define MaxSize         // 存储数据元素的最大个数
struct QNode
{
    ElementType Data[MaxSize];
    int rear;
    int front;
};

typedef struct QNode *Queue;

【1】、入队（AddQ）

void AddQ(Queue PtrQ,ElementType item)
{
    if((PtrQ->rear+1) % MaxSize == PtrQ->front)
    {
        printf("队列已满\n");
        return;
    }

    PtrQ->rear = (PtrQ->rear + 1) % MaxSize;
    PtrQ->Data[PtrQ->rear] = item;
}

循环队列当存储空间全部使用时，read 等于 front，此时无法表示循环队列是空的还是满的，此时解决方法有两种：第一种是 使用额外的标记：Size 或者 tag域，Size 用来记录当前循环队列中元素的个数。第二种方式是 仅使用 n-1 个数组空间；

【2】、出队（DeleteQ）

ElementType DeleteQ(Queue PtrQ)
{
    if(PtrQ->front == PtrQ->rear)
    {
        printf("队列空\n");
        return ERROR;
    }
    else
    {
        PtrQ->front = (PtrQ->font + 1) % MaxSize;
        return PtrQ->Data[PtrQ->front];
    }
}

三、队列的链式存储实现

队列的链式存储结构可以用一个单链表实现。插入（入栈，AddQ）和删除（出栈，DeleteQ）操作分别在链表的两头进行。队列头指针 front 指向 链表头，队列尾指针 rear 指向 链表尾。

typedef struct QNode *Queue;

struct Node
{
    ElementType Data;
    struct Node *Next;
};

struct QNode                // 链队列结构
{
    struct Node *rear;      // 指向队尾结点
    struct Node *front;     // 指向队头结点
};

Queue PtrQ;

【1】、入队（AddQ）

不带头节点的链式队列入队操作：

void AddQ(Queue PtrQ,ElementType item)
{
    struct Node *temCell;

    temCell = (struct Node *)malloc(sizeof(struct Node));
    temCell->Data = item;
    tempCell->Next = NULL;

    if(PtrQ->font == NULL)                      // 如果是第一个结点
    {
        PtrQ->rear = PtrQ->front = temCell;     // 队列的头指针和尾指针都指向第一个结点
    }
    else
    {
        PtrQ->rear->Next = temCell;             // 之前的链表的尾结点连接新结点，形成链
        PtrQ->rear = temCell;                   // 队列的尾结点指向新结点
    }
}

【2】、出队（DeleteQ）

不带头节点的链式队列出队操作：

ElementType DeleteQ(Queue PtrQ)
{
    struct Node *FrontCell;
    ElementType FrontElem;

    if(PtrQ->front == NULL)
    {
        printf("队列已空\n");
        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;
}

JZTXT

05. 队列

一、什么是队列

二、队列的顺序存储实现

三、队列的链式存储实现