队列:先入先出(FIFO)表。
常用操作:
应用场景:
队列通常用来实现消息(任务)的快速读写,即消息队列。消息队列的常用来解决如下问题:
实现方式:
使用循环数组实现一个队列:
1 from array import array
2
3 class arr_queue(object):
4 def __init__(self, maxsize):
5 self._array = array('i', range(maxsize))
6 self._head = 0
7 self._tail = 0
8 self._length = 0
9 self._maxsize = maxsize
10
11 def enqueue(self, value):
12 if self._length >= self._maxsize:
13 raise Exception('queue is full')
14 self._array[self._tail] = value
15 self._length += 1
16 self._tail += 1
17 if self._tail >= self._maxsize:
18 self._tail = 0
19
20 def dequeue(self):
21 if self._length <= 0:
22 raise Exception('queue is empty')
23 value = self._array[self._head]
24 self._length -= 1
25 self._head += 1
26 if self._head >= self._maxsize:
27 self._head = 0
28 return value
29
30 def __len__(self):
31 return self._length