Tizeng's blog Ordinary Gamer

循环队列

2019-04-16
Tizeng

循环队列是一种队列的实现,它充分利用了连续数组的储存结构,如果队列的头部元素被pop,那前面的空间就空出来了,但加入元素时还是往尾部在加,如果我们把数组看成一个环,超出尾端范围的元素再按顺序放入数组开头,就能防止假溢出的发生。

假设队列的头指针为front,尾指针为rear(注意尾指针指向的不是最低端的元素,而是最底元素的后面一格,因为需要判断队列是否为空),数组大小为n,队列长度为len,由此我们有两个常见的下标关系:

rear = (front + len) % n

front = (rear + n - len) % n

(rear + 1) % n == front时,代表队列已满。

下面放一个LeetCode 622题目中实现的循环队列代码:



下一篇 图形学常识

Comments

Content