Description

Build three classes that conform to the following interfaces.Use arrays in creating your classes (e.g., do not use the built-inArrayList class when creating the ArrayList-like interface). Extendthe sample driver below to completely test the FIFO nature of aQueue, the LIFO nature of a stack and the arbitrary inserts andremoves in an ArrayList-like structure. Sample Driver:ArrayBasedDataStructuresDriver.javaPreview the documentView in anew window

ArrayList-like Interface

void insert(Object, int index): Add the object at the specifiedindex.

Object remove(int index): Remove and return the object at thespecified index. (This should behave like the corresponding methodin Java’s built-in ArrayList class; see Savitch’s description.)

int size()

String toString()

boolean isEmpty()

int indexOf(Object): Returns -1 if not found

boolean equals(Object): Compare sizes and elements in the datastructure.

Object get(int index): Returns the object at indexspecified.

Stack Interface (LIFO)

void push(Object)

Object pop()

int size()

String toString()

boolean isEmpty()

boolean equals(Object)

Queue Interface (FIFO)

void enqueue(Object)

Object dequeue()

int size()

String toString()

boolean isEmpty()

boolean equals(Object)

Hints and Tips

• Deliverables: You should turn in four .java files, three arefor your classes and the fourth is your test harness (driver).

• You should practice building drivers and even more advancedtesting harnesses yourself. The above driver is merely a startingpoint that you can use to initially exercise your code. In lecture,we will talk about what a testing harness should do. For thisassignment, you can just display the results of your test toscreen. Once we’ve gone through exception handling, you will haveall the skills needed to write the harness the way I described inclass.

• A reminder that Stacks should be LIFO, queues should be FIFO,and ArrayLists can add and remove in arbitrary order.

• The data structures should hold objects of class Object.

• Your code should not depend on absolute path specifications orany other environment-specific specifications. We may take off upto 3 points from any submission that has such a specification. (Tothose using Eclipse, this is a particularly easy mistake to makebecause Eclipse will often add in a package statementautomatically.) The grader may make reasonable accommodations butgenerally should not have to change your code to run it on his/hermachine. If you’re not sure how to make your submissionnon-environment-specific, please see me. The program should not askfor user input from the console.

Q: The list of methods I’m supposed to write seems to be missingmethods I need in order for me to actually create and use aninstance of the class. For instance, my ArrayList-like class, if itdoes not have an add or append method, cannot be used for anything.Can I create additional methods? A: Yes, you should create anymethods you believe necessary in order to make the class work. Thelist of methods given above are just the ones we’re looking for tograde.

Q: Do these structures hold a fixed size set of items (i.e.,static), or can they grow at runtime? A: Your software should beable to automatically resize your array once capacity is reached,and may be tested beyond 100 elements. Remember that stacks,queues, etc. are (in the abstract) infinite capacity datastructures.

Q: What is FIFO and LIFO? A: Good question.

Q: How will you test this code? A: Tests may use the samestrategies and techniques shown to you in the first few HWs, butmore complete.

Q: Are comments (file headers, method headers, inline comments)important? A: Keep in mind the grading rubric and how much commentsare worth.

Q: I think there is a way to relate these classes viainheritance. Should I do this? A: We’ll cover this later in thequarter; you should use no inheritance for this assignment.

Q: If I’m not to use inheritance, then how can I code the equalsmethods in such a way that it can accept input of class Object? A:We’ll see later on (pp. 465-471 to be precise) how to utilizeinheritance principles to properly write the equals method. Fornow, while you are to accept anything of class Object as input, youdon’t have to check what the input types are. That is to say, youdon’t have to return false if the input is a different type thanthe type of the ArrayList, etc. class. To enable the comparison,convert the input into ArrayList (or whatever class isappropriate).