Stack Data Structure

Stack is a basic data structure which could be compared as logical stack in real world scenario. A stack is a limited access data structure - elements can be added and removed from the stack only at the top.

There are mainly 3 functions that are performed on the stack:

  • push, adds an item to the top of the stack,
  • pop, removes the item from the top
  • peek, returns the item from the top without removing it

Stack always perform Last In First Out(LIFO) operation. Consider a stack with elemnts [1, 2, 3, 4, 5]. 5 being at top. Will perform operation on stack

  1. stack = [1,2,3,4,5]
    operation:pop
    output : 5 , stack=[1,2,3,4]
  2. stack = [1,2,3,4]
    operation:pop
    output : 4, stack=[1,2,3]
  3. stack = [1,2,3]
    operation:push 4
    output : 4, stack=[1,2,3,4]
  4. stack = [1,2,3,4]
    operation:peek
    output : 4 , stack=[1,2,3,4]

Anaylsis of Stack Operations

  1. Push an element O(1)
  2. Pop an elementO(1)
  3. Search an element O(n)

Implementation details: One of the basic ways to create a stack is using arrays.

public class Stack {

	private int array[];
	private int currentIndex = -1;
	
	public Stack(int size) {
		array = new int[size];
	}
	public void push(int number) {
		if (currentIndex >= array.length) {
			//throw exception
			return;
		}
		array[++currentIndex] = number;
	}
	
	public int pop() {
		if (isEmpty()) {
			//throw custom exception
			throw new ArrayIndexOutOfBoundsException("stack is empty");
		}
		return array[currentIndex--];
	}
	
	public int peek() {
		if (isEmpty()) {
			//throw custom exception
			throw new ArrayIndexOutOfBoundsException("stack is empty");
		}
		return array[currentIndex];
		
	}
	
	public boolean isEmpty() {
		return currentIndex == -1; 
	}

	public static void main(String[] args) {
		Stack stack = new Stack(5);
		stack.push(4);
		stack.push(5);
		System.out.println(stack.pop());
		System.out.println(stack.pop());
		stack.push(3);
		System.out.println(stack.pop());
		System.out.println(stack.pop());

	}

}

Output is:
5
4
3
java.lang.ArrayIndexOutOfBoundsException: stack is empty