COSC-052 Project 3

COSC-052: Computer Science II

Project 3
Spring 2013

Due: Wed, Mar 27 @ 5 PM
8 points

In lecture, we have started discussing self-referential classes, template classes, container classes, and abstract data types. For this project, you'll use a singly-linked list to implement a stack and a doubly-linked list to implement a double-ended queue or deque (pronounced "deck"). Naturally, the classes for these containers must be able to hold any object, so you must implement them as template classes. Specifically, you will implement and use the Node<T> class to implement Stack<T>, and you will implement and use the DLNode<T> class to implement Deque<T>. Recall that I put the code for Node<T> on cs-class, which you can copy to your directory by typing the command

cp ~maloofm/cosc052/node.h ./

The container classes must implement a default constructor, a copy constructor, an overloaded memberwise copy operator (operator=), a size method, an empty method, a clear method, and a destructor. (Not deconstructor! That's POMO. This is C++.)

It is imperative that you follow my design for the public interface. Stack<T>::pop must remove and return the object from the top of the stack, Stack<T>::push must add an object to the top of the stack, and Stack<T>::top must return a reference to the object on the top of the stack. Deque<T>::removeFront and removeBack must remove and return the object from the front and back of the deque, respectively, insertFront and insertBack must add an object to the front and back of the deque, respectively, and Deque<T>::front and back must return a reference to the object at the front and back of the deque, respectively. Finally, I would recommend implementing the method printInternal for both classes so you can inspect the internal state of the containers and their linked lists during development.

Any method that dynamically allocates memory must throw bad_alloc. Any method that returns or removes objects must throw the NoSuchObject exception when called for an empty container. Derive NoSuchObject from logic_error. Use constant parameters and constant methods as appropriate.

To grade your project, I'll drop a main function into your directory and compile. main will test all aspects of all of your class. As a consequence, it is imperative that you test all of your methods thoroughly, preferably as you're developing them.

Getting Started

You should have everything you need to get started. Node<T> is on cs-class, and we will discuss Stack<T> in lecture. Use the Makefile from p2 and modify it for this project.

Instructions for Electronic Submission

At the top of the file main.cc (or the file containing the main function), place the following header comment, with the appropriate substitutions:

/*
 * COSC-052 Project 3
 * Name: <your name>
 * ID: <GoCard ID>
 * E-mail: <e-mail address>
 * Instructor: Maloof
 *
 * In accordance with the class policies and Georgetown's Honor Code,
 * I certify that, with the exceptions of the class resources and those
 * items noted below, I have neither given nor received any assistance
 * on this project.
 */

You'll be submitting p3 exactly like you submitted p2. If you need to include a message about your submission, then place the message in a file named README. Place the README file in the project's directory.