数据结构——队列

我们在使用手机的时候，偶尔都会碰到过卡住的时候，比如一个地方怎么点都没有用，屏幕也卡住不显示其他东西，但当你把卡住的App关闭掉之后，手机的操作显示就又恢复正常了，其实这就是因为操作系统中的各个程序的指令堆积在一起排队执行，而某一个App卡住的时候，大家都卡住了。

操作系统中是应用了一种数据结构来实现刚才提到的先到先执行的排队功能，这就是队列。

队列的定义

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

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端称为队头。假设队列 q = (q1,q2,q3,....qn)，那么我们一般定义q1就是队头，而qn自然为队尾了。这样我们在删除操作时，就从q1开始，而插入操作时则从qn开始。这也比较符合我们的生活习惯，我们在排队的时候，就是先到的人先出列，而晚到的人就在队尾排队。

循环队列

以前的文章，我写了线性表有顺序存储结构和链式存储结构，而同样，队列作为一种特殊的线性表，自然也存在这两种存储方式。首先我们先来看队列的顺序存储结构。

队列顺序存储结构的不足

和线性表的顺序存储结构的缺点一样，队列的若是采用常规的顺序存储结构，那么它在插入和删除时，每个元素都要依次向前或向后移动位置，此时的时间复杂度为O(n)。而当队列中队头之前的位置空出来，而队尾的元素已满时，明明在队头之前可能还有空间，但是按照顺序存储结构的判断，此时已经不能插入数据，再插入数据的话，整个数组就会溢出，而这种之前有空位，却插入到后面溢出位置的做法，我们称为 假溢出 。

循环队列的定义

所以为了解决这种假溢出的办法就是后面满了，就再从头开始，寻找之前空出来的空间，把数据存储进去，也就是头尾相接的循环。我们把队列这种头尾相接的顺序存储结构称为循环队列。

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

#define MAXSIZE 10   //循环队列的最大存储空间

/**
 *  函数运行状态代码
 */
#define SUCCESS 1
#define ERROR   0

typedef int Status ; //函数的运行状态 假设为int类型

typedef int QElemType; //QElemType的类型根据实际情况而定，这里假设为int

/**
 *  定义一个循环队列
 */
typedef struct{
    
    QElemType data[MAXSIZE];
    
    int front; //循环队列的头指针
    
    int rear;  //循环队列的尾指针
    
}sqQueue;

循环队列的初始化代码如下:

/**
 *  初始化一个循环队列
 *
 *  @param Q 循环队列的线性表
 *
 *  @return Status
 */

Status InitQueue (sqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    
    return SUCCESS;
}

我们来实现求一个循环队列的长度的功能，其实很简单，只要返回尾指针与头指针相减的数据就可以,当然，这里我们要考虑当循环了一遍之后头尾交换位置的情况

/**
 *  求循环队列的队列长度
 *
 *  @param Q 循环队列的线性表
 *
 *  @return length
 */
int QueueLength (sqQueue Q)
{
    return (Q.rear - Q.front +MAXSIZE) %MAXSIZE;
}

跟线性表一样，我们一般要完成插入和删除功能的代码，而实现部分如下:

循环队列的入队列操作代码:

/**
 *  循环队列的入队操作
 *
 *  @param Q 循环队列的线性表
 *  @param e 将要插入的数据
 *
 *  @return Sataus
 */
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 SUCCESS;
}

循环队列的出队列的操作代码 :

/**
 *  循环队列的出队列操作
 *
 *  @param Q 循环队列的线性表
 *  @param e 存储队头数据的元素
 *
 *  @return Status
 */
Status DeQueue (sqQueue * Q, QElemType *e)
{
    if (Q->front == Q->rear) {               //判断队列是否为空
        return ERROR;
    }
    *e = Q->data[Q->front];                  //将队头元素赋值给e
    Q->front = (Q->front + 1) %MAXSIZE;      //front指针后移一位
    
    return SUCCESS;
}

从上面的代码，我们能够分析出，单是顺序存储，若不是循环队列，算法的时间性能是不高的，但是循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。

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

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队列的头指针指向链队列的头结点，而尾指针指向终点结点。

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

链队列的结构为:

/**
 *  结点结构
 */
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
    
}QNode, *QueuePtr;

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

链队列的入队操作:

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

链队列的出队操作，其实就是头结点的后继结点出队，将头结点的后继改成它后面的结点，之后再释放要删除元素的内存，若链表除了头结点之外只剩下一个元素时，则要将rear指向头结点。

/**
 *  若队列不空，删除链队列的队头元素，并用e返回其值
 *
 *  @param Q 链队列
 *  @param e 删除的元素的数据
 *
 *  @return Status
 */
Status DeLinkeQueue (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);                        //释放p
    return SUCCESS;
}

循环队列和链队列的比较

循环队列和链队列的比较可以从两个方面来比较，首先从时间上，其实它们的基本操作都是常数时间，时间复杂度都为O(1)，不过循环队列是事先申请好空间的，而链队列是即时申请空间的所以链队列的每次申请和释放操作都会带来一定的性能消耗和时间开销。

从空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间的浪费的问题，而链队列则不存在这个问题。

总得来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

总结

我们在这里的总结，将栈和队列拿来比较。

• 栈（stack）是限定进在表尾进行插入和删除操作的线性表
• 队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

他们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端，因此它们各自有各自的技巧来解决这个问题。

对于栈来说，如果存储的数据类型相同的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化的利用数组的空间。

对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除的时间复杂度从O(n)变成了O(1)。

它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同。