CS 301 - Data Structures and Algorithms I - Fall 2002
Project 2
Loyola College >
Department of Computer Science >
CS 301 >
Projects >
Project 3
Due
Monday, November 18 at 11:59pm
Purpose
To use dynamically allocated arrays.
Introduction
A deque (for "double-ended queue" and pronounced "deck") is an ordered
structure that allows adds and removes from both ends, so that it can
be used as a stack (by adding and removing from the same end) or a queue
(by adding and removing from opposite ends) or some combination of
the two.
Assignment
Provide an implementaion of a deque according to the specifications in
the supplied header file. Your implemenetation must use a dynamically
allocated array to store the items in the deque.
Files
Requirements
For any credit, your implementation must use a dynamically allocated
array to hold the items on the deque.
For full credit, your implementation must satisfy the following
requirements.
- It should be easy to modify your implementation to use different
item types.
- It should not produce any memory leaks.
- The copy constructor should perform a deep copy.
- The add and remove methods should work in amortized time better than
O(n).
- Your dynamically allocated array should be resized as appropriate
for the add and remove methods.
- The space allocated to your array should be O(n).
Testing
No test driver is provided for this project. It is your responsibility
to write a main function that adequately tests your Deque
class.
Submissions
Submit your project by attaching the files containing your code
to an e-mail message sent to
jglenn@cs.loyola.edu. You should only send the files you created or
modified (i.e. deque.h and deque.cpp).
You needn't send your main; your project will be tested with
one of my devising.
The body of your message must contain a pledge
that you have not violated the Honor Code in the completion of the project.