怎么用模板建网站,河源网站搭建费用,html5编辑器手机版,wordpress 添加小工具栈
栈这个词实际上在计算机科学里使用很多#xff0c;除了数据结构外#xff0c;还有内存里的栈区 #xff08;和堆对应#xff09;#xff0c;熟悉 C 系语言的话应该不会陌生。 上一章我们讲到了先进先出 queue#xff0c;其实用 python 的内置类型 collections.deque …栈
栈这个词实际上在计算机科学里使用很多除了数据结构外还有内存里的栈区 和堆对应熟悉 C 系语言的话应该不会陌生。 上一章我们讲到了先进先出 queue其实用 python 的内置类型 collections.deque 或者我们自己实现的 LinkedList 来实现它都很简单。 本章我们讲讲 后进先出的栈。
生活中的数据结构
栈。好比在桶里头放盘子先放的盘子放在了底下后来的盘子放在上边。你要拿的时候也是先拿最上边的。
栈其实也很简单因为基础操作就俩一个 push 和一个 pop咦咋和队列一样的 确实方法名字一样但是得到的结果可是不同的。
栈 ADT
上一章我介绍了我们怎样选取恰到的数据结构来实现新的 ADT你能想到这里我们应该使用之前提到的哪个数据结构来实现吗 你的大脑可能开始高(gui)速(su)旋转了上几章学过的 array, list, deque, LinkedList, CircularDoubleLinkedList, queue 等在大脑里呼啸而过这个时候可能已经一脸愁容了到底该选啥
还用问嘛当然是时间复杂度最小的啦大部分情况下空间都是够用的。 其实你会发现栈比队列还简单因为它只在顶上操作想象装着盘子的桶如果有一种数据结构能方便在尾部增减元素不就满足需求了吗。 这个时候如果你忘记了可以翻翻前几章看看哪个数据结构符合要求。
想一下似乎 CircularDoubleLinkedList 循环双端队列是满足的因为增删最后一个元素都是 O(1)。 不过看了下示例代码似乎没有 pop() 方法对因为我已经把实现 deque 作为思考题了。 如果之前你没写出来也没关系这里我们会再实现它。
视频里我们将借助 CircularDoubleLinkedList 实现 双端队列 Deque 并且用 Deque 实现 Stack。
Stack over flow 什么鬼
嗯stackoverflow 不是一个程序员问答网站吗没错。 函数的临时变量是存储在栈区的如果你不幸写了一个没有出口的递归函数就会这个错。不信你试试
def infinite_fib(n):return infinite_fib(n-1) infinite_fib(n-2)
infinite_fib(10)一大段输出之后就会出现异常 RecursionError: maximum recursion depth exceeded。 后边会讲到递归递归是初学者比较难理解的概念在树的遍历等地方还会看到它。
源码
# -*- coding: utf-8 -*-# NOTE: 这里拷贝的 double_link_list.py 里的代码from collections import dequeclass Node(object):def __init__(self, valueNone, prevNone, nextNone):self.value, self.prev, self.next value, prev, nextclass CircularDoubleLinkedList(object):循环双端链表 ADT多了个循环其实就是把 root 的 prev 指向 tail 节点串起来def __init__(self, maxsizeNone):self.maxsize maxsizenode Node()node.next, node.prev node, nodeself.root nodeself.length 0def __len__(self):return self.lengthdef headnode(self):return self.root.nextdef tailnode(self):return self.root.prevdef append(self, value): # O(1), 你发现一般不用 for 循环的就是 O(1)有限个步骤if self.maxsize is not None and len(self) self.maxsize:raise Exception(LinkedList is Full)node Node(valuevalue)tailnode self.tailnode() or self.roottailnode.next nodenode.prev tailnodenode.next self.rootself.root.prev nodeself.length 1def appendleft(self, value):if self.maxsize is not None and len(self) self.maxsize:raise Exception(LinkedList is Full)node Node(valuevalue)if self.root.next is self.root: # emptynode.next self.rootnode.prev self.rootself.root.next nodeself.root.prev nodeelse:node.prev self.rootheadnode self.root.nextnode.next headnodeheadnode.prev nodeself.root.next nodeself.length 1def remove(self, node): # O(1)传入node 而不是 value 我们就能实现 O(1) 删除remove:param node # 在 lru_cache 里实际上根据key 保存了整个node:if node is self.root:returnelse: #node.prev.next node.nextnode.next.prev node.prevself.length - 1return nodedef iter_node(self):if self.root.next is self.root:returncurnode self.root.nextwhile curnode.next is not self.root:yield curnodecurnode curnode.nextyield curnodedef __iter__(self):for node in self.iter_node():yield node.valuedef iter_node_reverse(self):相比单链表独有的反序遍历if self.root.prev is self.root:returncurnode self.root.prevwhile curnode.prev is not self.root:yield curnodecurnode curnode.prevyield curnode############################################################
# 分割线下边是本章 内容实现
############################################################class Deque(CircularDoubleLinkedList): # 注意这里我们用到了继承嗯貌似我说过不会用啥 OOP 特性的抱歉def pop(self):删除尾节点if len(self) 0:raise Exception(empty)tailnode self.tailnode()value tailnode.valueself.remove(tailnode)return valuedef popleft(self):if len(self) 0:raise Exception(empty)headnode self.headnode()value headnode.valueself.remove(headnode)return valuedef test_deque():dq Deque()dq.append(1)dq.append(2)assert list(dq) [1, 2]dq.appendleft(0)assert list(dq) [0, 1, 2]dq.pop()assert list(dq) [0, 1]dq.popleft()assert list(dq) [1]dq.pop()assert len(dq) 0class Stack(object):def __init__(self):self.deque Deque() # 你可以很容易替换为 python 内置的 collections.dequedef push(self, value):self.deque.append(value)def pop(self):return self.deque.pop()class Stack2(object):def __init__(self):self._deque deque()def push(self, value):return self._deque.append(value)def pop(self):return self._deque.pop()def empty(self):return len(self._deque) 0def test_stack():s Stack()s.push(0)s.push(1)s.push(2)assert s.pop() 2assert s.pop() 1assert s.pop() 0import pytest # pip install pytestwith pytest.raises(Exception) as excinfo: # 我们来测试是否真的抛出了异常s.pop()assert empty in str(excinfo.value)if __name__ __main__:test_stack()数据结构头脑风暴法
当我们不知道使用什么数据结构来解决问题的时候《程序员面试金典》这本书的第六章提到了一种方式叫做『数据结构头脑风暴法』。 这种笨方法就是快速过一遍数据结构的列表然后逐一尝试各种数据结构看看哪个最适合。
在你实现一个更高级的数据结构的时候如果脑子没有思路不妨尝试下这个方法迅速过一遍你所知道的数据结构看看哪种最适合。(从每个操作的时间复杂度和空间复杂度分析寻找最优解)
思考题
上一章我们用数组实现了队列其实也能用数组来实现栈你能自己用数组来实现一个栈的 ADT 吗实际上借助 python 内置的 list/collections.deque 结构就很容易实现一个栈请你尝试实现本章我们全部使用自己编写的数据结构而没用到 python 内置的数据结构。这里我们自己实现了 Deque你能用 python 内置的 collections.deque 实现栈吗有轮子能直接用的话看起来就简单多了这里我们为了学习数据结构的实现就避免了直接使用内置结构哪些经典算法里使用到了栈呢
Leetcode 练习
https://leetcode.com/problems/implement-queue-using-stacks/
