python-双端队列

双端队列
双端队列是一种类队列的数据结构，它支持在队列的头部和尾部都进行插入和删除操作
双端队列的抽象数据类型
D作为双端队列的实例
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)返回当前双端队列中的元素的个数

使用环形数组实现双端队列
1位置：
向双端队列中添加第一个元素front=(front-1)%len(data)
删除双端队列中的第一个元素front=(front+1)%len(data)
向双端队列的末尾添加一个元素last=(front+size)%len(data)
删除双端队列末尾的一个元素last=(front+size-1)%len

class Empty(Exception):
    pass #占位语句
class DeQueue:
    DEFAULT_CAPACITY=10
    def __init__(self):
        self._data=[None]*DeQueue.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 * len(self._data))
        avail=(self._front-1)%len(self._data)
        self._data[avail]=e
        self._front = avail
        self._size+=1
    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_first(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        answer=self._data[self._front]
        self._data[self._front]=None
        self._front=(self._front+1)%len(self._data)
        self._size-=1
        return answer
    def delete_last(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        de=(self._front+self._size-1)%len(self._data)
        answer=self._data[de]
        self._data[de]=None
        self._size-=1
    def first(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[self._front]
    def last(self):
        if self.is_empty():
            raise Empty("Stack is empty")
        return self._data[(self._front+self._size-1)%len(self._data)]
    def _resize(self,cap):
        old=self._data
        self._data=[None]*cap
        walk=self._front
        for k in range(self._size):
            self._data[k]=old[walk]
            walk=(1+walk)%len(old)
        self._front=0
    def print_deque(self):
        print(self._data)
Q=DeQueue()
Q.add_first(1)
Q.print_deque()
Q.add_first(2)
Q.print_deque()