时间戳

首页 > 解决方案 > 为什么这个函数被认为是队列的实现？

python-3.x - 为什么这个函数被认为是队列的实现？

问题描述

这些示例来自 Mark Lutz 的 Learning Python。第一个函数是一个递归函数，用于遍历具有任意嵌套的列表以计算元素的总和：

def sumtree_rec(L):
    tot = 0
    for x in L:
        if not isinstance(x, list):
            tot += x
    else:
        tot += sumtree(x)
    return tot

第二个函数实现了同样的功能，但没有递归：

def sumtree_notrec(L):
    tot = 0
    items = list(L)
    while items:
        front = items.pop(0)
        if not isinstance(front, list):
           tot += front
        else:
            items.extend(front)
    return tot

我相信我了解这两个功能的工作原理。我追踪了 sumtree_notrec 中的 L 如何随着代码体的每次迭代而变化，并且它与书中的输出相匹配。我也认为我理解为什么将递归视为堆栈，因为每个级别都会将调用帧推送到运行时堆栈，并且在调用完成时弹出。

我不明白的是为什么递归函数被称为 FIFO 队列？我查了一下，感觉我理解数据结构代表什么，我只是不明白它们是如何应用于这个函数的。我还发现了这个资源，它对调用堆栈做了一些解释：https ://www.cs.ucsb.edu/~pconrad/cs8/topics.beta/theStack/02/

例如，如果我在非递归函数中跟踪 L（不是实际代码，只是一个表示）：

L --> [1,[2,[3,4],5],6,[7,8]]
L --> (1) is popped [[2,[3,4],5],6,[7,8]]
L --> [2,[3,4],5] is not popped
L --> [6,[7,8],2,[3,4],5]

ETC...

为什么叫队列？什么对象是“先入”然后是“先出”？

标签： python-3.xdata-structures

解决方案

递归版本是深度优先搜索。非递归版本是广度优先搜索。在非递归版本中，items列表被视为队列。每当从 中弹出一个列表时items，该列表中的各个元素都会添加到items.

这就是队列的简单定义：元素被添加到后面并从前面移除。

推荐阅读