python-实现双端队列-循环数组

昨天我们实现了队列，今天实现双端队列。

我们定义的抽象数据类型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模块中已经有了双端队列，它实现了除我们自己实现的方法之外的方法。它支持遍历，支持用下标访问队列的每一个元素，支持通过索引修改元素，统计某一元素数量，移除某一元素等非常实用的方法。只是命名并不像我们写的那样对称，有兴趣的可以去看一下官方文档。

加油！