1、什么是队列？

队列（Queue）：具有一定操作约束的线性表。只能在一端插入，而在另一端删除。

• 数据插入：入队列（AddQ）
• 数据删除：出队列（DeleteQ）
• 先来先服务
• 先进先出：FIFO

 

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

类型名称：队列(Queue)
数据对象集：一个有0个或多个元素的有穷线性表。
操作集：长度为MaxSize的队列Q 属于 Queue，队列元素item 属于 ElementType
        1、Queue CreatQueue( int MaxSize )：生成长度为MaxSize的空队列；
        2、int IsFullQ( Queue Q, int MaxSize )：判断队列Q是否已满；
        3、void AddQ( Queue Q, ElementType item )： 将数据元素item插入队列Q中；
        4、int IsEmptyQ( Queue Q )： 判断队列Q是否为空；
        5、ElementType DeleteQ( Queue Q )：将队头数据元素从队列中删除并返回。

 

3、队列的顺序存储实现

               队列的顺序存储结构通常由一个一维数组和一个记录队列头元素位置的变量front

以及一个记录队列尾元素位置的变量rear组成。

#define MaxSize <储存数据元素的最大个数>
    struct QNode {
    ElementType Data[ MaxSize ];   //数据数组
    int rear;    //尾位置，实际是数组下标
    int front;   //头位置
};
typedef struct QNode *Queue;

 

循环队列

 

4、队列的链式存储实现

队列的链式存储结构也可以用一个单链表实现。插入和删除操作分别在链表的两头进行；

队列指针front和rear应该分别指向链表的哪一头？front指向链表的头

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(“队列空”); 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;
}