前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

4.11队列顺序存储的不足

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

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

在现实中也是如此，一群人在排队买票，前面的人买好了离开，后面的人就要全部向前一步，补上空位，似乎这也没什么不好。

那能不能出队列的时候，后面的元素不存储再数值的前n个单元这一条件，出队列的性能就会大大增加。也就是说，对头不需要一定在下标为0的位置

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

假设是长度为5的数组，初始状态，front 与rear指针均指向下标为0的位置。然后入队a1、a2、a3、 a4, front 指针依然指向下标为0位置，而rear指针指向下标为4的位置

出队a1、a2, 则front指针指向下标为2的位置，rear 不变,再入队as,此时front指针不变，rear 指针移动到数组之外。嗯?数组之外,那将是哪里?

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

现实当中，你上了公交车，发现前排有两个空座位，而后排所有座位都已经坐满，你会怎么做?立马下车，并对自己说，后面没座了，我等下一辆?没有这么笨的人，前面有座位，当然也是可以坐的，除非坐满了，才会考虑下一辆。

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

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

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

链队列的结构为:

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

4.12.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;
 }

4.12.2队列的链式存储结构一出队操作

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

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

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

4.13总结回顾

栈(stack) 是限定仅在表尾进行插入和删除操作的线性表。

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

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

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

对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是0(n)的时间复杂度变成了0(1)。 它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同