COSC-052 Project 3

COSC-052: Computer Science II

Project 3
Spring 2023

Due: F 3/24 @ 5:00 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 use the Node<T> class, which I've provided, to implement Stack<T>, and you will implement and use the DLNode<T> class to implement Deque<T>. One departure from previous projects is, with template classes, the class definition and its implementation are in a .h file.

In addition to methods for adding, removing, and inspecting objects, 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, you'll find an implementation of the method Stack<T>::printInternal, which will let you inspect the internal state of the containers and their linked lists during development. I recommend that you implement an analogous method for Deque<T>. We will discuss these methods extensively in lecture, and so your lecture notes serve as the documentation for this project.

Any method that returns or removes objects may throw the NoSuchObject exception when called for an empty container. Derive NoSuchObject from logic_error.

Getting Started

To get started, log on to cs-class and copy over the following zip file:

cs-class% cd
cs-class% cp ~maloofm/cosc052/p3.zip ./
cs-class% unzip p3.zip

In the p3 directory, you will find the implementation for Node<T> and the class definitions for Stack<T> and Deque<T>, which we will discuss in lecture. There is also a Makefile. For convenience, there is a submit target in the Makefile that produces submit.zip for Autolab. To produce this file, type 'make submit', although you may need to make changes to the file extensions.

Instructions for Electronic Submission

In a file named HONOR, include the following statement with the appropriate modifications:

In accordance with the class policies and Georgetown's Honor System,
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.

Name
NetID

You will submit p3 exactly like you submitted p2. Make sure you remove all debugging output before submitting.

Plan B

If Autolab is down, upload your zip file to Canvas.