Exercise 3.23: A
deque (“double-ended
queue”) is a sequence in which items can be inserted and deleted at either the
front or the rear. Operations on deques are the constructor make-deque,
the predicate empty-deque?, selectors front-deque and
rear-deque, and mutators front-insert-deque!,
rear-insert-deque!, front-delete-deque!,
rear-delete-deque!. Show how to represent deques using pairs, and give
implementations of the operations.
All operations should be accomplished in Θ
(
1
) steps.
练习 3.23：双端队列（deque，即 “double-ended queue” 的缩写）是一种序列，其中的项可以从前端或后端插入和删除。双端队列上的操作包括：构造函数 make-deque，谓词 empty-deque?，选择函数 front-deque 和 rear-deque，以及变动函数 front-insert-deque!、rear-insert-deque!、front-delete-deque!、rear-delete-deque!。请说明如何用序对来表示双端队列，并给出各操作的实现。所有操作都应在 Θ(1) 步内完成。