Object-Oriented Programming: Stacks and Queues

Goals

This laboratory exercise reviews strategies of problem solving discussed in this class. Then, building on recent work, the lab introduces stacks and queues as examples of useful classes.

Handling Complexity

The reading for this laboratory exercise outlines several strategies and language capabilities for handling complexity. These include the use of procedures, local variables, parameters, recursion, data abstraction, procedural abstraction, libraries, and classes and objects.

1. Identify how you have used each of the above approaches or capabilities in the solving of at least two specific problems during this course.

Stacks as ADTs:

The reading describes a stack as an object that contains can store data and that has the following operations:

• Make-Stack
  Create a new, empty stack object.
• Empty
  Empty returns true or false (#t or #f), depending upon whether the stack contains any items or not.
• Push
  Push adds the specified item to the top of the stack.
• Pop
  If the stack is not empty, Pop removes the top item from the stack, and this item is returned.
  If the stack is empty, nothing is returned, and an error is reported.
• Top
  If the stack is not empty, the top item is returned, but the contents of the stack are not changed.
  If the stack is empty, nothing is returned, and an error is reported.

To implement a class within Scheme, we may proceed following the recent reading on Abstract Data Types. The simplest approach is to maintain an internal list within the abstract data type or class. With this approach, push and pop operations insert or delete an item from the front of the list, the empty operation tests if the list is empty, and the top operation returns the head of the list.

2. Write a stack class, following the implementation described above.

3. Check your implementation using the following script that is duplicated from the reading for this lab:

   
   > (define mag-pile     ...    )   ; make stack for magazines
                   ; (details of call dependent on implementation)
   > (define bill-pile    ...    )   ; make stack for bills
                   ; (details of call dependent on implementation)
   > (bill-pile 'push! "mortgage")   ; send push message to bill-pile
   > (bill-pile 'push! "doctor's bill")
   > (bill-pile 'push! "credit card")
   > (bill-pile 'empty?)             ; send empty? message to bill-pile
   #f                                ; response from empty? message
   > (mag-pile 'empty?)
   #t
   > (mag-pile 'push! "Communications of the ACM - April 1997")
   > (mag-pile 'push! "CS Education Bulletin - Spring 1998")
   > (bill-pile 'top)                ; send top message to bill-pile
   "credit card"                     ; data returned as message response
   > (mag-pile 'top)
   "CS Education Bulletin - Spring 1988"
   > (bill-pile 'pop!)
   "credit card"
   > (bill-pile 'top)
   "doctor's bill"
   

4. Expand the code for the stack ADT implementation by adding
   • a size method which will return the number of items currently on the stack,

   • a print method which will print all of the current elements on the stack, and

   • an nth method which takes one parameter (an index) and returns the item at that position from the top in the current stack.

The Queue Abstract Data Type

A queue class may be defined with the following constructor for creating new objects:

(define queue-class
  (lambda ()
    (let* ((front (list 'dummy-header))
           (rear front))
      (lambda (message . arguments)
        (case message
              ((empty?) (null? (cdr front)))

              ((enqueue!)
               (if (null? arguments)
                   (error 'queue-class "method ENQUEUE!: An argument is required")
                   (begin

                     ; Attach a new cons cell behind the current rear
                     ; element.

                     (set-cdr! rear (list (car arguments)))

                     ; Advance REAR so that it is once more a list
                     ; containing only the last element.

                     (set! rear (cdr rear)))))

              ((dequeue!)
               (if (null? (cdr front))
                   (error 'queue-class "method DEQUEUE!: The queue is empty")

                   ; Recover the first element of the queue (not including
                   ; the dummy header).

                   (let ((removed (cadr front)))

                     ; Splice out the element to be dequeued.

                     (set-cdr! front (cddr front))

                     ; If you just spliced out the last element of the
                     ; queue, reset REAR so that it holds the dummy
                     ; header.

                     (if (null? (cdr front))
                         (set! rear front))
                          removed)))

              ((front)
               (if (null? (cdr front))
                   (error 'queue "method FRONT: The queue is empty")
                   (cadr front)))

              (else (error 'queue-class "unrecognized message")))))))

5. Add to the queue an additional method, activated by the print message, that displays each of the elements of the queue on a separate line (without actually removing any of them from the queue). Make sure not to print the dummy header.

6. Write a procedure print-symbols that creates an empty queue, then processes a list to put each symbol on the list or on any sublist into the queue, and finally uses the print method added in the previous exercise to display the contents of the queue. For example,

       (print-symbols '(((to) be) (or (not (to ((be)))))))
   

   should print

       to be or not to be
   

7. Rewrite the previous print-symbols procedure to use a stack instead of a queue to store the symbols. How does the output differ from that obtained in the previous problem?

Work to be turned in:

• Comments for part 1, 7.
• Code, with test runs, for parts 2, 4, 5, 6.

This document is available on the World Wide Web as

http://www.walker.cs.grinnell.edu/courses/153.sp05/labs/lab-stacks-queues.shtml

created April 28, 1997 last revised March 15, 2005
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.