python堆栈与队列_python：用deque实现栈，队列和保存最后的N个元素

栈其实就是一个后进先出的队列，而一般意义的队列指的是FIFO队列（先进先出）。

标准库的collections.deque是个双端队列，可以轻松实现这两个数据结构。

ps：虽然直接用python的list去做也行，但会比deque慢一些，因为list的实际数据结构导致在首尾插入或删除元素的时候比deque慢。

栈的实现：

from collections import deque

dq = deque()  #初始化一个新的deque，当然也可以传入诸如list这样的东西初始化。

dq.pop()  # 弹栈并返回

dq.append(x)  #压栈

len(dq)  #栈大小

dq[-1]  #取栈顶元素

FIFO队列的实现：

dq = deque()  #初始化一个新的deque，当然也可以传入诸如list这样的东西初始化。

dq.popleft()  #队首弹出元素，并返回

dq.append(x)  #压元素入队列尾

len(dq)  #栈大小

dq[0]  #取队尾

dq[-1]取队首

当然除了实现栈和FIFO队列，本身就是个双端队列，两头都可以插入和删除元素，同时支持循环左移或右移操作。

dq.pop()   #队尾出 并返回

dq,popleft()  #队首出  并返回

len(dq)   #size

dq.append()   # 队尾入

dq.appendleft()  #队首入

dq.rotate(n)    #循环左移(n<0)  右移(n>0)

实现保存最后N个元素

即利用deque的maxlen参数，当deque已经满了，再在末尾插入元素的时候回删除队首的元素。

ps：在队列已满的时候，在队首插入元素，会把队尾的元素删除。

>>> from collections import deque

>>> dq = deque(maxlen=3)

>>> dq.append(1)

>>> dq.append(2)

>>> dq.append(3)

>>> dq

deque([1, 2, 3], maxlen=3)

>>> dq.append(4)

>>> dq

deque([2, 3, 4], maxlen=3)

>>> dq.append(5)

>>> dq

deque([3, 4, 5], maxlen=3)