Exercise 3.23. 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.23 All operations should be accomplished in 
(1) steps.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| (define (make-deque-cell) | |
| (cons | |
| (cons '() '()) | |
| '())) | |
| (define (value-deque-cell cell) | |
| (car | |
| (car cell))) | |
| (define (prev-deque-cell cell) | |
| (cdr | |
| (car cell))) | |
| (define (next-deque-cell cell) | |
| (cdr cell)) | |
| (define (set-value-cell! cell value) | |
| (set-car! (car cell) value) | |
| (newline) | |
| (display (list 'cell-value-has-been-set-to value)) | |
| (newline)) | |
| (define (set-prev-cell! cell prev) | |
| (set-cdr! (car cell) prev) | |
| (newline) | |
| (display (list 'cell-prev-has-been-set-to (value-deque-cell prev))) | |
| (newline)) | |
| (define (set-next-cell! cell next) | |
| (set-cdr! cell next) | |
| (newline) | |
| (display (list 'cell-next-has-been-set-to (value-deque-cell next))) | |
| (newline)) | |
| (define (print-cell cell) | |
| (value-deque-cell cell)) | |
| (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 (empty-deque? deque) | |
| (null? (front-ptr deque))) | |
| (define (make-deque) (cons '() '())) | |
| (define (front-deque deque) | |
| (if (empty-deque? deque) | |
| (error "FRONT called with an empty deque" deque) | |
| (value-deque-cell (front-ptr deque)))) | |
| (define (print-deque deque) | |
| (let | |
| ((cell-iter (front-ptr deque))) | |
| (define (print-deque-at-start start-cell) | |
| (cond | |
| ((eq? (next-deque-cell cell-iter) cell-iter) | |
| (newline) | |
| (display (list 'printing (value-deque-cell cell-iter))) | |
| (newline) | |
| (display (list 'next-of-cell-iter-is (value-deque-cell (next-deque-cell cell-iter)))) | |
| (newline) | |
| (display (list 'cell-iter-is (value-deque-cell cell-iter)))) | |
| (else | |
| (newline) | |
| (display (list 'printing (value-deque-cell cell-iter))) | |
| (newline) | |
| (set! cell-iter (next-deque-cell cell-iter)) | |
| (newline) | |
| (display (list 'cell-iter-is (value-deque-cell cell-iter))) | |
| (newline) | |
| (print-deque-at-start cell-iter)))) | |
| (print-deque-at-start cell-iter))) | |
| (define (rear-insert-deque! deque item) | |
| (let | |
| ((new-cell (make-deque-cell))) | |
| (cond | |
| ((empty-deque? deque) | |
| (set-value-cell! new-cell item) | |
| (set-prev-cell! new-cell new-cell) | |
| (set-next-cell! new-cell new-cell) | |
| (set-front-ptr! deque new-cell) | |
| (set-rear-ptr! deque new-cell) | |
| (print-deque deque)) | |
| (else | |
| (display 'queue-not-empty) | |
| (set-value-cell! new-cell item) | |
| 'done-setting | |
| (set-prev-cell! new-cell (rear-ptr deque)) | |
| (set-next-cell! new-cell new-cell) | |
| (newline) | |
| (display (list 'rear-ptr-of-deque-is (value-deque-cell (rear-ptr deque)))) | |
| (newline) | |
| (display (list 'next-of-rear-ptr-of-deque-was (value-deque-cell (next-deque-cell (rear-ptr deque))))) | |
| (newline) | |
| (set-next-cell! (rear-ptr deque) new-cell) | |
| (display (list 'next-of-rear-ptr-of-deque-now-is (value-deque-cell (next-deque-cell (rear-ptr deque))))) | |
| (newline) | |
| (set-rear-ptr! deque new-cell) | |
| (display (list 'rear-ptr-of-deque-now-is (value-deque-cell (rear-ptr deque)))) | |
| (newline) | |
| (print-deque deque))))) | |
| (define q1 (make-deque)) | |
| (rear-insert-deque! q1 'a) | |
| (rear-insert-deque! q1 'b) | |
| (rear-insert-deque! q1 'c) | |
| (rear-insert-deque! q1 'd) | |