Make sure you read the sections in the above on how to interpret CodeLab string comparison feedback
Overview
In this lab you are presented with a collection of 'classic' methods on the various data structures.
The CodeLab Framework
Each exercise consists of one or more methods corresponding to a task on a container: clearing, searching, reversing, selecting, etc. You are not being asked to write
a full app; the container itself is available for you to use (via the supplied interface — see next paragraph), and drivers have been written to load up the container
as well as print out any necessary diagnostics and other output to allow you to determine whether your algorithm worked.
Each of the containers occupies its own subtopic in this lab. The subtopic entry in the TOC (e.g., the entry for 'Stack') contains the interface for the container as well as any
other relevant information you may need so that my driver and your code play nicely together.
The Containers
In order to allow a more pseudocode-like expressivity, I have coded up the standard containers rather than using the JCF classes. This avoids decisions like using ArrayList vs LinkedList for a list,
HshSet vs TreeeSet for a set, etc All the containers are available to you in all the exercises of this lab.
The following is the set of the available containers and their methods available to you. The semantics of each methods is as presented for each container.
Stack
void push(E e)
E pop()
E peek()
int size()
boolean isEmpty()
Queue
void add(E e)
E remove()
E peek()
boolean isEmpty()
PriorityQueue
void add(E e)
E remove()
E peek()
boolean isEmpty()
Deque
void addFirst(E e)
E removeFirst()
void addLast(E e)
E removeLast()
int size()
boolean isEmpty()
List
void add(E e)
void add(int index, E e)
E get(int index)
boolean isEmpty()
E remove(int index)
E set(int index, E e)
int size()
Node
All node-based structures will use the same Node type, containing the union of all the fields for a singly-, doubly- and binary-tree- based
underlying container. Notice these are fields (i.e., instance variables), not methodsi, but not declared private so your code has access to them.
E data
Node next, prev, right, left
Set
void add(E e)
boolean contains(E e)
boolean isEmpty()
int size()
Map
V get(K k)
boolean isEmpty()
void put(K k, V v)
boolean containsKey(K k)
int size()
The Submission Class
The method(s) of your solution should be made static and placed in a wrapping class, whose name will be supplied to you (in ()'s in the title of the instructions of the
exercise), and corresponds to the container and task at hand;
e.g. StackClear, DequeReverse, TreeSearch, etc.
The Input
The input will be one or more data files and stdout; while you can see them in the interactive session section of the instructions, for the most part, they are not of any real concern to you;
the driver will print out the loaded container in a more readable fashion.
The Output
The output will contain all the information you need to debug your code if necessary. Typically, the initial container (i.e., the container loaded up by the driver with the data from the input file)
will be printed first, followed by the result(s) of the driver calling your method. As usual with your container labs, correctness is determined by your matching the expected output
(i.e., the output produced by MY solution).
A Sample Exercise
An example has been supplied … clearing a stack. The solution has been provided as 'initial code', i.e., code that is already present in the Work Area as a launching point for your submission.
In this instance, there is nothing for you to do other than submit. (I;'m even counting this as one of the labs.)
Implement a method named clear that accepts a stack as its parameter and empties out the stack
void clear(Stack<E> stack) {…}
Stack Search (StackSearch)
Implement a method name search that accepts a stack and a value as its parameters and returns whether the value is contained in the stack. The stack
should remain unchanged after the search.
boolean search(Stack<E> stack, E e) {…}
Stack Reverse (StackReverse)
Implement a method name reverses that elements of its stack parameter.
Implement a method named clear that accepts a queue as its parameter and empties out the queue
void clear(Queue<E> queue) {…}
Queue Search (QueueSearch)
Implement a method name search that accepts a queue and a value as its parameters and returns whether the value is contained in the queue. The queue
should remain unchanged after the search.
boolean search(Queue<E> queue, E e) {…}
Queue Reverse (QueueReverse)
Implement a method name reverses that elements of its queue parameter.
void reverse(Queue<E> queue) {…}
Binary Tree
Binary Tree Size
Implement a method name size that returns the size (number of nodes) in the tree whose root is the node passed in as a parameter.