An unbound / growing Stack implementation backed by an Array.

The stack is a list-like structure in which elements may be inserted or removed from only one end. While this restriction makes stacks less flexible than lists, it also makes stacks both efficient (for those operations they can do) and easy to implement. Many applications require only the limited form of insert and remove operations that stacks provide. In such cases, it is more efficient to use the simpler stack data structure rather than the generic list.

Stack is called a “LIFO” list, which stands for “Last-In, First Out.” Note that one implication of the LIFO policy is that stacks remove elements in reverse order of their arrival. The accessible element of the stack is called the top element. Elements are not said to be inserted, they are pushed onto the stack.

In this post we will have an unbound stack with different growth strategy. The options are Tight and Double. This is same implementation as ArrayList. In Tight strategy it creates a new Stack with current capacity + 5 and in Double strategy it creates a Stack of double the size of current capacity and then copies all the elements from the Old Stack to New Stack.

The ADT of the growing STACK is :

package com.tuturself.stack;

public interface Stack < E > {

 /**
  * size() - returns the size of the stack
  * 
  * @return {@link Integer}
  */
 public int size();

 /**
  * isEmpty() - returns true if empty,false otherwise
  * 
  * @return {@link Boolean}
  */
 public boolean isEmpty();

 /**
  * push() - pushes the element at the top of the stack
  * 
  * @param element
  * @throws Exception
  */
 public void push(E element) throws Exception;

 /**
  * pop() - pops the elements from the top of the stack
  * 
  * @return {@link Element}
  * @throws Exception
  */
 public E pop() throws Exception;

 /**
  * top() - Only returns the top element without removing
  * 
  * @return
  * @throws Exception
  */
 public E top() throws Exception;
}

Now let us check the Implementation ArrayStack.java

package com.tuturself.stack;

/**
 * This is a unbound stack with different growth strategy. The options are Tight
 * and Double. This is same implementation as ArrayList. In Tight strategy it
 * creates a new Stack with current capacity + 5 and in Double strategy it
 * creates a Stack of double size of current capacity and then copies all the
 * elements from the Old Stack to New Stack.
 */
public class ArrayStack < E > implements Stack < E > {
 private int top = -1;
 private int capacity;
 private static int defaultSize = 10;
 private int overflowStrategy;
 private E[] stack;

 public ArrayStack() {
  this(0);
 }

 public ArrayStack(int overflowStrategy) {
  this(defaultSize, overflowStrategy);
 }

 @SuppressWarnings("unchecked")
 public ArrayStack(int capacity, int overflowStrategy) {
  this.capacity = capacity;
  stack = (E[]) new Object[capacity];
  this.overflowStrategy = overflowStrategy;
 }

 @Override
 public int size() {
  return top + 1;
 }

 @Override
 public boolean isEmpty() {
  if (top == -1)
   return true;
  return false;
 }

 @Override
 public void push(E element) throws Exception {
  if (top == capacity - 1) {
   // different strategies to deal with overflow
   if (this.overflowStrategy == 2)
    tightStrategy();
   else if (this.overflowStrategy == 1)
    growthStrategy();
   else
    throw new Exception("stack full..cant enter");
  }
  stack[++top] = element;
 }

 @Override
 public E pop() throws Exception {
  if (top == -1)
   throw new Exception("stack empty..cant pop");
  return stack[top--];
 }

 @Override
 public E top() throws Exception {
  if (top == -1)
   throw new Exception("stack empty");
  return stack[top];
 }

 @SuppressWarnings("unchecked")
 public void tightStrategy() {
  E[] newStack = (E[]) new Object[capacity + 5];
  for (int i = 0; i < capacity; i++)
   newStack[i] = stack[i];
  stack = newStack;
  capacity = capacity + 5;
 }

 @SuppressWarnings("unchecked")
 public void growthStrategy() {
  E[] newStack = (E[]) new Object[capacity * 2];
  for (int i = 0; i < capacity; i++)
   newStack[i] = stack[i];
  stack = newStack;
  capacity = capacity * 2;
 }

 public void showStack() {
  for (int i = 0; i < capacity; i++) {
   if (i > top)
    System.out.print(" - ");
   else
    System.out.print(" " + stack[i] + " ");
  }
  System.out.println(" ");
 }

}

Now lets test the Stack :

public class StackTest {

 public static void main(String[] args) {
  try {
   for (int n = 10; n <= 100; n = n * 10) {
    long startTime = System.currentTimeMillis();
    ArrayStack < Integer > myStack = new ArrayStack < Integer > (2);
    System.out.println("Running test for " + n + " elements");
    for (int i = 0; i < n; i++)
     myStack.push(i);
    System.out.println(myStack.size());
    System.out.println(((System.currentTimeMillis() - startTime)) + " miliseconds with tight strategy");
    startTime = System.currentTimeMillis();
    ArrayStack < Integer > myStackTwo = new ArrayStack < Integer > (1);
    for (int i = 0; i < n; i++)
     myStackTwo.push(i);
    System.out.println(((System.currentTimeMillis() - startTime)) + " miliseconds with growth strategy");
   }
  } catch (Exception exception) {
   exception.printStackTrace();
  }
 }
}

 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself