A data structure is a container that includes a set of operations for retrieving and adding elements to the container. A stack, for example, is a data structure (think stack of books) that holds an ordered collection of elements and removes elements in a Last-In First-Out (LIFO) order. That is, when removing elements the element removed was the last element added. The add and remove operations on stacks are traditionally called push and pop respectively. That is, we push and pop elements on and off the stack.
Another commonly used data structure is called a queue. A queue data structure (think store check out lane) that also holds an ordered collection of elements, except elements in a queue data structure are added at the end and removed from the front. In other words, elements are removed in a First-In First-Out (FIFO) order.
One of the most useful frameworks in the Java Platform is called the Collections Framework. The Java Collections Framework consists of a set of interfaces and classes for a large number of commonly used data structures.
The most basic collection interface is named Collection<E>. The <E> indicates that the interface references an generic type. We’ll talk much more about generics, but for now it is sufficient to know that generic types can hold any type. The Collection interface have a superinterface named Iterable<E>. We’ll learn how to implement the Iterable interface next week and practice implementing it during the next lab.
The Collection interface specifies a set of operations that a class that represents a collection must have. Some of the methods from the documentation that we’re ready to discuss are given below.
- boolean add(E e)
- boolean addAll(Collection<? extends E> c)
- void clear()
- boolean contains(Object o)
- boolean containsAll(Collection<?> c)
- boolean isEmpty()
- boolean remove(Object o)
- boolean removeAll(Collection<?> c)
- boolean retainAll(Collection<?> c)
- int size()
- Object[] toArray()
Notice that these are operations that you can perform on any collection of elements, regardless of whether or not the collection represents a stack, a queue, or some other data structure.
The Collection interface has a number of subinterfaces such as Queue, Set, and List. Each of these subinterfaces, extends Collection and requires additional methods. Let look at the Queue interface. The Queue interface includes the following additional methods:
As per the documentation, these method recognize a head and tail of the queue. In addition, some of the methods return null on error and some throw exceptions. We can also see from the documentation that many concrete classes implement Queue such as ArrayDeque, LinkedList, and PriorityQueue.
In this assignment you’ll be creating an interface named Collection, and interface named Queue that extends Collection, and a concrete class named ArrayQueue that implements Queue. We’ll also write a driver that tests the methods in the ArrayQueue class.
1. Create directories named util6 and a6 as subdirectories in your repository.
2. Create an interface named Collection in the util6/ directory and include it in the util6 package. Require the following methods in the interface
- boolean add(Object o)
- boolean addAll(Object[] arr)
- void clear()
- boolean contains(Object o)
- boolean containsAll(Object[] arr)
- boolean isEmpty()
- boolean remove(Object o)
- boolean removeAll(Object[] arr)
- boolean retainAll(Object[] arr)
- int size()
- Object[] toArray()
3. Create another interface in the util6/ directory named Queue that extends Collection and include it in the util6 package. The Queue interface should include the following methods.
- boolean add(Object e)
- Object element()
- boolean offer(Object e)
- Object peek()
- Object poll()
- Object remove()
4. Create a concrete class in the util6/ directory named ArrayQueue that implements the Queue interface using an array of Objects as the underlying data structure. Include it in the util6 package.
- Include in the ArrayQueue class a default constructor as well as a constructor that has one integer parameter that specifies the initial size of the underlying array.
- The underlying array should not change in size after it has been constructed.
- All methods should act as specified in the Java documentation unless specified otherwise.
- No method should throw ClassCastException, IllegalArgumentException or UnsupportedOperation Exception.
5. Create a driver in the a6/ directory named TestArrayQueue that tests each of the methods in the ArrayQueue class.
6. Create a Makefile in the a6/ directory that allows you to compile with the command ‘make’ and run the driver using the command ‘make run’.
7. When complete, clean the util6/ and a6/ directories and push your repo changes to GitHub.
© 2018 – 2019, Eric. All rights reserved.