Java数据结构代写 | COMP 2402 Abstract Data Types and Algorithms Assignment #2
Purpose & Goals
Generally, the assignments in this course are meant to give you the opportunity to practice with the
topics of this course in a way that is challenging yet also manageable. At times you may struggle and at
others it may seem more straight-forward; just remember to keep trying and practicing, and over time
you will improve.
Specifically, assignment 2 aims to improve your understanding of the array-based data structures we’ve
been talking about by:
• Using the ArrayList, ArrayQueue, and/or ArrayDeque interfaces to solve a variety of problems,
recognizing when one may be more appropriate than another, and
• Implementing our own special Stack and Deque-like interfaces using some of the concepts we’ve
been learning about.
Part A: The Setup
Start by downloading and decompressing the Assignment 2 Zip File (comp2402a2.zip), which contains a
skeleton of the code you need to write. You should have the files: Part0.java, Part1.java, Part2.java,
Part3.java, MyStack.java, MyFastStack.java, MyDeque.java, MyFastDeque.java and Tester.java.
As with assignment 1, you can test Parts0-3 using the command line or input/output files. You can test
Parts 4 and 5 with the Tester class included in the zip file. As before, you’ll want to add your own tests as
this is just given as a basis on which you should build. The submission server will do thorough testing; it
is your job to read the specifications as carefully as possible, and to examine your own code for potential
problems and test those cases.
Part B: The Interface
As with assignment 1, the file Part0.java in the zip file actually does something (although it’s a
different something than assignment 1). You can use its doIt(x) method as a starting point for your
solutions. Compile it. Run it. Test out the various ways of inputting and outputting data. You should not
need to modify Part0.java, it is a template.
You can download some sample input and output files for each question as a zip file (a2-io.zip). If you
find that a particular question is unclear, you can possibly clarify it by looking at the sample files for that
question. Note that these are very limited tests; you can and should add to them to test your code more
thoroughly as the server tests are much more extensive.
1. [10 marks] Read the input one line at a time and output every x’th line, starting with line 0,
where x>0 is a parameter to the doIt method. To get full points, try to use as little extra
space and time as possible.
2. [10 marks] Read the input one line at a time and output every x’th line from the end, starting
with the last line, where x>0 is a parameter to the doIt method. To get full points, try to use
as little extra space and time as possible.
3. [10 marks] Read the input one line at a time, and output the last x lines in reverse order, where
x>=0 is a parameter to the doIt method. If there are fewer than x lines, print the n < x
existing lines in reverse. (The lines themselves are forwards, their order is reversed. See the
sample input/output to clarify if you need it.) To get full points, try to use as little extra space
and time as possible.
Part C: The Implementation
The starter code contains MyStack and MyDeque interfaces, which are modified Stack and Deque
interfaces described below. Part C involves you completing implementations of these interfaces,
MyFastStack and MyFastDeque, in the files MyFastStack.java and MyFastDeque.java,
respectively. These are described in more detail in Parts 4 and 5 below.
Both MyStack and MyDeque represent a sequence of items where any neighbouring duplicates have
(both) been removed. For example, the original sequence [a,b,c,c,b,d] would shrink to just
[a,d] (since once the neighbouring c,c are removed, b and b become neighbouring duplicates and
are also removed.)
As another example, the sequence [a,b,c,c,c,b,d] would shrink to [a,b,c,b,d] since once
the first neighbours c,c are removed, a third c remains.
The individual elements are atomic (i.e. indivisible), so [ab,ab] shrinks to , and [ba,ab] does not
shrink at all.
Finally, if you have the sequence [a,b,c,c,b,a], this would shrink to the empty sequence .