CS212 Exams
Spring 1998 - Prelim 1

Abstraction and Structure Definitions

A queue is a container with the property that the first thing inserted into the queue is the first object that can be removed from the queue. That is, queues are First-In, First-Out (FIFO) containers.

You are asked to implement the following contract for queues:

     type: <queue>
     (create-queue) --  creates a new, empty queue
     (empty? q)     --  returns #t if the queue is empty
     (insert x q)   --  takes an object x and a queue q and returns a new queue
                          with x inserted into the queue
     (front q)      --  returns the front of the queue.  that is, the first
                          object in the queue.
     (remove q)     --  returns a new queue with the front removed.

The contract requires that the following equivalences hold:

     (empty? (create-queue)) = #t
     (empty? (insert x q)) = #f

     if (empty? q) = #t, then (front (insert x q)) = x and
                              (remove (insert x q)) = q

     if (empty? q) = #f, then (front (insert x q)) = (front q) and
                              (remove (insert x q)) = (remove q).

In what follows, you will define a structure for queues and methods for create-queue, empty?, insert, front, and remove.

a.

class definition:

b.

create-queue definition:

c.

empty? definition:

d.

insert definition:

e.

front definition:

f.

remove definition:

Solution

Return to CS 212 Prelim 1 - Spring 1998