CSE 326 Data Structures
Project 1
April 7,1997

due: April 16, 1997


The purpose of this assignment is to:


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.


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:

All provided files can be found in the project directory:
You should make a copy of this directory into your home directory
% cp -r /cse/courses/cse326/97sp/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:

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. Supppose 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.

C++ Templates

Many ADTs that we will describe in this class are general enough to manage many types of data. For example, this assigment 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);

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.