Stacks & QueuesProblem 1 of 38

Implement Stack from Scratch

Brute Force
Time: O(1)
Space: O(n)
Optimal
Time: O(1)
Space: O(n)

Problem Statement

Implement a stack data structure from scratch that supports the following operations:

  • push(x): Add element x to the top of the stack
  • pop(): Remove and return the top element
  • top() / peek(): Return the top element without removing it
  • isEmpty(): Check if the stack is empty
  • size(): Return the number of elements in the stack

Example:

push(1) -> Stack: [1] push(2) -> Stack: [1, 2] push(3) -> Stack: [1, 2, 3] top() -> Returns: 3 pop() -> Returns: 3, Stack: [1, 2] size() -> Returns: 2 isEmpty() -> Returns: false

Approach 1: Using Array

Intuition

Use a fixed-size array to store stack elements. Maintain a top pointer that tracks the index of the topmost element. Initially, top = -1 indicates an empty stack.

Algorithm

  1. Initialize an array of fixed size and set top = -1
  2. For push: increment top and store element at arr[top]
  3. For pop: return arr[top] and decrement top
  4. For peek: return arr[top] without modifying top
  5. Check bounds for overflow and underflow
java
public class Stack {
    private int[] arr;
    private int topIndex;
    private int capacity;
    
    public Stack(int size) {
        capacity = size;
        arr = new int[capacity];
        topIndex = -1;
    }
    
    public Stack() {
        this(1000);
    }
    
    public void push(int x) {
        if (topIndex >= capacity - 1) {
            throw new RuntimeException("Stack Overflow");
        }
        arr[++topIndex] = x;
    }
    
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack Underflow");
        }
        return arr[topIndex--];
    }
    
    public int top() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return arr[topIndex];
    }
    
    public boolean isEmpty() {
        return topIndex == -1;
    }
    
    public int size() {
        return topIndex + 1;
    }
    
    public static void main(String[] args) {
        Stack s = new Stack(100);
        s.push(10);
        s.push(20);
        s.push(30);
        System.out.println("Top: " + s.top());      // 30
        System.out.println("Pop: " + s.pop());      // 30
        System.out.println("Size: " + s.size());    // 2
        System.out.println("Empty: " + s.isEmpty()); // false
    }
}

Complexity Analysis

  • Time Complexity: O(1) for all operations
  • Space Complexity: O(n) where n is the capacity of the stack

Approach 2: Using Linked List (Dynamic Size)

Intuition

Use a singly linked list where the head represents the top of the stack. Push adds a new node at the head, and pop removes the head node. This allows dynamic sizing without fixed capacity.

Algorithm

  1. Maintain a head pointer for the top of the stack
  2. For push: create new node, point it to current head, update head
  3. For pop: store head's data, move head to next node, return data
  4. No size limit - grows dynamically
java
public class StackLinkedList {
    private class Node {
        int data;
        Node next;
        
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    
    private Node head;
    private int count;
    
    public StackLinkedList() {
        head = null;
        count = 0;
    }
    
    public void push(int x) {
        Node newNode = new Node(x);
        newNode.next = head;
        head = newNode;
        count++;
    }
    
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack Underflow");
        }
        int val = head.data;
        head = head.next;
        count--;
        return val;
    }
    
    public int top() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return head.data;
    }
    
    public boolean isEmpty() {
        return head == null;
    }
    
    public int size() {
        return count;
    }
    
    public static void main(String[] args) {
        StackLinkedList s = new StackLinkedList();
        s.push(10);
        s.push(20);
        s.push(30);
        System.out.println("Top: " + s.top());      // 30
        System.out.println("Pop: " + s.pop());      // 30
        System.out.println("Size: " + s.size());    // 2
        System.out.println("Empty: " + s.isEmpty()); // false
    }
}

Complexity Analysis

  • Time Complexity: O(1) for all operations
  • Space Complexity: O(n) where n is the number of elements in the stack

Key Takeaways

  1. Array-based implementation is simpler but has fixed capacity
  2. Linked List implementation allows dynamic sizing but uses extra memory for pointers
  3. All basic stack operations (push, pop, top, isEmpty) should be O(1)
  4. LIFO (Last In First Out) is the fundamental property of a stack
  5. Always handle edge cases: empty stack and full stack (for array implementation)
Next
Implement Queue from Scratch