1 (defun make-deque ()
2   (cons '() '()))
3 (defun front-ptr (deque)
4   (car deque))
5 (defun rear-ptr (deque)
6   (cdr deque))
7 (defun set-front-ptr! (deque item)
8   (setf (car deque) item))
9 (defun set-rear-ptr! (deque item)
10   (setf (cdr deque) item))
11 (defun empty-deque? (deque)
12   (null (front-ptr deque)))
13 (defun front-deque (deque)
14   (if (empty-deque? deque)
15       (error "FRONT on empty deque")
16       (caar (front-ptr deque))))
17 (defun rear-deque (deque)
18   (if (empty-deque? deque)
19       (error "REAR on empty deque")
20       (caar (rear-ptr deque))))
21 (defun front-insert-deque! (deque item)
22   (let ((new-pair (cons (cons item '()) '())))
23     (cond ((empty-deque? deque)
24 	   (set-front-ptr! deque new-pair)
25 	   (set-rear-ptr! deque new-pair)
26 	   deque)
27 	  (t
28 	   (setf (cdr new-pair) (front-ptr deque))
29 	   (setf (cdar (front-ptr deque)) new-pair)
30 	   (set-front-ptr! deque new-pair)
31 	   deque))))
32 (defun rear-insert-deque! (deque item)
33   (let ((new-pair (cons (cons item (rear-ptr deque)) '())))
34     (cond ((empty-deque? deque)
35 	   (set-front-ptr! deque new-pair)
36 	   (set-rear-ptr! deque new-pair)
37 	   deque)
38 	  (t
39 	   (setf (cdr (rear-ptr deque)) new-pair)
40 	   (set-rear-ptr! deque new-pair)
41 	   deque))))
42 (defun front-delete-deque! (deque)
43   (cond ((empty-deque? deque)
44 	 (error "FRONT-DELETE on empty deque"))
45 	(t
46 	 (set-front-ptr!
47 	  deque
48 	  (cdr (front-ptr deque)))
49 	 deque)))
50 (defun rear-delete-deque! (deque)
51   (cond ((empty-deque? deque)
52 	 (error "REAR-DELETE on empty deque"))
53 	(t
54 	 (set-rear-ptr! deque (cdar (rear-ptr deque)))
55 	 (setf (cdr (rear-ptr deque)) '())
56 	 deque)))
57 (defun print-deque (deque)
58   (format t "(")
59   (mapcar (lambda (e)
60 	    (format t "~a " (car e)))
61 	  (front-ptr deque))
62   (format t ")"))