Data Structures

One sometimes inconvenient feature of lists in Scheme is that it is only possible to iterate through the list in one direction. We can get around this by implementing two-way lists. Consider that regular lists are built from cells (i.e., cons cells) containing two pointers, where the first (head) points to a value of the list and the second (tail) points to the next cell. We can extend this idea to handle two-way lists by adding an extra pointer to our list element. Consider the following code:

(defclass <triple> ()
  (previous :type <top> :initarg :prev)
  (value :type <top> :initarg :val)
  (next :type <top> :initarg :next))
  
(define (make-triple p v n)
  (make <triple> :prev p :val v :next n))

Using this code, we can now implement a mutable double ended queue (dequeue) which supports the following operations such that they take O(1) (constant) time.

• (new-mutable-deque) : Create a new empty mutable deque.
• (insert-front! val deq) : Put val at the front of deque.
• (insert-end! val deq) : Put val at the end of deque.
• (extract-front! deq) : Remove value at the front of the deque and return it.
• (extract-end! deq) : Remove value at the end of the deque and return it.

The implementation should behave as follows:

(define (a <deque>) (new-mutable-deque))
(define (b <deque>) (new-mutable-deque))
(insert-front! 5 a)
(insert-front! 4 a)
(insert-end! 'fred b)
(insert-end! 7 a)
(insert-front! 'barney b)
(extract-front! a) --> 4
(insert-end! 'beavis b)
(extract-end! a) --> 7
(insert-front! 2 a)
(extract-end! a) --> 5
(extract-end! a) --> 2
(extract-front! b) --> barney
(extract-front! b) --> fred
(extract-front! b) --> beavis

1. Before writing and code, draw an illustration of your data structure for a nonempty <deque>, using <triple>s. Your data structure must support all constant time operations.
   
   
   
   
   
2. Write code for the new class <deque>, and the three (3) procedures new-mutable-deque, insert-front!, and extract-end!. You do not need to write code for the other procedures, since they are similar, but you must ensure that your design would support these operations correctly and in constant time.

   (defclass <deque>
       
       
       
       
       
       
       (define new-mutable-queue
         (method ((o <top>) (q <deque>))
       
       
       
       
       
       (define insert-front!
         (method ((o <top>) (q <deque>))
       
       
       
       
       
       (define extract-end!
         (method ((q <deque>))
       
       
       
       
   

Solution

Return to CS 212 Prelim 2 - Spring 1997