Stack ADT Implementation

The Stack ADT stores arbitrary objects and insertions and deletions of this ADT follow the last-in-first-out (LIFO) scheme like a spring-loaded plate dispenser.

Main stack operations:

• void push(object): inserts an element
• object pop(): removes and returns the last inserted element

Auxiliary stack operations:

• object top(): returns the last inserted element without removing it
• integer size(): returns the number of elements stored
• boolean isEmpty(): indicates whether no elements are stored

Array-based stack

This is a simple way of implementing the Stack ADT using an array. Here, elements are added from left to right and a variable keeps track of the index of the top element.

let S be an array being used in a stack. Pseudocode for array-based stack is:

Algorithm size()
    return t + 1

Algorithm pop()
    if isEmpty() then
        throw EmptyStackException
    else
        t <- t - 1
return S[t + 1]

Algorithm push(o)
    if t = S.length  1 then
        throw StackFullException
    else
        t <- t + 1
        S[t] <- o

Here, we've presented you the implementation of the algorithm with java.

public class Stack {
    private static final int CAPACITY=10;
    private int capacity;
    private int top=-1;
    private Object [] obj;

    public Stack(int cap){
        capacity=cap;
        obj=new Object[capacity];
    }
    public Stack(){
        this(CAPACITY);
    }

    public int size(){
        return top+1;
    }
    public Object top(){
        if(isEmpty())
            return "Stack is empty.";
        return obj[top];
    }

    public boolean isEmpty(){
        return top<0;
    }

    public boolean isFull(){
        return size()>=capacity;
    }

    public void push(Object o){
        if(size()>=capacity){
            System.out.println("Stack is full.");
            return;
        }
        obj[++top]=o;
    }

    public Object pop(){
        if(isEmpty()) return "Stack is empty.";

        Object temp;
        temp=obj[top];
        obj[top--]=null;
        return temp;
    }
}

Performance

For n be the number of elements in the stack

• The space used is O(n)
• Each operation runs in time O(1)

Limitations

• The maximum size of the stack must be defined at creation and cannot be changed
• Trying to push a new element onto a full stack causes an implementation-specific exception