Java 6 - ArrayDeque

Java programmers are getting rich day by day (as the new versions and other frameworks come into existence), as the Java Collections Framework is hosting a lot of different datastructures and algorithm implementations. The latest one I came across is 'ArrayDeque' from Java version 6.

ArrayDeque is an implementation of the 'Deque' interface, which is a short form for "Double Ended Queue's". Double Ended Queue's extend 'Queue' and support adding and removing elements from both ends. In a Queue, you can add from one end and remove from the other. Also, Deque's can be used as a Queue and also a 'Stack'. ArrayDeque has no capacity restrictions like some other data structures (although you can specify that in one of its constructors). ArrayDeque is not threadsafe, as other collections like HashMap, et al. If you want it thread-safe, use 'LinkedBlockingQueue', which implements the 'BlockingQueue' interface, which further extends from 'Deque' interface.

A 'Deque' can be traversed from both directions programmatically using 'iterator' and 'descendingIterator' methods. Deque is doubly linked and can be compared to 'LinkedList', which also implements a 'Deque', apart from List. In LinkedList, you can access an element randomly, by the element's index, which you cant do in Deque's. It was designed this way to make it more efficient.

This kind of datastructure, which can be operated as a 'Queue', 'Stack' and can be traversed from both ends, is pretty useful in certain scenarios. A couple of 'backtracking' and other useful algorithms can be easily implemented with this kind of 'off-the-shelf' datastructures available from the 'Java Collection Framweork'.

A couple of months/years back, I had to code my own implementation to implement some algorithms. Ofcourse, its fun and a learning experience, but with ready-made stuff like this, it saves some time for a Java developer. And ofcourse, its better and useful for any developer to know the implementation 'behind-the-scenes'. By the way, Java is getting more abstract day by day (more high-level) with all these implementations and frameworks popping up from everywhere.

Below is a trivial Java program, for testing/demonstrating the new 'ArrayDeque' class from 'Java 6 Collections Framework':

import java.util.ArrayDeque;
import java.util.Iterator;

public class ArrayDequeTest
{
public static void main(String[] args) 
{    
ArrayDeque arrDeque = new ArrayDeque();

arrDeque.add("mercedes");
arrDeque.add("porsche");
arrDeque.add("audi");

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println();

arrDeque.addLast("bmw");
arrDeque.add("PORSCHE");
arrDeque.addLast("Ferrari");

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println();

for(Iterator descendingIter = arrDeque.descendingIterator();descendingIter.hasNext();) {
System.out.println(descendingIter.next());
}

System.out.println();
System.out.println("First Element : " + arrDeque.getFirst());
System.out.println("Last Element : " + arrDeque.getLast());
System.out.println("Contains \"porsche\" : " + arrDeque.contains("porsche"));

arrDeque.addFirst("porsche");

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

arrDeque.removeLastOccurrence("porsche");

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

arrDeque.removeFirstOccurrence("porsche");
System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println();
System.out.println("Popped Element : " + arrDeque.pop());

arrDeque.push("porsche");        
System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Size of Array Deck : " + arrDeque.size());

System.out.println("\n Peek : " + arrDeque.peek());

System.out.println("\n Peek First : " + arrDeque.peekFirst());
System.out.println("\n Peek Last : " + arrDeque.peekLast());

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Poll First : " + arrDeque.pollFirst());
System.out.println("\n Poll Last : " + arrDeque.pollLast());

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Poll : " + arrDeque.poll());

System.out.println("\n Peek First : " + arrDeque.peekFirst());
System.out.println("\n Peek Last : " + arrDeque.peekLast());

arrDeque.offerFirst("porsche");
arrDeque.offerLast("what the heck?");

System.out.println();

for(Iterator iter = arrDeque.iterator();iter.hasNext();) {
System.out.println(iter.next());
}

System.out.println("\n Get First : " + arrDeque.getFirst());
System.out.println("\n Get Last : " + arrDeque.getLast());

System.out.println("\n Element : " + arrDeque.element());

Object[] objArray = arrDeque.toArray();
System.out.println("\n Object Array Size : " + objArray.length);

String[] strArray = (String[]) arrDeque.toArray(new String[0]);
System.out.println("\n String Array Size : " + strArray.length);

ArrayDeque arrDequeClone = arrDeque.clone();
System.out.println("Clone Size : " + arrDequeClone.size());

System.out.println("arrDeque == arrDequeClone : " + (arrDeque == arrDequeClone));

System.out.println("arrDeque.equals(arrDequeClone) : " + arrDeque.equals(arrDequeClone));
}
}



