Project #3 implement a stack and a doubly-linked list



23 February 2019 Project #3
COSC 052 Spring 2019 Page 1 of 4
In lecture, we have started discussing self-referential classes, template classes, container classes, and abstract data
types. For this project, you will 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>. A Makefile and some starting code are available on Canvas.
The queue and deque container classes, among other methods, must implement a default constructor, a copy
constructor, an overloaded assignment operator, a size method, an empty method, a clear method, and a
It is imperative that you follow the design for the public interface. Stack<T>::pop must remove and the object
from the top of the stack. Stack<T>::push must add an object to the top of the stack. Stack<T>::top
must return a reference to the object on the top of the stack. Deque<T>::removeFront and
Deque<T>::removeBack must remove and return the object from the front and back of the deque
respectively. Deque<T>::insertFront and Deque<T>::insertBack must add an object to the front
and back of the deque respectively. Deque<T>::front and Deque<T>::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 a bad_alloc exception object. Any method that
returns or removes objects must throw the NoSuchObject exception when called for an empty container.
Derive NoSuchObject from logic_error.
Node and DL Node Class UML Diagrams
+ info : T
+ next : DLNode<T>*
+ previous : DLNode<T>*
+ DLNode(T = T(), DLNode<T>* = NULL, DLNode<T>* = NULL)
– object : T
– nextPtr : Node<T>*
+ Node(const T& = T(),
Node<T>* = NULL)
+ setObject( const T & ) : void
+ getObject() : T&
+ setNextPtr( Node<T> * ) : void
+ getNextPtr() const : Node<T>*
23 February 2019 Project #3
COSC 052 Spring 2019 Page 2 of 4
Getting Started
To get started download the zip file attached to the Project 3 Assignment on Canvas. In this file, you will find the
implementation code for Node<T> and the class declarations for Stack<T> and Deque<T>, which we will
discuss in lecture. There is also a Makefile that contains, among other things, a submit target that produces for Autolab. To produce this file, just type ‘make submit’ at the command line. You may need
to make changes to the file extensions as described in the Makefile comments.
Academic Integrity
This is an individual project and all work must be your own. Refer to the guidelines specified in the Academic
Honesty section of this course syllabus or contact me if you have any questions. A file named HONOR containing
the following contents is also provided:
Make the appropriate substitutions and ensure that the file is included with your submission.
Instructions for Electronic Submission
Although you may use any development environment for your project, your grade will depend upon how your
project compiles and runs on AutoLab. Use the available test compile submissions to ensure it will compile before
submitting for grade. Testing on the cs-class server is also advised as there is no limit there.
Your project must be submitted no later than Tuesday, March 26, 2019 at 5:00pm. Late submissions will be
penalized 1 point for each minute. In general requests for extensions will not be considered.
You will submit Project 3 in the same way you did the previous two projects. (Plan B: ONLY in case of some
catastrophic issue with the AutoLab system or one of the servers I will inform everyone to submit to Canvas).
Emergency Backup
Once you have submitted your project, it is important to keep an electronic copy on a university machine such as
the class server (cs-class) that preserves the modification date and time. If we lose your project or the
submission system breaks, then we will need to look at the modification date and time of your project to ensure
that you submitted it before it was due. Retain either the zip file or the directory containing your project’s files.
This graded assignment is worth 100 points and will be counted as part of the Programming Projects category for
the course. Your final score is based on automated tests performed by AutoLab, as well as a manual review
conducted by one of our Teaching Assistants (TAs). We will talk about the AutoLab tests in class and you will be
able to see exactly what those are when you submit for the first time.
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.
23 February 2019 Project #3
COSC 052 Spring 2019 Page 3 of 4
Course Materials Notice
The materials used in Georgetown University courses (“Course Materials”) generally represent the intellectual
property of course instructors which may not be disseminated or reproduced in any form for public distribution
(e.g., sale, exchange, etc.) without the written permission of the course instructor. Course Materials include all
written or electronic documents and materials, including syllabi, current and past examination questions/answers,
and presentations such as lectures, videos, PowerPoints, etc., provided by a course instructor. Course Materials
may only be used by students enrolled in the course for academic (course-related) purposes.
Published course readings (book chapters, articles, reports, etc.) available in Canvas are copyrighted material.
These works are made available to students through licensed databases or fair use. They are protected by
copyright law, and may not be further disseminated or reproduced in any form for distribution (e.g., uploading to
websites, sale, exchange, etc.) without permission of the copyright owner.
More information about intellectual property and copyright can be found here:
More information about computer acceptable use policy and intellectual property can be found here:

Computer Systems Acceptable Use Policy

This document: Copyright © 2019 W. A. Woods. All Rights Reserved. This material may not be published,
broadcast, rewritten, or redistributed.
On-line documentation: Copyright © 2019 Mark Maloof. All Rights Reserved. This material may not be
published, broadcast, rewritten, or redistributed.
23 February 2019 Project #3
COSC 052 Spring 2019 Page 4 of 4
(this page intentionally left blank)


There are no reviews yet.

Be the first to review “Project #3 implement a stack and a doubly-linked list”

Your email address will not be published.