SICP Exercise 3.23

sicp

Question

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 \(\Theta(1)\) steps.

Answer

This would be really easy if it weren’t for rear-delete-queue, which is hard to do in \(\Theta(1)\) time, since you need to get the second-to-last pair in the list.

In order to solve this problem, we need to use a double linked list as our basic structure. This uses a three-part structure which I will call a node containing first the value, then the previous element and then the next element. Here are the helper functions for our nodes:

(define (make-node val prev next)
  (list val prev next))
(define (val-node node) (car node))
(define (prev-node node) (cadr node))
(define (next-node node) (caddr node))
(define (set-val-node! node x)
  (set-car! node x))
(define (set-prev-node! node x)
  (set-car! (cdr node) x))
(define (set-next-node! node x)
  (set-car! (cddr node) x))

With this, we can now implement the deque logic.

(define (make-deque)
  (let ((front-ptr '())
        (rear-ptr '()))
    (define (empty-deque?)
      (or (null? front-ptr) (null? rear-ptr)))
    (define (front-deque)
      (if (empty-deque?)
          (error "FRONT called with an empty deque")
          (car front-ptr)))
    (define (rear-deque)
      (if (empty-deque?)
          (error "REAR called with an empty deque")
          (car rear-ptr)))
    (define (set-front-ptr! i)
      (set! front-ptr i))
    (define (set-rear-ptr! i)
      (set! rear-ptr i))
    (define (front-insert-deque! i)
      (let ((new-node (make-node i '() '())))
        (cond ((empty-deque?)
               (set-front-ptr! new-node)
               (set-rear-ptr! new-node))
              (else
               (set-next-node! new-node front-ptr)
               (set-prev-node! front-ptr new-node)
               (set-front-ptr! new-node)))))
    (define (rear-insert-deque! i)
      (let ((new-node (make-node i '() '())))
        (cond ((empty-deque?)
               (set-front-ptr! new-node)
               (set-rear-ptr! new-node))
              (else
               (set-prev-node! new-node rear-ptr)
               (set-next-node! rear-ptr new-node)
               (set-rear-ptr! new-node)))))
    (define (front-delete-deque!)
      (cond ((empty-deque?)
             (error "FRONT-DELETE! called with an empty deque"))
            ((null? (next-node front-ptr))
             (set-front-ptr! '()))
            (else
             (set-front-ptr! (next-node front-ptr))
             (set-prev-node! front-ptr '()))))
    (define (rear-delete-deque!)
      (cond ((empty-deque?)
             (error "REAR-DELETE! called with an empty deque"))
            (else
             (set-rear-ptr! (prev-node rear-ptr))
             (set-next-node! rear-ptr '()))))
    (define (dispatch m)
      (cond ((eq? m 'front-insert-deque!) front-insert-deque!)
            ((eq? m 'rear-insert-deque!) rear-insert-deque!)
            ((eq? m 'front-delete-deque!) (front-delete-deque!))
            ((eq? m 'rear-delete-deque!) rear-delete-deque!)
            ((eq? m 'front-deque) (front-deque))
            ((eq? m 'rear-deque) (rear-deque))
            ((eq? m 'front-ptr) front-ptr)
            (else
             (error "UNKNOWN METHOD -- make-deque"))))
    dispatch))