数据结构笔记 5. 队列

队列（queue）是只允许在一端进行插入操作， 而在另一端进行删除操作的线性表

队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾， 允许删除的一端称为队头。

1、 队列的抽象数据类型

ADT 队列(Queue)
Data
    同线性表。元素具有相同的类型，相信元素具有前驱和后继关系。
Operation
    InitQueue(*Q):初始化操作， 建立一个空队列Q。
    DestroyQueue(*Q)：若队列Q存在，则销毁它。
    ClearQueue(*Q):将队列Q清空
    QueueEmpty(Q); 若队列Q为空返回true,否则false.
    GetHead(Q, *e); 若队列Q存在且非空，用e返回队列Q的队头元素
    EnQueue(*Q, e); 若队列Q存在，插入新元素e到队列Q中并成为队尾元素。
    DeQueue(*Q, *e); 删除队列Q中队头元素，并用e返回其值。
    QueueLength(Q); 返回队列Q的元素个数
endADT

2. 循环队列

2.1 队列顺序存储的不足

我们假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)

与栈不同的是，队列元素的出队是在队头，即下标为0的位置，那也就是意味着队列中的所有元素都得向前移动，以保证队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)

2.2 循环队列的定义

我们把队列的这种头尾相接的顺序存储结构称为循环队列

队列满的条件是(rear+1)%queueSize == front(rear队尾指针，front队头指针, queueSize队列的的大小）

队列长度：(rear-front+queueSize)%queueSize

循环队列顺序存储结构代码如下：

typedef int QElemType; /*QElemType类型根据实际情况而定，这里假设为int*/
/*循环队列的顺序存储结构*/
typedef struct {
    QElemType data[MAXSIZE];
    int front;  /*头指针*/
    int rear; /*尾指针，若队列不空，指向队列尾元素的下一个位置*/
}SqQueue;

/*初始化一个空队列Q*/
Status InitQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear=0;
    return OK;
}

/* 返回Q的元素个数，也就是队列的当前长度*/
int QueueLength(SqQueue Q) {
    return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
}

/*若队列未满，则插入元素e为Q新的队尾元素*/
Status EnQueue(SqQueue *Q, QElemType e) {
    if( (Q->rear+1) %MAXSIZE == Q->front) /*队列满的判断*/
        return ERROR;
    Q->data[Q->rear] = e;   /*将元素e赋值给队尾*/
    Q->rear = (Q->rear+1)%MAXSIZE; /*rear指针向后移一位置,*/
                                   /*若到最后则转到数组头部*/
    return OK;
}

/*若队列不空，则删除Q中队头元素，用e返回其值*/
Status DeQueue(SqQueue *Q, QElemType *e) {
    if(Q->front == Q->rear) /*队列空的判断*/
        return ERROR;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE; /*front指针向后移一位置，若到最后则转到数组头部*/
    return OK;
}

3. 队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

我们将头指针指向链队列的头结点，而队尾指针指向终端结点。

空队列时，front和rear都指向头结点。

链队列的结构为：

typedef int QElemType; /*QElemType类型根据实际情况而定，这里假设为int*/
typedef struct QNode /*结点结构*/
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct   /*队列的链表结构*/
{
    QueuePtr front, rear; /*队头，队尾指针*/
}LinkQueue;

3.1 入队操作

/*插入元素e为Q的新的队尾元素*/
Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s)    /*存储分配失败*/
       exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;  /*把拥有元素e新结点s赋值给原队尾结点的后继*/
    Q->rear = s; /*把当前的s设置为队尾结点，rear指向s*/
    return OK;
}

3.2 出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点。

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/
Status DeQueue(LinkQueue *Q, QElemType *e) {
    QueuePtr p;
    if(Q->front == Q->rear)
        return ERROR;
    p = Q->front->next;   /*将欲删除的队头结点暂存给p*/
    *e = p->data;        /*将欲删除的队头结点的值赋值给e*/
    Q->front->next = p->next; /*将原队头结点后继p->next赋值给头结点后继*/
    if(Q->rear == p)  /*若队头是队尾，则删除后将rear指向头结点*/
        Q->rear = Q->front;
    free(p);
    return OK;
}

循环队列与链队列比较：

1. 基本操作都是常数时间O(1)的
2. 循环队列是事先申请好空间，使用期间不释放，而链队列，每次申请和释放结点会存在一些时间开销。
3. 空间上，循环队列固定长度，所以就有了存储元素个数和空间浪费的问题，链队列不存在这个问题。空间上链队列更加灵活。

在可以确定队列长度最大值的情况下，建议用循环队列，否则无法预估队列长度时，用链队列。