14. Implementing Stack in Java

Stack is simply a collection of elements but this collection follows the last-in first-out (LIFO) principle. It means that the element which is inserted last would be removed first. If we insert an element and then remove an element from the collection, then the element that would be removed was the one which was inserted at the last.
The operation of inserting an element is called pushing onto the stack and the operation of removing an element is called popping off the stack.

Technically Stack(or any data structure) is an Abstract Data Type - ADT (an entity that can be specified mathematically and defines a set of instances on which we can perform certain operations).

We can define these data types or ADTs using interface in which we basically give signature of the operations and parameters that operations require.

Stack supports four main methods:

• new(): this method to create a stack.
• push(o:element): here, we specify an element o. The method adds this element to the abstract data type by inserting an object o on to the top of the stack. 
• pop(): it just removes the top element from the stack. If the stack is empty, they should flag an error stating that the stack is empty.
• top():element: top operation returns the top element, it does not remove it and that is how it differs from the pop. Again if the stack is empty then top does not make any sense, it should flag an error.

We can also define below support methods:

• size():integer: returns the number of objects in stack.
• isEmpty(): Boolean: return true if stack is empty else returns false.

Stack data structure is already built-in class in java.util package, still we can define our own interface:

public interface Stack {
 
 // accessor methods
 public int size();
 public boolean isEmpty();
 public Object top() throws EmptyStackException;
 
 // update methods
 public void push(Object element);
 public Object pop() throws EmptyStackException;
}

After creating the interface, we have to implement this. Below is example of how to implement this using an array:

public class ArrayStack implements Stack {

 // default capacity of Stack
 public static final int CAPACITY = 1024;

 private int N; // maximum capacity of Stack
 private Object S[]; // S holds the elements of the Stack
 private int t = -1; // top element of the Stack

 // initialize the stack with default capacity
 public ArrayStack() {
  this(CAPACITY);
 }

 // initialize the stack with given capacity
 public ArrayStack(int cap) {
  N = cap;
  S = new Object[N];
 }

 // Returns the current stack size
 @Override
 public int size() {
  return (t + 1);
 }

 // Return true if stack is empty
 @Override
 public boolean isEmpty() {
  return (t < 0);
 }

 // Return the top stack element
 @Override
 public Object top() throws EmptyStackException {
  if (isEmpty())
   throw new EmptyStackException();
  return S[t];
 }

 // Push a new element on the stack
 @Override
 public void push(Object element) {
  if (size() == N)
   throw new StackOverflowError();
  S[++t] = element;
 }

 @Override
 public Object pop() throws EmptyStackException {
  Object elem;

  if (isEmpty())
   throw new EmptyStackException();

  elem = S[t];
  S[t--] = null;

  return elem;
 }

}