python-031-实现队列结构-列表实现-动态改变大小

队列与前天的栈是表亲关系，也是一种基本的数据结构，与栈不同的是，它是遵循先进先出的原则(FIFO)，即只能在队首删除元素，队尾插入元素。

通常我们把插入元素的一段称为对尾，删除元素的一端称为队头。

这个很容易理解，想象肯德基排队点餐：你从队尾开始排队，正在点餐的人在队头。

队列在很多场景都有应用，且广泛的应用于很多计算机设备中，比如网络打印机，web服务器等。

同样的，先来分析下队列应该有哪些方法，对于队列Q，抽象数据类型ADT应该包含两种主要的方法出队列、进队列：

• Q.enqueue(e) 入队列，在队尾插入一个元素。
• Q.dequeue 出队列，在队列中有元素的情况下，将队头元素返回，并从队列中移除，在队列为空是，返回错误。
  对于我们使用来说他应该还包括以下的方法：
• Q.frist() 返回队列的队头元素，但是不移除队头元素，这有点像栈的pop()
• Q.is_empty() 如果队列为空则返回True
• len(Q) 返回队列中的元素个数
  为了方便我们学习这种数据结构，我还实现了str()方法，用来打印队列。

同样的定义了，队列为空的一个异常类，继承自Exception。

我们的队列名称叫做ArrayQueue，因为我们的队列使用列表实现的。

我们用数组实现队列有一个很不方便的地方就是出队列的时候，我们在设计时，是将列表的前面作为队头的，所以我们将元素出队列的时候，很简单的实现是pop（0）,但是我在前面学习的过程中了解到，pop（）不带参数的话时间复杂度为O(1)，但是如果有参数，传入索引，这会导致时间复杂度提高，变为O(n-k+1)，k是元素的索引，因为，如果我们弹出了前面的元素，列表就需要将这个洞补上，来保证整个列表的索引的正确性，而在我们实现队列出队列的情况下，如果用pop（0）则会大大增加时间复杂度，达到O(n)。越简单的实现，则效率越低。

我们用新的方法来避免调用pop（0）。用一个指代为空的指针替代这个出队列的元素，即用None来代替这个元素的位置，然后用一个成员变量self._front来标识队头的位置，这样的话对于出队操作就变成了O(1)，但是这样子出队列几次后就会变成这样：

队头     None    |    None    |    None    |    1    |    2    |    ········    |    6    |   队尾 

因为列表在底层是用数组实现的，随着进队出队的操作，这个列表将变的越来越大，最终的大小是这个队列自创建以来入队元素的总数量。这是很可怕的。
这种设计会对那种所需队列大小相对稳定，但经常入队出队的应用非常不友好，会造成很大的内存浪费。
于是我们就考虑利用前面的这些None，——循环的使用列表，当列表的随后一个位置被使用之后，将下一个保存的位置变为列表的前面。

这样就会出一个问题，就是前面的对头位置怎么确定，我们用这个公式 (self._front + 1) % N，N是当前底层数组的长度。比如，我们的队列底层数组的长度为10:

None    |    None    |    None    |    1（self._front）    |    2    |    3    |    6    |    7    |    8    |    9    |

现在我们要删除队头元素，self._front = (self._front + 1) % N => (self._front = 3 + 1) % 10 = 4，这样就得到了我们的新的队头。

如果要新插入一个元素 ：

1    |    None    |    None    |    1（self._front）    |    2    |    3    |    6    |    7    |    8    |    9    |

就要用(self._front + self._size) % N来确定新加入元素的索引。
这你自己算吧。

接下来就是动态数组的问题了，当所有的空间都满了，我们需要扩展空间，就需要将底层数组的大小变为原来的两倍，来降低下一次改变数组大小的概率。

如果队列中的元素个数小于等于空间的四分之一，就把底层数组的大小减小一半。

在改变数组大小的时候，我们其实是用了一个新的数组，将旧的数组值复制到新的数组中，但是这不是单纯的复制，因为我们之前在计算self._front时用到了当前数组的大小，如果直接复制们就会出大问题，所以我们需要将原来的队头放到新数组的第一个。

放出代码：

class Empty(Exception):
    pass


class ArrayQueue:
    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty('Queue is empty!')
        return self._data[self._front]

    def enqueue(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 dequeue(self):
        if self.is_empty():
            raise Empty('Queue 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 _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)   # 为了方便我们观察队列内部

这个队列的每一种操作的时间复杂度都为O(1)，其中入队出队的时间复杂的计算用到了会计学中摊销算法。这里自行百度。

下面我们来测试一下这个队列:

if __name__ == '__main__':
    my_queue = ArrayQueue()
    my_queue.enqueue(1)
    my_queue.enqueue(5)
    print(my_queue)
    my_queue.dequeue()
    my_queue.dequeue()
    print(my_queue)
    my_queue.enqueue(0)
    my_queue.enqueue(3)
    my_queue.enqueue(19)
    my_queue.enqueue(0)
    my_queue.enqueue(4)
    my_queue.enqueue(66)
    my_queue.enqueue(88)
    my_queue.enqueue(111)
    print(my_queue)
    my_queue.dequeue()
    my_queue.dequeue()
    my_queue.dequeue()
    my_queue.dequeue()
    print(my_queue)
    my_queue.enqueue(0)
    my_queue.enqueue(4)
    my_queue.enqueue(6)
    my_queue.enqueue(8)
    print(my_queue)
    my_queue.enqueue(11)
    print(my_queue)
    my_queue.enqueue(0)
    my_queue.enqueue(4)
    my_queue.enqueue(6)
    my_queue.enqueue(8)
    print(my_queue)

这涉及了所有需要改变队列底层数组大小的情况。

结果：

image.png

我在之前跟着书也写过队列，跟着个比起来，简直是垃圾——《python程序员算法宝典》张波、楚秦编著。

现在真是什么人都敢出来写书。
垃圾！！！！

我写文章也就自己看看，你们竟然厚颜无耻出书！！！！