Stack

My notes on the stack abstract data type with an implementation using an array in Java.

You can find the complete code for this and other data structures here: data structures and algorithms

A stack is an abstract data type that mimics a real world stack where you can place elements on the top or you can take the top element. The behavior of the stack is described as last in first out (LIFO).

Common Operations for a stack includes:

Operation	Complexity
push(element)	O(1)
pop()	O(1)

Push will place a new element on the top of the stack.

public boolean push(T valueToPush) {
    if(size == innerArray.length) {
        return false;
    }
    innerArray[size] = valueToPush;
    size++;
    return true;
}

Pop takes out the top element from the stack and returns it.

public T pop() {
    if(size == 0) {
        throw new NullPointerException("empty stack");
    }
    T valueToPop = innerArray[size - 1];
    innerArray[size - 1] = null;
    size--;
    return valueToPop;
}

In this implementation the capacity of the stack is the capacity of the inner array. We keep track of the size of the stack by increasing or decreasing the size with every pop and push, by doing this we always know that top is at innerArray[size-1] and when we do a push we put new element at innerArray[size].

Implementing a stack using a linked list would be even easier because we can keep prepending a new node to the linked list with every push and for the pop we only need to get the first element, remove it from the list and then return it.

Download the complete code for this and other data structures here: data structures and algorithms.