(define <deque> <pair>)
; using a <triple> is a waste of space
; Another common error was to add slots, and not use head and tail
(define (new-mutable-deque)
(list empty))
; or (list '()) or (cons '() '()) etc.
; see above for pictorial representation
(define (insert-front! o (q <deque>))
(let* ((old (head q))
(new (make-triple empty o old)))
(set! (head q) new)
(if (null? old) (set! (tail q) new))
(set! (prev old) new))))
(define (extract-end! q <deque>)
(let ((old (tail q)))
(cond ((null? old) (error "Empty DEQueue"))
((null? (prev old))
(set! (head q) empty)
(set! (tail q) empty)
(val old))
(else (set! (next (prev old)) empty)
(set! (tail q) (prev old))
(val old))))))
; Note that there are three cases listed:
; 1. There are no elements to extract because the queue is empty
; 2. The last element is also the first element, so we must set! (head q) also
; 3. Normal case
; This is how you would implement the other two functions:
(define (insert-end! o (q <deque>))
(let* ((old (tail q))
(new (make-triple old o empty)))
(set! (tail q) new)
(if (null? old) (set! (head q) new)
(set! (next old) new)))))
(define (extract-front! (q <deque>))
(let ((old (head q)))
(cond ((null? old) (error "Empty DEQueue"))
((null? (next old))
(set! (head q) empty)
(set! (tail q) empty)
(val old))
(else (set! (prev (next old)) empty)
(set! (head q) (next old))
(val old))))))
