循环队列CircularQueue

发表于 | 分类于 | 阅读次数 ℃
本文字数： 1.4k | 阅读时长 ≈ 1 分钟

循环队列可以看作是顺序队列的拓展。顺序队列在经过一系列的入队、出队操作之后，即使队列容量尚有空余，但因为队尾指针已经“走到尽头”，也要进行一些扩容操作，这样就浪费了许多空间。而“循环队列”可以充分利用空间，减少扩容操作。一般情况，循环列表都是基于数组实现的。

循环队列类

1
2
3
4
5
6
7
class CircularQueue(object):

	def __init__(self, capacity):
		self._items = [] # 基于列表实现
		self._capacity = capacity + 1
		self._head = 0
		self._tail = 0

需要指出的是，根据循环队列的特性，循环队列在队满的时候，队尾指针tail指向的位置实际上是不存储数据的。在同等条件下，顺序队列可以比循环队列多存储一个数据。但是为了方便调用者使用，我们在初始化容量时自动将capacity + 1，保证确实能存储传入进来的capacity个数据。

入队操作

入队操作要注意队满以及队尾指针的条件，(self._tail + 1) % self._capacity == self._head

1
2
3
4
5
6
def enqueue(self, value):
	if (self._tail + 1) % self._capacity == self._head:
		print('The queue is full! The data %s ignored!' % value)
		return False
	self._items.append(value)
	self._tail = (self._tail + 1) % self._capacity

出队操作

注意队空的条件self._head == self._tail，更新队首指针self._head = (self._head + 1) % self._capacity

1
2
3
4
5
6
def dequeue(self):
	if self._head == self._tail:
		print('The queue is empty')
		return False
	value = self._items[self._head]
	self._head = (self._head + 1) % self._capacity

查看队列

1
2
3
4
5
6
def printQueue(self):
	current = self._head
	while current != self._tail:
		print(self._items[current], end=',')
		current = (current + 1) % self._capacity
	print()

代码纠错

上述代码在程序执行存在错误！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
q = CircularQueue(5)
# 先入队5个
for i in range(5):
	q.enqueue(i)
# 此时队列：0,1,2,3,4,

# 再出队3个
for _ in range(3):
	q.dequeue()
#此时队列：3,4,

#再入队3个
for i in range(5,8):
	q.enqueue(i)
# 此时队列:3,4,5,0,1
# 6,7并没有写入进去，而且遍历数据时依旧是原来的数据
# 5写入成功是因为_tail在队满时本来就是None

更新后的代码见这里