Search This Blog

Monday 22 July 2013

Stacks in JDK

In the previous post we saw the various queue implementations available in Java. Today I decided to check out stacks:
public static void main(final String[] args) {      final Stack<Integer> stack = new Stack<Integer>();
      System.out.println("Item pushed is " + stack.push(1));
      System.out.println("Item pushed is " + stack.push(2));
      System.out.println("Item pushed is " + stack.push(3));

      System.out.println("Item popped is " + stack.pop());
      System.out.println("Top element is " + stack.peek());
      System.out.println("Item popped is " + stack.pop());

      System.out.println("Is stack empty ? " + stack.isEmpty());
      System.out.println("Item popped is " + stack.pop());
      System.out.println("Item popped is " + stack.pop());
   }
The stack is from the java utils package. It has a push method to add items. A pop method to pop items. Additional methods include:
  • peek () to get a reference to top of stack element without popping it
  • isEmpty() checks to see if stack is empty.
The output of the method is as below:
Item pushed is 1
Item pushed is 2
Item pushed is 3
Item popped is 3
Top element is 2
Item popped is 2
Is stack empty ? false
Item popped is 1
Exception in thread "main" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at com.test.collections.StackTest.main(StackTest.java:19)
An attempt to pop of an empty stack will result in a run time EmptyStackException. This class is heavily used in the JDK.
From the class docs:
The Stack class represents a last-in-first-out (LIFO) stack of objects. 
It extends class Vector.
A more complete and consistent set of LIFO stack operations is provided 
by the {@link Deque} interface and its implementations, which should be 
used in preference to this class.
As seen the Stack class extends from the Vector class, a thread safe implementation of Lists. It is therefore slow and hence they recommend to not use it. The alternative would be:
public static void main(final String[] args) {

      final Deque<Integer> stack = new ArrayDeque<Integer>();
      stack.push(1); // void return type
      stack.push(2);
      stack.push(3);

      System.out.println("Item popped is " + stack.pop());
      System.out.println("Top element is " + stack.peek());
      System.out.println("Item popped is " + stack.pop());
      System.out.println("Is stack empty ? " + stack.isEmpty());
      System.out.println("Item popped is " + stack.pop());
      System.out.println("Item popped is " + stack.pop());
   }
Item popped is 3
Top element is 2
Item popped is 2
Is stack empty ? false
Item popped is 1
Exception in thread "main" java.util.NoSuchElementException
 at java.util.ArrayDeque.removeFirst(Unknown Source)
 at java.util.ArrayDeque.pop(Unknown Source)
 at com.stacks.TestDQStack.main(TestDQStack.java:20)
Notable points of difference are:
  • The push method has a void return type. 
  • If we try to pop an element from an empty stack we get a runtime exception - NoSuchElementException. 
  • The pop method internally calls removeFirst method
  • The push method internally calls the addFirst method

1 comment: