Programming Assignment 4

Implementing a Queue Data Structure

810:052

Data Structures

Fall Semester 1997

Due: by 8:00 AM on October 29, 1997

Background: Queues

Lists can be a useful ADT, but they aren't really a useful data structure in at least one sense: There is no accepted definition for what a list should do. As a result, different programmers discussing their lists may have very different meanings. Is there more than one way to add items to a list? Can I look up things in the list? Can I remove or replace items? So, using "list" as a part of our design and programming vocabulary is likely to cause more confusion than it can avoid.

The rest of the course will be devoted to "classic" data structures that do have well-defined interfaces. The first two that we study, stacks and queues, can be implemented using the techniques that we studied while discussing lists. A stack is a list where insertions and removals always occur at the same end of the list. Furthermore, all access to items in a stack must occur at that same end, so we aren't allowed to "look up" items that occur deeper in the list. A queue is a list where insertions and removals always occur at opposite ends of the list.

Beyond that, there isn't much to say about what stack and queue "mean". As we will see, there are several interesting techniques that we can use to implement these structures, each with specific performance implications. These implementation trade-offs will be our topic of discussion for the next two weeks.

Your Task

Implement a Queue class. Your Queue should meet the interface specification provided by Roberge in his Laboratory Exercise 6. You should use a circular linked list as the underlying implementation.

Source Files

Here is the public portion of Roberge's interface for the Queue class. You will also need his test program to test your implementation and to complete the bridge exercise.

Deliverables

As always, your files must begin with a header block that includes the file name, your name as author, and the creation and modification history of the file. You may use this file as a template. And don't forget to follow the programming style sheet for the course!

Submit to your instructor, by the due time and date, the following:

• two separate e-mail messages, each of which contains only a single C++ file.
  • your Queue interface, augmented with any private member data and private member functions, and
  • your Queue implementation.

• a completed bridge exercise from Roberge's Laboratory Exercise 6 and print-outs of your interface and implementation, stapled in the order listed.