数据结构重读 – 循环队列

队列也可以用顺序存储表示。定义还是一样的:从队尾rear推入元素。从头部head拿出元素,是FIFO。

与链式存储一致,我们仍然需要附设两个指针front和rear分别表示队列头元素和队列元素的位置。初始时front=rear=0是队列空的条件。

每当插入新的队列元素时,尾指针将增1.删除队列头元素时,头指针增加1。即非空队列中:头元素总是指向队首元素,而尾指针总是指向队尾元素的下一个位置。

除了基本的顺序存储外,我们还可以使用循环数组来构造一个循环队列

在循环队列中,上述head+1,rear+1变为(head+1)%MAX, (rear+1)%MAX。

队列空的条件还是head==rear,但是满的条件变为(rear+1)%MAX==head。为了这个Full的判断,循环队列将浪费一个空间,即可使用的空间只有MAX-1个。

代码如下:

Leave a Reply

Your email address will not be published.