; Deque ; pair: front pointer, rear pointer ; elements are: pair(value, pair(next pointer, previous previous)) (define (make-deque) (cons '() '())) (define (front-ptr deque) (car deque)) (define (rear-ptr deque) (cdr deque)) (define (set-front-ptr! deque item) (set-car! deque item)) (define (set-rear-ptr! deque item) (set-cdr! deque item)) (define (make-element value next previous) (cons value (cons next previous))) (define (element-value element) (car element)) (define (next-ptr element) (cadr element)) (define (previous-ptr element) (cddr element)) (define (set-next-ptr! element next) (set-car! (cdr element) next)) (define (set-previous-ptr! element previous) (set-cdr! (cdr element) previous)) (define (empty-deque? deque) (null? (front-ptr deque))) (define (front-deque deque) (if (empty-deque? deque) (error "FRONT called with an empty deque") (element-value (front-ptr deque)))) (define (rear-deque deque) (if (empty-deque? deque) (error "REAR called with an empty deque") (element-value (rear-ptr deque)))) (define (front-insert-deque! deque item) (let ((new-element (make-element item (front-ptr deque) '()))) (cond ((empty-deque? deque) (set-front-ptr! deque new-element) (set-rear-ptr! deque new-element) deque) (else (set-previous-ptr! (front-ptr deque) new-element) (set-front-ptr! deque new-element) deque)))) (define (rear-insert-deque! deque item) (let ((new-element (make-element item '() (rear-ptr deque)))) (cond ((empty-deque? deque) (set-front-ptr! deque new-element) (set-rear-ptr! deque new-element) deque) (else (set-next-ptr! (rear-ptr deque) new-element) (set-rear-ptr! deque new-element) deque)))) (define (front-delete-deque! deque) (if (empty-deque? deque) (error "FRONT-DELETE deque is empty") (let ((next (next-ptr (front-ptr deque)))) (cond ((null? next) (set-rear-ptr! deque '())) (else (set-previous-ptr! next '()))) (set-front-ptr! deque next) deque))) (define (rear-delete-deque! deque) (if (empty-deque? deque) (error "REAR-DELETE deque is empty") (let ((previous (previous-ptr (rear-ptr deque)))) (cond ((null? previous) (set-front-ptr! deque'())) (else (set-next-ptr! previous '()))) (set-rear-ptr! deque previous) deque)))