CSE 2050 Data Structures

In this assignment, you will implement a number of small programs. Here, you will:

• use dynamic memory allocation, pointers, and references.
• implement data structures
• implement classes in multiple les
• use overloading and overriding
• use inheritance
• understand the meaning of virtual keyword

Your programs should contain a multi-line header comment similar to:

/*
PROGRAM: CIRCLE.CPP
Written by Bob the Great
This program calculates the circumference of a circle.
Last modification: 8/20/2010
*/

Implementation Instructions

We provide a template for source les and make le that you must use. You will nd the les in the directory src/ which contains:

• .cpp les for the implementation of the data structures
• .h les for the declarations of the data structures
• a main.cpp le to test the code
• an incomplete Makefile that builds the project.

You will write your code inside the provided source les, and you will edit the makele so it builds the code to create a single executable.

Questions

Linked List

In this question you will implement a hierarchy of classes (Figure 1) with interfaces similar to the respective data structures in Java:

• Collection: http://docs.oracle.com/javase/7/docs/api/java/util/Collection. html
• LinkedList: http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList. html
• Queue: http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
• Stack: https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

The type the data structures will hold is again myType which in your case is just an integer with a dierent name, but potentially could be anything.

Each class has his own header le and source le, with the exclusion of Collection which is an abstract class:

• collection.h
• linked_list.h, linked_list.cpp
• queue.h, queue.cpp
• stack.h, stack.cpp

In the header les you will also nd the documentation in javadoc format (that you should know if you took java 1 and/or java 2 and/or algorithm & data structure classes) for each of those elements.

You will implement the class methods in the le .cpp les.

main.cpp implement the Main() function and plays with your code a bit. It is meant as aid for debugging and grading purpose, so you are not allowed to modify it, unless specied. See image.