A deque
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!
and
rear-delete-deque!.
Show how to represent deques using pairs, and give implementations of the operations. All operations should be accomplished in Θ(1) steps.