数据结构学习——队列

队列

概念：

队列与栈相同，实现一个队列同样需要顺序表或者链表作为基础，因此一个队列既可以是顺序表也可以是链表。但与栈不同不同的是，队列是一种先进先出的线性表，只允许在一段进行插入操作、而在另一端进行删除操作。亦或者说，队列要求所有的数据从一端进入，从另一端离开。在队列中允许插入数据的一段叫做队尾，允许数据离开的一端叫做队头。

生活中场景：

相信我们都经历过电脑死机的现象，在死机时，我们经常会点击鼠标进行操作，当然电脑此时并不会出现任何操作，而过了一会，电脑又自动将刚才鼠标点击的操作进行了一遍。这就是因为在操作系统中，多个程序因为需要通过一个通道输出，而按先后次序排队等待造成的。一群人在排队买票，前面的人买好了离开，后面的人就要全部向前一步，补上空位。这些现象就采用了队列的数据结构。

假设队列是q=(a 1 ,a 2 ,......,a n )，那么a 1 就是队头元素，而a n 是队尾元素。这样我们就可以删除时，总是从a 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

顺序表队列：

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

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

因此我们可以得出一个结论：队列在出队时，一定会全部移动数据。如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

假设是长度为5的数组，初始状态，空队列左图所示，front与rear指针均指向下标为0的位置。然后入队a 1 、a 2 、a 3 、a 4 ，front指针依然指向下标为0位置，而rear指针指向下标为4的位置，如图右图所示。

出队a 1 、a 2 ，则front指针指向下标为2的位置，rear不变，如左图所示，再入队a 5 ，此时front指针不变，rear指针移动到数组之外。如右图所示。

假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。

顺序表循环队列：

解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。刚才的例子继续，rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了，如图所示。

接着入队a 6 ，将它放置于下标为0处，rear指针指向下标为1处，如左图所示。若再入队a 7 ，则rear指针就与front指针重合，同时指向下标为2的位置，如右图所示。

此时问题又出来了，我们刚才说，空队列时，front等于rear，现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？办法一是设置一个标志变量flag，当front==rear，且flag=0时为队列空，当front==rear，且flag=1时为队列满。办法二是当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如左图所示，我们就认为此队列已经满了，也就是说，我们不允许右图情况出现。

顺序表循环队列的顺序存储结构c语言描述：

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;
/* 循环队列的顺序存储结构 */
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;
  /* 将元素e赋值给队尾 */
  Q->data[Q->rear] = e;
  /* rear指针向后移一位置， */
  Q->rear = (Q->rear + 1) % MAXSIZE;
  /* 若到最后则转到数组头部 */
  return OK; 
}

顺序表循环队列的出队列操作代码：

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

链式队列：

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

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

链队列的结构描述：

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;
/* 结点结构 */
typedef struct QNode
{
  QElemType data;
  struct QNode *next;
} QNode, *QueuePtr;
/* 队列的链表结构 */
typedef struct
{
  /* 队头、队尾指针 */
  QueuePtr front, rear;
} LinkQueue;

链式队列入队操作：

入队操作时，其实就是在链表尾部插入结点。

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;
/* 结点结构 */
typedef struct QNode
{
  QElemType data;
  struct QNode *next;
} QNode, *QueuePtr;
/* 队列的链表结构 */
typedef struct
{
  /* 队头、队尾指针 */
  QueuePtr front, rear;
} LinkQueue;

链式队列入队操作：

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

链式队列出队操作：

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

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

循环队列与链队列的比较：

从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

例子：

实现一个链队列，任意输入一串字符串，以@为结束标志，然后将队列中的元素逐一取出，打印在屏幕上。

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode ,*QueuePtr;

typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

initQueue(LinkQueue *q){
    q->front = q->rear =(QueuePtr)malloc(sizeof(QNode));
    if(!q->front)
        exit(0);
    q->front->next=NULL;
}

EnQueue(LinkQueue *q,ElemType e){
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!q->front)
        exit(0);
    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

DeQueue(LinkQueue *q,ElemType *e){
    QueuePtr p;
    if(q->front == q->rear)
        return;
    p=q->front->next;
    *e = p->data;
    q->front->next = p->next;
    if(q->rear == p)
        q->rear = q->front;
    free(p);
}

main()
{
    ElemType e;
    LinkQueue q;
    initQueue(&q);
    printf("Please inpt a string into a queue:\n");
    scanf("%c",&e);
    while(e!='@'){
        EnQueue(&q,e);
        scanf("%c",&e);
    }
    printf("The string into the queue is:\n");
    while(q.front != q.rear){
        DeQueue(&q,&e);
        printf("%c",e);
    }
    printf("\n");
    getche();
}