Sunday, June 14, 2015

Stack Implementation in Java

Stack is a LIFO (Last In First Out) data structure and supports various operations as specified by the interface below:
public interface IStack<T> {
    public boolean push(T value);
    public T pop();
    public void clear();
    public boolean contains(T value);
    public int size();
}

The Stack can be implemented using an Array or a LinkedList. The Array implementation will be having an underlying array which will be re-sized accordingly. The source code is pretty straight forward and does not need much explanation.
public class ArrayStack<T> implements IStack<T> {
 private static final int MINIMUM_SIZE = 10;
 private T[] array = (T[]) new Object[MINIMUM_SIZE];
 private int size = 0;

 @Override
 public boolean push(T value) {
  int stackSize = this.size;
  if (stackSize >= array.length) {
   array = Arrays.copyOf(array, (stackSize + (stackSize>>1)));
  }
  array[size++] = value;
  return true;
 }

 @Override
 public T pop() {
  if (size <= 0) return null;
  T t = array[--size];
  array[size] = null;
  int stackShrinkSIze = size;
  if (size >= MINIMUM_SIZE && size < (stackShrinkSIze + (stackShrinkSIze<<1))) {
   System.arraycopy(array, 0, array, 0, size);
  }
  return t;
 }
 @Override
 public void clear() {
  size = 0;
 }
 
 @Override
 public boolean contains(T value) {
  for (int i = 0; i < size; i++) {
     T item = array[i];
     if (item.equals(value))
    return true;
  }
  return false;
 }
 @Override
 public int size() {
  return size;
 }
}

Similarly we can make use of LinkedList to implement Stack in Java.
public class LinkedStack<T> implements IStack<T> {
 private Node<T> top = null;
 private int size = 0;

 public LinkedStack() {
  top = null;
  size = 0;
 }
 @Override
 public boolean push(T value) {
  return push(new Node<T>(value));
 }
 private boolean push(Node<T> node) {
  if (top == null) { 
   top = node;
  } else {
   Node<T> oldTop = top;
   top = node;
   top.below = oldTop;
   oldTop.above = top;
  }
  size++;
  return true;
 }
 @Override
 public T pop() {
  if (top==null) return null;

  Node<T> nodeToRemove = top;
  top = nodeToRemove.below;
  if (top != null) top.above = null;

  T value = nodeToRemove.value;
  size--;
  return value;
 }
 @Override
 public void clear() {
  top = null;
  size = 0;
 }
 @Override
 public boolean contains(T value) {
  if (top == null) return false;
  Node<T> node = top;
  while (node != null) {
   if (node.value.equals(value)) return true;
   node = node.below;
  }
  return false;
 }

 @Override
 public int size() {
  return size;
 }
}

On a side note we have a class named Stack in Java as well but it usage is deprecated. That's all. I hope you liked the post!

No comments: