昨天我们实现了队列，今天实现双端队列。
我们定义的抽象数据类型ADT——D，这个ADT支持如下方法：
- D.add_first(e): 在双端队列前面添加一个元素e。
- D.add_last(e): 在双端队列的后面添加一个元素e。
- D.delete_first(): 从双端队列中移除并返回第一个元素。如果双端队列为空，则出发异常。
- D.delete_last(): 从双端队列中移除并返回最后一个元素。如果双端队列为空，则出发异常。
这些是最基本的方法，但为了我们使用方便，还包含以下方法：
- D.first(): 返回但不移除第一个元素。如果双端队列为空，则出发异常。
- D.last(): 返回但不移除最后一个元素。如果双端队列为空，则出发异常。
- D.is_empty(): 如果双端队列为空则返回True。
- len(D): 返回双端队列中的元素个数。
这个与昨天一样还是使用适配器模式，使用环形数组实现。
根据昨天的队列可以很容易的扩展为双端队列。同样的为了我们观察双端队列，我还实现了str，打印内部数组。
这里唯一需要注意个就是这次我还是只用了三个成员变量——self._data、self._size、self._front。
至于双端队列的尾部索引，我们用下面的公式：
back = (self._front + self._size - 1) % len(self._data)
这样每次操作队尾都要算一次back，但是省掉了一个成员变量的空间。
据此实现的双端队列的每一个单独的操作的时间复杂的都是O(1)，当然同样是用了摊销的方法。因位不是每一步操作都需要改变地测数组的大小。
具体的是实现代码：
class Empty(Exception):
pass
class ArrayDeque:
DEFAULT_CAPACITY = 10
def __init__(self):
self._data = [None] * ArrayDeque.DEFAULT_CAPACITY
self._size = 0
self._front = 0
def __len__(self):
return self._size
def is_empty(self):
return self._size == 0
def add_first(self, e):
if self._size == len(self._data):
self._resize(2 * self._size)
self._front = (self._front - 1) % len(self._data)
self._data[self._front] = e
self._size += 1
def delete_first(self):
if self.is_empty():
raise Empty('Deque is empty!')
answer = self._data[self._front]
self._data[self._front] = None
self._front = (self._front + 1) % len(self._data)
self._size -= 1
if 0 < self._size <len(self._data) // 4:
self._resize(len(self._data)//2)
return answer
def add_last(self, e):
if self._size == len(self._data):
self._resize(2 * len(self._data)) # 当队列满了，就把队列容量扩大一倍
avail = (self._front + self._size) % len(self._data)
self._data[avail] = e
self._size += 1
def delete_last(self):
if self.is_empty():
raise Empty('Deque is empty!')
back = (self._front + self._size - 1) % len(self._data)
answer = self._data[back]
self._data[back] = None
self._size -= 1
if 0 < self._size <len(self._data) // 4:
self._resize(len(self._data)//2)
return answer
def first(self):
if self.is_empty():
raise Empty('Deque is empty!')
return self._data[self._front]
def last(self):
if self.is_empty():
raise Empty('Deque is empty!')
back = (self._front + self._size - 1) % len(self._data)
return self._data[back]
def _resize(self, capacity):
old = self._data
walk = self._front
self._data = [None] * capacity
for k in range(self._size):
self._data[k] = old[walk]
walk = (1 + walk) % len(old)
self._front = 0
def __str__(self):
return str(self._data)
测试：
if __name__ == '__main__':
deque = ArrayDeque()
deque.add_last(11)
deque.add_last(19)
print(deque)
deque.add_first(1)
deque.add_first(2)
print(deque)
deque.delete_first()
deque.delete_first()
deque.delete_first()
print(deque)
deque.add_last(23)
deque.add_last(33)
deque.add_last(1)
deque.add_last(73)
deque.add_last(3)
deque.add_last(10)
deque.add_last(43)
deque.add_last(33)
deque.add_last(90)
deque.add_last(53)
print(deque)
deque.delete_first()
deque.delete_first()
deque.delete_first()
print(deque)
deque.delete_first()
deque.delete_first()
deque.delete_first()
deque.delete_first()
print(deque)
输出：
image.png
明后天会写几道关于栈和队列的题目。下周就可以进入链表的学习了。
可以看到之前的将近20篇文章的都是讲的链表的题目，但是没有具体的讲链表本身是怎样的，所以我需要重新开始学习了。
看了之前自己没学之前实现的双端队列和队列，简直就是一坨屎。链表也是。
在python的标准collection模块中已经有了双端队列，它实现了除我们自己实现的方法之外的方法。它支持遍历，支持用下标访问队列的每一个元素，支持通过索引修改元素，统计某一元素数量，移除某一元素等非常实用的方法。只是命名并不像我们写的那样对称，有兴趣的可以去看一下官方文档。
加油！
