Assignment 2: Creating ADTs and Implementing Data
Structures
Description
In this assignment, you’ll work in groups to write your own ADTs for a stack and a queue, and
then create working versions of an arraylist, a doubly linked list, a stack and a queue using the
Test-Drive Development approach of testing your implementations.
Equipment and Materials
For this assignment, you will need:
• Eclipse, Java 8 and JUnit 4
Instructions
This assignment consists of three parts, to be completed outside of class time. See the course
outline and Brightspace for due dates. Complete this assignment with your assigned group.
Part A: Create ADTs and Implement 4 data structures (90 marks)
Using the specifications below:
1. Create your own stack and queue contracts as Java interfaces.
2. Design unit tests for implementations of the ListADT, StackADT and QueueADT
provided by your instructor.
Note: Your instructor will use a different set of JUnit tests to test your implementations.
3. Implement your utility classes for an arraylist, doubly linked list, a stack and a queue.
There are two submission folders for this assignment. The requirements for each submission
are outlined in the Submission Deliverables section of this document. Each of the two
submissions has a separate due date. See Brightspace for exact due dates.
Part B: Complete an Evaluation as a Group (5 marks)
After completing the work outlined in Part A, check your work against the provided marking
criteria. Your instructor will refer to your group’s self-evaluation when grading the assignment
and will provide further feedback and grade adjustments as needed. Your instructor is
responsible for awarding the group’s final grade.
1. Open the Marking Criteria documents (MarkingCriteria_Assignment2.docx) and save a
copy with your group’s name.
© 2023, Southern Alberta Institute of Technology 1
2. As a group, discuss how well you met each criterion and assign yourselves a mark for
each row in the table. You may include a short, point form, explanation for your mark in
the Notes column.
3. Save this file for submission to Brightspace along with your completed code.
Part C: Complete a Peer Assessment (5 marks)
Each student must also complete a peer assessment of their group members. Your instructor
will provide further submission details.
Assignment Specifications
Important: Read the specifications very carefully. If you are uncertain about any of the
requirements, discuss it with your instructor.
1. Write your own [Link] and [Link] interface with all the required
functionalities as method stubs with appropriate pre-conditions, post-conditions,
parameters, return values and expected exceptions using proper Javadoc notations.
Note: These 2 files are the only requirements for submission 1.
2. Create a complete set of JUnit tests in a class called [Link] based on the
supplied [Link] and [Link] interfaces.
Note: Ensure all tests fail before moving to the next step.
3. Write an implementation for the utility class [Link] using the supplied
[Link] and [Link] interfaces using an array as the underlying data structure to
store the elements in this list.
Note: You can NOT modify the ADTs provided in any way!
4. Completely test the implementation of [Link] for correct functionality using the
set of JUnit test from the previous step.
5. Repeat steps 2–4 for the utility class [Link] using a linked list as the underlying data
structure to store each element in a node, based on the same [Link] and
[Link] interfaces provided by your instructor.
a. Your implementation should also include a [Link] class.
b. Name the complete set of JUnit test functions [Link].
Note: If you’re following the TDD approach correctly and have created JUnit tests against
the ListADT interface, the same tests apply to your DLL as well!
6. After the due date of submission 1, submission 2 will be released with the ADTs you will
need for the following steps.
© 2023, Southern Alberta Institute of Technology 2
7. Create a complete set of JUnit test functions in a class called [Link] based on
the instructor-supplied [Link] and [Link].
Note: Ensure all tests fail before moving to the next step.
8. Write an implementation for the utility class [Link] using the [Link] and
[Link] interfaces provided by your instructor. Use your [Link]
implementation as the underlying data structure to store the elements of the stack.
9. Repeat steps 7-8 for the utility class [Link] using the [Link] and
[Link] interfaces provided by your instructor. Use your [Link] implementation
as the underlying data structure to store elements of the queue.
a. Include a complete set of JUnit test functions in a class called
[Link] based on the instructor supplied [Link] and
[Link], again using the TDD approach.
Warning
Implement this project using ONLY the libraries that you developed for the MyStack, MyQueue,
MyArrayList and MyDLL.
The exception is using the [Link]() or [Link]() methods to resize your array
in MyArrayList, the toArray methods and the Iterator implementations. You are also allowed to
use any of the standard exceptions in the Java library such as NullPointerException and
NoSuchElementException.
You will be penalized 50% of your final mark for the assignment if you use the java classes
from the [Link].*, or similar packages beyond the exceptions listed above. If you’re unsure,
discuss it with your instructor.
Submission Deliverables
Submission 1: Stack and Queue ADTs (16 marks)
Your group’s submission should include a zipped folder which includes the following items and
nothing else:
1. Your [Link]
2. Your [Link]
Note: Although you do not need to submit it at this time, you may want to review the Marking
Criteria document to make sure you have completed this submission correctly.
© 2023, Southern Alberta Institute of Technology 3
Name your group’s assignment submission folder as your group name followed by the
assignment number (e.g., [Link]).
Upload your group’s .zip file to Brightspace by the specified due date and time.
Submission 2: Data Structures (74 marks)
Your group’s submission should include a zipped folder which includes the following items:
1) Your completed javadoc using the “-private” option when generated, and the output
placed in the doc directory of the project.
2) A folder containing the complete Eclipse project directory.
3) The completed Marking Criteria document containing your group’s evaluation of your
application.
Name your group’s assignment submission folder as your group name followed by the
assignment number (e.g., [Link]).
Upload your group’s .zip file to Brightspace by the specified due date and time.
No late assignments will be accepted.
© 2023, Southern Alberta Institute of Technology 4
