面向对象编程章节中的练习12.10 我们通过创建一个函数queue-maker来构建一个队列数据结构。 在此函数中,我们处理发送到对象的消息 例如,当我们发送对象时,消息“enqueue”和操作数“a”=>“a”将被推送到队列
(define q (queue-maker))
(q 'enqueue 'a)
需要做的是为消息“enqueue-list”添加处理程序,操作数将是一个列表。这会将列表中的所有项目添加到队列中
(q 'enqueue-list '(b c d))
这里的问题是为什么我们不使用追加!修改队列的函数?
使用
append!
对于书中给出的队列的实现来说都是一场灾难。
练习 12.10 要求您使用程序 12.15 中定义的版本。这是使用尾指针来提高
enqueue!
效率的版本。在此实现中,您可以通过两种方式使用
append!
:您可以直接
append!
进入队列列表。 (a) 不使用尾指针,因此必须遍历整个队列,更糟糕的是,(b) 不会 update尾指针,从而破坏数据结构,因此下次调用时
enqueue!
您将丢失刚刚添加的所有内容。您可以通过更新尾部指针以指向新的最后一个缺点来修复此问题,这否定了使用
append!
的任何假定的性能优势。但这无论如何都不安全您可以
append!
指向指向队列最后一个cons的尾指针。这更好,但您仍然必须记住更新尾指针以指向新的最后一个 cons,因此您“仍然”必须遍历要附加的列表。然而,这仍然不安全,请参见下文。
两者都都不安全。
如果您使用早期的队列实现(程序 12.13 中的实现),看起来使用append!
会起作用:现在无需担心尾指针。但这也是不安全的。 这就是为什么所有这些方法都不安全。
考虑这段代码:
(define (enqueue-list-twice q l)
(q 'enqueue-list! l)
(q 'enqueue-list! l) ;or just enqueue! anything
l)
如果使用 append!
来实现
enqueue!
会发生什么?好吧,第一次这样做时,您最终会得到一个尾部为
l
的队列。这不是 l
的副本,它是
l
。第二次执行此操作时,
append!
将粉碎此列表中的最后一个缺点,因此
l
的最后一个缺点将是...l
。因此,这种方法为您设置了一个令人讨厌的陷阱:它将其参数之一作为队列的一部分隐藏起来,
然后将被破坏性地修改。太恶心了。
您甚至可以通过制作列表的显式副本来解决此问题,这再次否定了使用append!
的优势,因为无论如何您都必须遍历它才能复制它。当您完成所有这些工作时,最好只是实施该事情,而不必自始至终事后猜测
append!
。最明显、安全的方法就是通过重复调用
enqueue-list!
来实现
enqueue!
。