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