The crux of Java collections - Stack, Queue & Bags

Collections is one of the most important standard library available in Java. It allows developers to take the power of generics and Iterator and develop code which expects less input from the user and allows good reusability. All references are from Dr.Sidgewich codebase. Collections can be implemented using linked list or array.

Here I am going show my implementation of Queue using basic re-sizing array, implements Iterable interface and is generic. Below is shown the class diagram. This can be easily ported into stack and bags using simple logic changes.

Code:

package george.queue;

import java.util.Iterator;

public class VariableCapacityQueue implements Iterable {
private E[] s;
private int N = 0;

public VariableCapacityQueue() {
s = (E[]) new Object[1];
}

public boolean isEmpty() {
return N == 0;
}

public void enqueue(E item) {
if (N == s.length)
resize(2 * s.length);
s[N++] = item;
System.out.println("array size is "+s.length);
// array size increament verified
}

public E dequeue() {
// return s[--N];//just moves the pointer but not the element//So
// modifying code
E temp = s[0];
s[0] = null;
moveElements(s.length);
N--;
// The above two steps prevents loitering
if (N > 0 && N == s.length / 4)// otherwise will terminate at -1 itself
resize(s.length / 2);
System.out.println("array size is " + s.length);
return temp;
}

private void resize(int capacity) {
E[] copy = (E[]) new Object[capacity];
for (int i = 0; i < N; i++)
copy[i] = s[i];
s = copy;
}

private void moveElements(int capacity) {
E[] copy = (E[]) new Object[capacity];
for (int i = 1; i < N; i++)
// first element in queue removed so n reduced by 1
copy[i - 1] = s[i];
s = copy;
}

public class ListIterator implements Iterator {
private int i = 0;

public boolean hasNext() {
return i < N;
}

public void remove() {
}

public E next() {
return s[i++];
}
}

public Iterator iterator() {
return new ListIterator();
}


}

Performance:

Order of Growth:

Running time is worst when compared to Linked List implementation because of moveElements() method being called each time something is dequeued.  Thus dequeue operation has a order of growth  O(N^2). Enqueue operation consumes in the order of O(N) for elements of size N. Any suggestion to improve dequeue implementation is welcome.

Memory:

The memory consumption will be almost similar to the one shown below. Expect for the fact that we are using generics so the 8N + 24 for String  will be xN + 24 depending upon the datatype used for storing in the array. Similarly padding will change accordingly.