For more info, check the docs from Sun's website. I'll post some more info, if I happen to spend some more time and implement an algorithm or any other imp stuff, using this datastructure.

Dont Smack The Stack (Deal With Stack Overflow Exceptions)

At times, Java programmers come across this scenario when they have to handle 'Stack Overflow' exception in Java. This probably and mostly happens due to some petty mistakes in the code. Stack overflow happens when all the memory that is allocated to the stack is totally used. Most of the programming languages have limited memory for the stack. So, when stack memory is totally used, it results in program crash.

Stack overflow usually happens when a recursive function is used infinitely (which is probably due to some naive coding mistake). Alternatively, it can also happen when a very large stack variable is used.

Some programming languages (specially functional programming languages like 'Scheme') use 'Tail Recursion' to avoid 'Stack Overflow' errors and to improve efficiency. In this kind of technique, the last statement/operation in a method/function is a recursive call. By this use of logic, recursions can easily be transformed to iterations and thus help in effective use of memory/data-structures.

Below are some scenario's in which this kind of java exception happens:

1) Infinite Recursion:

If you have designed java applications with interfaces or abstract classes, sometimes you might bump into situations, where in, you have overridden a method from some interface/class that you are implementing and you mistakenly called the method of the interface/class, instead of calling some other method or implementing a totally new functionality. This code would not throw any compile time errors. But, at runtime, you would be surprised to see 'Stack Overflow' exceptions. Below is one trivial example:

public interface Interface1 {
public void doSomeShit();
}


Here's a class that implements 'Interface1', overrides the method and calls the same method. This is pretty stupid coding, but there might be scenario's where you might not notice because of code complexity or due to neglect.

public class Interface1Impl implements Interface1
{
public static void main(String[] args) {
Interface1Impl i = new Interface1Impl();
i.doSomeShit();

}

public void doSomeShit() {
doSomeShit();
}
}


The above program compiles fine, but throws 'Stack Overflow' exception, at runtime.

Example 2:

public class StackOverflowDemo1
{
public static void main(String[] args) 
{
StackOverflowDemo1 sofd = new StackOverflowDemo1();
sofd.method1();
}

public void method1() {
method2();
}

public void method2() {
method1();
}
}



Example 3:

public class StackOverflowDemo2
{
public static void main(String[] args) 
{
StackOverflowDemo2 sofd = new StackOverflowDemo2();
sofd.valueOf(sofd);
}

public String valueOf(Object obj) {
return valueOf(obj);    
}
}



The above code throws 'Stack Overflow' exception, as you are doing nothing special, but overriding the 'String' objects 'valueOf' method and calling it again.

The JVM (Java Virtual Machine) uses stack to store the state of java method invocations (excluding Native methods). The state of a method is in its local variables, parameters, return value and whatever business/plain logic involved in that method. Java's programming model further splits 'Java Stack' into 'Stack frames' (which is probably a programming concept for efficiently handling the state of a method, et al things). Each and every method's state is associated with a particular stack frame. When the method completes, the stack frame is deallocated. This is how the methods parameters, local variables, return type variables are always thread safe.

If you have problems with Java stack or if you want to increase the size of Java Stack, you can use the following command:

Java - Xss Stack-Size

Replace the 'Stack-Size', with the size of memory that you need.

Thats it! Happy coding and 'Protect The Stack'! ;-) (Now, the heap's calling..huh)