队列和栈
本节讲解的队列与栈,如果你对之前的线性和链式结构顺利掌握了,那么下边的队列和栈就小菜一碟了。因为我们会用前两节讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似,队列是先进先出结构(FIFO, first in first out), 栈是后进先出结构(LIFO, last in first out)。
生活中的数据结构:
- 队列。没错就是咱平常排队,第一个来的第一个走
本章我们详细讲讲常用的队列
队列 Queue
如果你熟悉了上两节讲的内容,这里你会选取哪个数据结构作为队列的底层存储?
class Queue():
def __init__(self):
self.item = DoubleLinkedList()
def push(self, value):
self.item.append(value)
def pop(self):
value = self.item.top_node().value
self.item.remove(value)
return value
用数组实现队列
难道用数组就不能实现队列了吗?其实还是可以的。只不过数组是预先分配固定内存的,所以如果你知道了队列的最大长度,也是 可以用数组来实现的。
想象一下,队列就俩操作,进进出出,一进一出,pop 和 push 操作。 似乎只要两个下标 head, tail 就可以了。 当我们 push 的时候赋值并且前移 head,pop 的时候前移 tail 就可以了。你可以在纸上 模拟下试试。列队的长度就是 head-pop,这个长度必须不能大于初始化的最大程度。
如果 head 先到了数组末尾咋办?重头来呗,只要我们保证 tail 不会超过 head 就行。
head = 0,1,2,3,4 ... 0,1,2,3,4 ...
重头再来,循环往复,仿佛一个轮回。。。。 怎么重头来呢?看上边数组的规律你如果还想不起来用取模,估计小学数学是体育老师教的。
maxsize = 5
for i in range(100):
print(i % maxsize)
我们来实现一个空间有限的循环队列。ArrayQueue,它的实现很简单,但是缺点是需要预先知道队列的长度来分配内存。
class Queue:
def __init__(self, maxsize=4):
self.item = Array(maxsize)
self.head = 0
self.end = 0
self.maxsize = maxsize
def push(self, value):
self.item[self.head % self.maxsize] = value
self.head += 1
def pop(self):
value = self.item[self.end % self.maxsize]
self.end +=1
return value
双端队列 Double ended Queue
你可能还听过双端队列。上边讲到的队列 队头出,尾尾进,我们如果想头部和尾巴都能进能出呢? 这就是双端队列了,如果你用过 collections.deque 模块,就是这个东西。他能高效在两头操作。
假如让你实现你能想起来嘛? 似乎我们需要一个能 append() appendleft() popleft() pop() 都是 O(1) 的数据结构。
上边我们实现 队列的 LinkedList 可以吗?貌似就差一个 pop() 最后边的元素无法实现了。 对,我们还有双端链表。它有这几个方法:
- append
- appendleft
- headnode()
- tailnode()
- remove(node)
栈 Stack
from collections import deque
class Stack():
def __init__(self):
self.item = deque()
def add(self,value):
self.item.append(value)
def pop(self):
return self.item.pop()
练习
- 使用 python 的 deque 来实现 queue ADT 吗?
- 是否能完成循环队列