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.


There are no comments yet.

Authentication required

You must log in to post a comment.

Login
(define dq (make-deque))

(check-true (empty-deque? dq))

(front-insert-deque! dq 'a)
(check-false (empty-deque? dq))
(check-equal? (front-deque dq) 'a)
(check-equal? (rear-deque dq) 'a)

(rear-insert-deque! dq 'b)
(check-equal? (rear-deque dq) 'b)

(front-delete-deque! dq)
(check-equal? (front-deque dq) 'b)

(front-insert-deque! dq 'a)
(check-equal? (front-deque dq) 'a)

(rear-delete-deque! dq)
(check-equal? (rear-deque dq) 'a)