赞
踩
假如公路上有一条单行隧道,所有通过隧道的车辆只允许从隧道入口驶入,从隧道出口驶出,不允许逆行,如下图:
因此,要想让车辆驶出隧道,只能按照它们驶入隧道的顺序,先驶入的车辆先驶出,后驶入的车辆后驶出,任何车辆都无法跳过它前面的车辆提前驶出:
队列(queue)是一种线性数据结构,它的特征和行驶车辆的单行隧道很相似;不同于栈的先入后出,队列中的元素只能先入先出(First In First Out,简称 FIFO),队列的出口端叫作队头(front),队列的入口端叫作队尾(rear)。
与栈类似,队列这种数据结构既可以用数组来实现,也可以用链表来实现;
用数组实现时,为了入队操作的方便,把队尾位置规定为最后入队元素的下一 个位置;
入队(enqueue)就是把新元素放入队列中,只允许在队尾的位置放入元素, 新元素的下一个位置将会成为新的队尾:
出队操作(dequeue)就是把元素移出队列,只允许在队头一侧移出元素,出队元素的后一个元素将会成为新的队头:
**问题:**如果像这样不断出队,队头左边的空间失去作用,那队列的容量岂不是越来越小了?
例如像下面这样:
**解决方案:**用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定
假设一个队列经过反复的入队和出队操作,还剩下2个元素,在“物理”上分布于数组的末尾位置。这时又有一个新元素将要入队,如下图:
在数组不做扩容的前提下,如何让新元素入队并确定新的队尾位置呢?
可以利用已出队元素留下的空间,让队尾指针重新指回数组的首位
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。