CSE 326 Data Structures Project 1

CSE 326 Data Structures
Project 1
April 6, 1998
due: Wednesday, April 15, 1998, electronically by 11:30 pm

Objectives

The purpose of this assignment is to:

Review Stack and Queue ADTs.
Do some simple analysis of a data structure's performance.
Become comfortable with the Unix programming environment.
Introduce the C++ template facility.

Overview

Stacks and Queues are two very basic abstract data types for storing data that are useful in a wide variety of applications. Stacks have a Last-In-First-Out (LIFO) behavior: if a number of items are put on a stack, they will be removed from the stack in reverse order. Queues have a First-In-First-Out (FIFO) behavior: items leave a queue in the order that they were placed on the queue.

Despite their different behavior, one can implement a queue data structure by employing two instances of a stack data structure. This implementation is efficient: n queue operations can be performed using on average a constant number of stack operations per queue operation. Assuming that each stack operation takes a constant amount of work, then performing n queue operations can take only linear (O(n)) time.

Assignment

Your job is to implement a queue data structure that stores its data using only two instances of a stack data structure. Your implementation must be efficient: you will be required to argue that it uses only O(n) stack operations for n queue operations.

What we've provided

As a starting point we've provided a few files:

Stack.h - Contains the specification and efficient implementation of a Stack ADT. It is implemented as a C++ template class. Notice that the implementation is not in a separate .C file : the section on Templates below explains why this is the case.
Queue.h - Contains the specification of a Queue ADT as a C++ template class, as well as the shell of its implementation. You will be adding your implementation to this file.
main.C - Contains a simple driver program for testing your Queue implementation. It performs a brain-dead version of the Unix command cat, reading words from stdin, putting them into a queue, then dequeuing them and outputting them to stdout. The driver initializes an empty queue of strings (the queue has type Queue<char *>). Each step of the main loop randomly chooses one of two operations: (1) read a word and enqueue it or (2) dequeue a word and print it.
Makefile - Contains the specification for building a test executable called catq which performs the functionality of main.C described above. To build catq enter the following at the shell prompt:
% make catq
You will not need to edit this file for this assignment.

All provided files can be found in the project directory:

/cse/courses/cse326/98sp/project1

You should make a copy of this directory into your home directory

% cp -r /cse/courses/cse326/98sp/project1 ~/project1

and edit your copy.

What to hand in

You are required to hand in your project1 directory with your implementation of the Queue data structure. Included in this directory should be these two files:

Queue.h - This should contain your implementation of the Queue data structure that uses two Stacks.
README - This is a text file describing your project implementation. It should include the following discussion:
1. Describe your queue implementation. Specifically, how did you implement the Enqueue() and Dequeue() operations? Provide interesting examples illustrating the queue's behavior.
2. Argue that your implementation is efficient. First, what is the worst case running time of your queue for a single Enqueue() operation? Dequeue() operation? Despite this worst case behavior, why does your implementation use O(n) time for n queue operations? Assume that stack operations take a constant amount of time.
Your writing style is important on this part of the project. You should write your README file in a well organized and clear way. It should be less 60 lines. You should imagine that thousands of people will be reading your file and that you will receive e-mail or a phone call from someone who does not understand what you are talking about.

How to hand in

We are using the turnin program to hand in project assignments. When you are ready to submit your solution, you should have all of your files sitting in some directory. Suppose this directory is named ~/326stuff/myproj1dir. Suppose also, that you're in section AA. To submit your solution, type the following:

% cd ~/326stuff/myproj1dir % make clean % cd ../ % turnin -c cse326=AA -p project1 myproj1dir

This will submit the contents of your directory with a time stamp. You can submit more than once, but only the last submission is kept. Check the contents of your last submission by:

% turnin -v -c cse326=AA -p project1

man turnin for more details and options.

Computing at home

It is fine to develop your program at home using another C++ compiler, but you must turn in the program using turnin and your program must compile and work correctly using g++ on the instructional machines. In this way we can compile and run your program on our test suite.

C++ Templates

Many ADTs that we will describe in this class are general enough to manage many types of data. For example, this assignment uses a queue of strings, but you could imagine having queues of integers, or queues of points, etc. Unfortunately, C++ does not make it easy to implement ADTs for general purpose use. One way to do this in C++ is to use templates.

Look at our Stack implementation using templates in Stack.h. It illustrates the general structure for declaring a template class:

template <class T> class Stack {
...
    // Stack specification and implementation with respect to type T
...
};

Everything inside the brackets is just like it would be in normal class specification/implementations, except the declarations use some unknown type T. The identifier T is used as a placeholder to represent the type of data that will be stored on the stack.

Instantiating template classes to create new objects is similar to normal classes, except we must specify the type for the template. For example, here is how you create a stack of integers capable of holding 100 objects:

Stack<int> mystack(100);

mystack.Push(8);
mystack.Push(4);
int result = mystack.Pop();

Note that its use after instantiation is just like any other object.

The only caveat of using C++ templates is that both the specification and implementation must be specified in an include file. This is because the compiler cannot compile code for a template class until it sees how it is being instantiated. If code needs to have both int stacks (Stack<int>) and (char *) stacks (Stack<char *>), the compiler will generate different code for each. The end result, however, is what we desired: the ability to specify both types of stacks with a single set of source code.

Note that the recent C++ standard allows for compilers to support template class implementation in a separate source module. However, most compilers including our version of g++ on the instructional unix machines don't support this.