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!

1 comment:

Sarika A said...

An overwhelming web journal I visit this blog, it's unfathomably amazing. Unusually, in this present blog's substance made inspiration driving truth and reasonable. The substance of data is enlightening. We are providing the best services click on below links to visit our website.
Oracle Fusion HCM Training
Workday Training
Okta Training
Palo Alto Training
Adobe Analytics Training