Chapter 3, Modularity, Objects, and State
Exercise 3.23
To do it in constant time, double linked list is required. Similar to queue
, here also we use front and rear pointers.
Used a structure which I referred as ptr
that contains 3 items next
which points to next ptr
, prev
which points to previous ptr
and data
which contains the actual data/item.
After establishing the above concepts, implementation is straighforward, just managing the pointers carefully(having some background in C helped me). Lets first see the output/examples:
Note that display-deque
is a procedure to display contents of deque. It prints ~
to mark the end of the list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
> (define d1 (make-deque))
> (display-deque (front-insert-deque! d1 '1))
1 ~
> (display-deque (front-delete-deque! d1))
~
> (display-deque (front-insert-deque! d1 '1))
1 ~
> (display-deque (front-insert-deque! d1 '2))
2 1 ~
> (display-deque (rear-delete-deque! d1))
2 ~
> (display-deque (front-insert-deque! d1 '1))
1 2 ~
> (display-deque (front-insert-deque! d1 '0))
0 1 2 ~
> (display-deque (rear-insert-deque! d1 'c))
0 1 2 c ~
> (display-deque (rear-insert-deque! d1 'd))
0 1 2 c d ~
> (display-deque (rear-insert-deque! d1 'e))
0 1 2 c d e ~
> (display-deque (rear-delete-deque! d1))
0 1 2 c d ~
> (display-deque (front-delete-deque! d1))
1 2 c d ~
> (display-deque (rear-delete-deque! d1))
1 2 c ~
> (display-deque (front-delete-deque! d1))
2 c ~
> (display-deque (front-delete-deque! d1))
c ~
> (display-deque (rear-delete-deque! d1))
~
> (display-deque (front-delete-deque! d1))
. . Delete called with an empty deque
> (display-deque (rear-delete-deque! d1))
. . Delete called with an empty deque
> (display-deque (rear-insert-deque! d1 'hello))
hello ~
> (display-deque (front-insert-deque! d1 'world))
world hello ~
> (display-deque (front-delete-deque! d1))
hello ~
> (display-deque (rear-insert-deque! d1 'world))
hello world ~
> (display-deque (front-delete-deque! d1))
world ~
> (display-deque (rear-delete-deque! d1))
~
>
Now here goes the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#lang sicp
(define (make-deque) (cons '() '()))
(define (display-deque deque)
(define (display-iter ptr)
(cond ((null? ptr) (display "~"))
(else
(display (data ptr))
(display " ")
(display-iter (next ptr)))))
(display-iter (front-ptr deque)))
(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-new-ptr item) (list '() item '()))
(define (next ptr) (car ptr))
(define (data ptr) (cadr ptr))
(define (prev ptr) (caddr ptr))
(define (set-next! ptr next) (set-car! ptr next))
(define (set-data! ptr dat) (set-car! (cdr ptr) dat))
(define (set-prev! ptr prev) (set-car! (cddr ptr) prev))
(define (empty-deque? deque) (or (null? (front-ptr deque)) (null? (rear-ptr deque))))
(define (front-deque deque)
(if (empty-deque? deque)
(error "Deque is empty")
(data (front-ptr deque))))
(define (rear-deque deque)
(if (empty-deque? deque)
(error "Deque is empty")
(data (rear-ptr deque))))
(define (front-insert-deque! deque item)
(let ((new-ptr (make-new-ptr item)))
(cond ((empty-deque? deque)
(set-front-ptr! deque new-ptr)
(set-rear-ptr! deque new-ptr)
deque)
(else
(set-next! new-ptr (front-ptr deque))
(set-prev! (front-ptr deque) new-ptr)
(set-front-ptr! deque new-ptr)
deque))))
(define (rear-insert-deque! deque item)
(let ((new-ptr (make-new-ptr item)))
(cond ((empty-deque? deque)
(set-front-ptr! deque new-ptr)
(set-rear-ptr! deque new-ptr)
deque)
(else
(set-prev! new-ptr (rear-ptr deque))
(set-next! (rear-ptr deque) new-ptr)
(set-rear-ptr! deque new-ptr)
deque))))
(define (front-delete-deque! deque)
(cond ((empty-deque? deque)
(error "Delete called with an empty deque"))
(else (set-front-ptr! deque (next (front-ptr deque)))
(if (empty-deque? deque)
(set-rear-ptr! deque '())
(set-prev! (front-ptr deque) '()))
deque)))
(define (rear-delete-deque! deque)
(cond ((empty-deque? deque)
(error "Delete called with an empty deque"))
(else (set-rear-ptr! deque (prev (rear-ptr deque)))
(if (empty-deque? deque)
(set-front-ptr! deque '())
(set-next! (rear-ptr deque) '()))
deque)))