python数据结构-双端队列-环状队列

python学习笔记之双端队列与环状队列

数据结构-双端队列-环状队列

双端队列

单端队列数据只能从队尾进，从队头出数据。而双端队列表示数据两端都可以进，两端都可以出。

双端队列里依然有两个指针，head和backend指针，一个空队列时，两个指针都指向None,从队列的前端增加数据时，head指针向前移动，当从队列的后端增加元素时，backend指针向后移动元素。如果要弹出队头的元素，那先把head往backend方向移动，再弹出此元素，如果要弹出队尾的元素，那行把backend指针往head所在方向移动。当两个指针指向None时，表示已是一个空队列。

可以用示意图来表达这一过程：

当删除元素元素时就是一个与增加元素相反的过程。

在python的标准库中已实现了双端队列，可以用from collections import deque导入。deque常用属性：

创建一个空队列：

In [10]: dq = deque()
In [11]: dq
Out[11]: deque([])

使用append方法向队列增加元素，此方法是向队尾增加元素：

In [12]: dq.append(4)
 
In [13]: dq.append(5)
 
In [14]: dq
Out[14]: deque([4, 5])
 

使用appendleft方法向队列增加元素，此方法是向队头增加元素：

In [15]: dq.appendleft(3)
 
In [16]: dq.appendleft(2)
 
In [17]: dq
Out[17]: deque([2, 3, 4, 5])
 

使用pop方法弹出一个元素，此方法是在队尾方向弹出元素：

In [18]: dq.pop()
Out[18]: 5
 
In [19]: dq
Out[19]: deque([2, 3, 4])
 

使用popleft方法弹出一个元素，此方法是在队头方向弹出元素：

In [20]: dq.popleft()
Out[20]: 2
 
In [21]: dq
Out[21]: deque([3, 4])
 

环状队列

环状队列在初始化时会生成指定数量的槽位，如果有元素append进来时，按照顺序依次加入到这些空的槽位中，当槽位被占满时，再append元素时会把最老的那个元素踢掉，再把新元素放入到槽位中，依此类推，环状队列最多保存初始化时指定槽位的数据。

可以用一个简单的示意图来表示：

标准库的deque不仅是双端队列，也是一个环状队列。只要初始化队列时加上maxlen参数即可。

创建一个槽位为5的环境队列：

In [23]: ring = deque(maxlen=5)
 
In [24]: ring
Out[24]: deque([])

向队列增加5个元素：

In [25]: ring.append(1)
 
In [26]: ring.append(2)
 
In [27]: ring.append(3)
 
In [28]: ring.append(4)
 
In [29]: ring.append(5)
 
In [30]: ring
Out[30]: deque([1, 2, 3, 4, 5])

当再增加一个元素时：

In [31]: ring.append(6)
 
In [32]: ring
Out[32]: deque([2, 3, 4, 5, 6])

第一个元素被覆盖了。