5. 环形队列

比较例 12.3 “用深度优先搜索解迷宫问题”的栈操作和例 12.4 “用广度优先搜索解迷宫问题”的队列操作可以发现,栈操作的top指针在Push时增大而在Pop时减小,栈空间是可以重复利用的,而队列的head、tail指针都在一直增大,虽然前面的元素已经出队了,但它所占的存储空间却不能重复利用,这样对存储空间的利用效率很低,在问题的规模较大时(比如100×100的迷宫)需要非常大的队列空间。为了解决这个问题,我们介绍一种新的数据结构--环形队列(Circular Queue)。把queue数组想像成一个圈,head和tail指针仍然是一直增大的,当指到数组末尾时就自动回到数组开头,就像两个人围着操场赛跑,沿着它们跑的方向看,从head到tail之间是队列的有效元素,从tail到head之间是空的存储位置,head追上tail就表示队列空了,tail追上head就表示队列的存储空间满了。如下图所示:

图 12.5. 环形队列

环形队列

习题

1、将例 12.4 “用广度优先搜索解迷宫问题”改用环形队列实现。然后回答:

  • 运行原来的程序要求queue数组至少有多长?不用跟踪程序的运行过程,你能很快答上来吗?

  • 改为环形队列之后要求queue数组至少有多长?