外贸网站google推广,怎么查看网站是asp还是php,校园二级网站建设,工商注册登记系统队列和栈
前面讲了线性和链式结构#xff0c;如果你顺利掌握了#xff0c;下边的队列和栈就小菜一碟了。因为我们会用前两章讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似#xff0c;队列是先进先出结构(FIFO, first in first out)#xff0c; 栈是…队列和栈
前面讲了线性和链式结构如果你顺利掌握了下边的队列和栈就小菜一碟了。因为我们会用前两章讲到的东西来实现队列和栈。 之所以放到一起讲是因为这两个东西很类似队列是先进先出结构(FIFO, first in first out) 栈是后进先出结构(LIFO, last in first out)。
生活中的数据结构
队列。没错就是咱平常排队第一个来的第一个走
本章我们详细讲讲常用的队列
队列 Queue
这里卖个关子如果你熟悉了上两节讲的内容这里你会选取哪个数据结构作为队列的底层存储 还记得第一章讲的如何实现 ADT 吗我视频了说了三个注意事项
1.如何选用恰当的数据结构作为存储2.选取的数据结构能否满足 ADT 的功能需求3.实现效率如何
我们先来看看 list 可以不对照这个三个需求看看能否满足
1.我们选择了 list2.看起来队列需要从头删除向尾部增加元素也就是 list.pop(0) 和 list.append(element)3.嗯貌似 list.pop(0) 会导致所有其后所有元素向前移动一个位置O(n)复杂度。append 平均倒是O(1)但是如果内存不够还要重新分配内存。
你看使用了 list 的话频繁 pop(0) 是非常低效的。(当然list 实现还有另一种方式就是插入用 list.insert(0, item)删除用list.pop())
脑子再转转 我们第二章实现了 链表 LinkedList看看能否满足要求
1.这里选择 LinkedList2.删除头元素 LinkedList.popleft()追加 append(element)。都可以满足3.哇欧这两个操作都是 O(1) 的完美。
好 就用 LinkedList 了我们开始实现具体看视频。这次实现我们还将演示自定义异常和测试异常。
用数组实现队列
难道用数组就不能实现队列了吗其实还是可以的。只不过数组是预先分配固定内存的所以如果你知道了队列的最大长度也是 可以用数组来实现的。
想象一下队列就俩操作进进出出一进一出pop 和 push 操作。 似乎只要两个下标 head, tail 就可以了。 当我们 push 的时候赋值并且前移 headpop 的时候前移 tail 就可以了。你可以在纸上 模拟下试试。列队的长度就是 head-pop这个长度必须不能大于初始化的最大程度。
如果 head 先到了数组末尾咋办重头来呗只要我们保证 tail 不会超过 head 就行。
head 0,1,2,3,4 … 0,1,2,3,4 …
重头再来循环往复仿佛一个轮回。。。。 怎么重头来呢看上边数组的规律你如果还想不起来用取模估计小学数学是体育老师教的。
maxsize 5
for i in range(100):print(i % maxsize)我们来实现一个空间有限的循环队列。ArrayQueue它的实现很简单但是缺点是需要预先知道队列的长度来分配内存。
双端队列 Double ended Queue
看了视频相信你已经会实现队列了你可能还听过双端队列。上边讲到的队列 队头出尾尾进我们如果想头部和尾巴都能进能出呢 这就是双端队列了如果你用过 collections.deque 模块就是这个东西。他能高效在两头操作。
假如让你实现你能想起来嘛 似乎我们需要一个能 append() appendleft() popleft() pop() 都是 O(1) 的数据结构。
上边我们实现 队列的 LinkedList 可以吗貌似就差一个 pop() 最后边的元素无法实现了。 对我们还有双端链表。它有这几个方法
appendappendleftheadnode()tailnode()remove(node) # O(1)
啊哈似乎删除头尾都可以啦而且都是 O(1) 的完美。 交给你一个艰巨的任务实现双端队列 Deque ADT。你可以参考前几章的任何代码挑战一下这个任务别忘记写单元测试呦。当然如果没想出来也没关系后边我们实现栈的时候还会用到它那里我们会实现这个代码。
源码
# -*- coding: utf-8 -*-# NOTE: 从 array_and_list 第一章拷贝的代码
class Array(object):def __init__(self, size32):self._size sizeself._items [None] * sizedef __getitem__(self, index):return self._items[index]def __setitem__(self, index, value):self._items[index] valuedef __len__(self):return self._sizedef clear(self, valueNone):for i in range(len(self._items)):self._items[i] valuedef __iter__(self):for item in self._items:yield itemclass FullError(Exception):passclass ArrayQueue(object):def __init__(self, maxsize):self.maxsize maxsizeself.array Array(maxsize)self.head 0self.tail 0def push(self, value):if len(self) self.maxsize:raise FullError(queue full)self.array[self.head % self.maxsize] valueself.head 1def pop(self):value self.array[self.tail % self.maxsize]self.tail 1return valuedef __len__(self):return self.head - self.taildef test_queue():import pytest # pip install pytestsize 5q ArrayQueue(size)for i in range(size):q.push(i)with pytest.raises(FullError) as excinfo: # 我们来测试是否真的抛出了异常q.push(size)assert full in str(excinfo.value)assert len(q) 5assert q.pop() 0assert q.pop() 1q.push(5)assert len(q) 4assert q.pop() 2assert q.pop() 3assert q.pop() 4assert q.pop() 5assert len(q) 0思考题
你能用 python 的 deque 来实现 queue ADT 吗哪些经典算法里用到了队列呢
