数据结构之队列

doMore 1,352 2020-02-24

队列,就类似于收银台排队等待结账的一排顾客,先到的先结账(先进先出)。队列有队头(head)和队尾(tail),当有一个元素入队时,就把他放在队尾的位置,就想是一个新的顾客去结账总是排在最后。而出队的元素总是队前头的那个。

利用数组Q[1..n]来实现一个最多容纳 n-1 个元素的队列。该队列有一个属性Q.head指向队头,另一个属性Q.tail 则指向下一个元素将要插入的位置。队列中的元素存放位置
Q.head,Q.head+1,···,Q.tail-1,并在最后的位置“环绕”,感觉好像位置1紧邻在位置n后面形成一个环序。当Q.head=Q.tail时,队列为空,初始时 Q.head=Q.tail=1。如果试图从一个空队列中删除一个元素,则队列发生下溢;当Q.tail.next(Q.tail+1)=Q.head时,队列占满,如果此时像队列中插入一个值,则发生上溢。

队列.jpg

ENQUEUE及DEQUEUE执行程序如下(伪代码,忽略对上溢、下溢的检查):

假设 n=Q.length

ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.length
	Q.tail = 1
else q.tail = Q.tail + 1
DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.length
	Q.head = 1
else Q.head = Q.head + 1
return x

特别注意:两种操作的时间复杂度都是 Q(1)。