Stack Data Structure & Problems

Nivetharavi

6 min readSep 10, 2026

What is a Stack? 🥞

A Stack is a data structure that follows LIFO:

Last In → First Out

Think of a stack of plates.
The plate we put last is the one we remove first.

Get Nivetharavi’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Common Stack Methods:

push() → Add an element to the top
pop() → Remove the top element
peek() → See the top element without removing it
isEmpty() → Check whether the stack is empty

Why do we use Stack in DSA?

Stack is useful when we need to work with recent or nearest elements or when we need to go back and remove previous elements.

1. Previous Smaller Element:

https://www.geeksforgeeks.org/problems/previous-smaller-element/1

What is the problem?
For every element, find the nearest smaller element on the left.
If there is no smaller element → -1.

Example: [4, 5, 2, 10, 8]
Output: [-1, 4, -1, 2, 2]

Why do we use Stack?
We use a stack to keep the useful previous elements and remove elements that cannot be the answer.

Logic 🧠

Find the previous smaller element.
I need the nearest element on the left that is smaller than the current element.
Pop bigger/equal elements.
If the stack top is bigger than or equal to the current element, pop it because it cannot be the smaller element I need.
Find the answer.
Stack empty → no smaller element → -1
Otherwise → stack top is the previous smaller element.

Simple thought:

Current element
      ↓
Is top >= current?
      ↓
    YES → POP
      ↓
    Repeat
      ↓
Smaller element found
      ↓
Stack top = Answer

Code:

class Solution {
public static ArrayList<Integer> prevSmaller(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();
        for(int i = 0; i < arr.length; i++) {
            // Remove bigger/equal elements
            while(!stack.isEmpty() && arr[i] <= stack.peek()) {
                stack.pop();
            }
            // No smaller element found
            if(stack.isEmpty()) {
                result.add(-1);
            }
            // Stack top is the previous smaller element
            else {
                result.add(stack.peek());
            }
            // Store current element
            stack.push(arr[i]);
        }
        return result;
    }
}

class Solution {
    public static ArrayList<Integer> prevSmaller(int[] arr) {

       Stack<Integer> stack = new Stack<>();
       ArrayList<Integer> result = new ArrayList<>();

       for(int i = 0; i < arr.length ; i++){
           // No smaller element found
           if(stack.isEmpty()){
               result.add(-1);
           }else {
               while(!stack.isEmpty() && arr[i] <= stack.peek()){
                   stack.pop();
               }
               // No smaller element found
               if(stack.isEmpty()){
                   result.add(-1);
               }
               // Stack top is the previous smaller element
               else{
                   result.add(stack.peek());
               }
           }

           stack.push(arr[i]);
       }
       // Store current element
       return result;
    }
}

Example: arr = [4, 5, 2]

4 → stack empty → -1
    stack = [4]

5 → 4 is smaller → 4
    stack = [4, 5]

2 → 5 >= 2 → pop
    4 >= 2 → pop
    stack empty → -1
    stack = [2]

Answer: [-1, 4, -1]

Remember 🔥: Pop Bigger/Equal → Find Smaller → Push Current

Time & Space:
Time: O(n), Space: O(n)

2. Stock Span Problem:

https://www.geeksforgeeks.org/problems/stock-span-problem-1587115621/1

What is the problem?
For every day, find the number of continuous previous days where the price is less than or equal to today’s price.
Current day is also included.

Example: [100, 80, 90, 120]
Output: [1, 1, 2, 4]

Why do we use Stack?
We use a stack to keep the indexes of useful previous prices and remove prices that are already included in today’s span.

Logic 🧠

Find the previous greater price.
I need the nearest price on the left that is greater than today’s price.
Pop smaller/equal prices.
If the stack top price is smaller than or equal to today’s price, pop it because it is included in today’s span.
Find the span.
Stack empty → no greater price → all previous days are included → i + 1
Otherwise → previous greater price found → i - stack.peek()
Store the current index.
Push the current index so that future days can use it.

Simple thought:

Current price
      ↓
Is top price <= current?
      ↓
    YES → POP
      ↓
    Repeat
      ↓
Greater price found
      ↓
Calculate span

Code:

class Solution {

public ArrayList<Integer> calculateSpan(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();

        for(int i = 0; i < arr.length; i++) {
            // Remove smaller/equal prices
            while(!stack.isEmpty() && arr[i] >= arr[stack.peek()]) {
                stack.pop();
            }
            // No greater price found
            if(stack.isEmpty()) {
                result.add(i + 1);
            }
            // Previous greater price found
            else {
                result.add(i - stack.peek());
            }
            // Store current index
            stack.push(i);
        }
        return result;
    }
}

class Solution {
    public ArrayList<Integer> calculateSpan(int[] arr) {
        
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> result = new ArrayList<>();
        
        for(int i = 0; i < arr.length; i++){
            // No greater price found
            if(stack.isEmpty()){
                result.add(i + 1);
                
            } else {
                // Remove smaller/equal prices
                while(!stack.isEmpty() && arr[i] >= arr[stack.peek()]){
                    stack.pop();
                }
                // No greater price found
                if(stack.isEmpty()){
                    result.add(i + 1);
                } 
                // Previous greater price found
                else {
                    result.add(i - stack.peek());
                }
            }
            // Store current index
            stack.push(i);
        }
        
        return result;
    }
}

Example: arr = [100, 80, 90, 120]

100 → stack empty → 1
      stack = [0]

80 → 100 is greater → 1
     stack = [0, 1]

90 → 80 <= 90 → pop
     100 is greater
     2 - 0 = 2
     stack = [0, 2]

120 → 90 <= 120 → pop
      100 <= 120 → pop
      stack empty → 4
      stack = [3]

Answer: [1, 1, 2, 4]

Remember 🔥: Pop Smaller/Equal → Find Greater → Calculate Span

Time & Space:
Time: O(n), Space: O(n)

3. Online Stock Span:

https://leetcode.com/problems/online-stock-span/

What is the problem?
For each new stock price, find the number of continuous previous days where the price was less than or equal to today’s price.

Example: [100, 80, 60, 70, 60, 75, 85]
Output: [1, 1, 1, 2, 1, 4, 6]

Why do we use Pair?
We need both:
value → to compare prices
index → to calculate the span

Logic 🧠

Find the previous greater price.
I need the nearest previous price that is greater than today’s price.
Pop smaller/equal prices.
If the stack top is smaller than or equal to today’s price, pop it because it cannot be the previous greater price.
Calculate the span.
Stack empty → no greater price → index + 1
Otherwise → previous greater price found → index - previous greater index

Simple thought:

Current price
      ↓
Is top <= current?
      ↓
    YES → POP
      ↓
    Repeat
      ↓
Previous greater found
      ↓
Calculate span using index

Code:

class StockSpanner {

    // Store index and price together
    class Pair {
        int index;
        int value;

        Pair(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

    // Stack stores previous prices with their indexes
    Stack<Pair> stack = new Stack<>();

    int currentIndex = 0;

    public StockSpanner() {
        
    }

    public int next(int price) {

        // Create pair for today's price
        Pair pair = new Pair(currentIndex, price);

        currentIndex++;

        // No previous price
        if(stack.isEmpty()) {
            stack.push(pair);
            return pair.index + 1;

        } else {

            // Remove all smaller/equal prices
            // They are included in today's span
            while(!stack.isEmpty() && 
                  pair.value >= stack.peek().value) {
                stack.pop();
            }

            // No greater price found
            // So all previous days are included
            if(stack.isEmpty()) {
                stack.push(pair);
                return pair.index + 1;

            } else {

                // Previous greater price found
                int temp = stack.peek().index;

                // Store today's price for future days
                stack.push(pair);

                // Distance from previous greater price
                return pair.index - temp;
            }
        }
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner obj = new StockSpanner();
 * int param_1 = obj.next(price);
 */

Remember 🔥:
Pop Smaller/Equal → Find Previous Greater → Calculate Span → Push Current

Time & Space: Time: O(n), Space: O(n)

Previous Smaller
→ Find: Previous Smaller
→ Pop: Bigger / Equal
→ Answer: stack.peek() / -1

Stock Span
→ Find: Previous Greater
→ Pop: Smaller / Equal
→ Answer: Index Difference

Online Stock Span
→ Find: Previous Greater
→ Pop: Smaller / Equal
→ Answer: Index Difference

Stack Data Structure & Problems

What is a Stack? 🥞

Get Nivetharavi’s stories in your inbox

Why do we use Stack in DSA?

1. Previous Smaller Element:

2. Stock Span Problem:

3. Online Stock Span:

Written by Nivetharavi

Responses (1)

More from Nivetharavi

Building Your First Spring App: A Step-by-Step Beginner’s Guide

Learn Spring with a Vehicle Shop example: IoC, Beans, Dependency Injection, XML configuration, and Autowiring.

Tree Medium Level

Maximum Width of Binary Tree: https://leetcode.com/problems/maximum-width-of-binary-tree/description/

SLIDING WINDOW (FIXED SIZE)

Max Sum Subarray of size K: https://www.geeksforgeeks.org/problems/max-sum-subarray-of-size-k5313/1

Tree Leetcode Solutions

Binary Tree Inorder Traversal: https://leetcode.com/problems/binary-tree-inorder-traversal/description

Recommended from Medium

The CDC Playbook for Data Engineers (Part 3)

This is the 3rd article in the CDC Playbook series. In Part 1, we looked at fundamentals of Change Data Capture.

Building a Modern Data Engineering Pipeline: From Raw Data to Analytics with Python, SQL, and…

Data engineering is the invisible machinery behind almost every data-driven product.

10 Essential Tools for Data Analysts, Data Engineers, and Data Scientists

Not libraries. Not code. The tools that run the real work.

What Is ACID for Data Engineers

Delta Lake hands you two of the four letters. The other two were always your job, and the docs say so if you read past the first line.

The Data Engineering Stack for 2027: What I’d Keep, What I’d Drop

Fewer tools, more of them owned by the same company, and a “skip it if” for every recommendation I make.

The Data Science Skills I’d Learn in 2027 (If I Started Over)

I spent too long collecting tools and not enough time learning to judge whether my work was any good.

Responses (1)

More from Nivetharavi

Building Your First Spring App: A Step-by-Step Beginner’s Guide

Learn Spring with a Vehicle Shop example: IoC, Beans, Dependency Injection, XML configuration, and Autowiring.

Tree Medium Level

Maximum Width of Binary Tree: https://leetcode.com/problems/maximum-width-of-binary-tree/description/

SLIDING WINDOW (FIXED SIZE)

Max Sum Subarray of size K: https://www.geeksforgeeks.org/problems/max-sum-subarray-of-size-k5313/1

Tree Leetcode Solutions

Binary Tree Inorder Traversal: https://leetcode.com/problems/binary-tree-inorder-traversal/description

Recommended from Medium

The CDC Playbook for Data Engineers (Part 3)

This is the 3rd article in the CDC Playbook series. In Part 1, we looked at fundamentals of Change Data Capture.

Building a Modern Data Engineering Pipeline: From Raw Data to Analytics with Python, SQL, and…

Data engineering is the invisible machinery behind almost every data-driven product.

10 Essential Tools for Data Analysts, Data Engineers, and Data Scientists

Not libraries. Not code. The tools that run the real work.

What Is ACID for Data Engineers

Delta Lake hands you two of the four letters. The other two were always your job, and the docs say so if you read past the first line.

The Data Engineering Stack for 2027: What I’d Keep, What I’d Drop

Fewer tools, more of them owned by the same company, and a “skip it if” for every recommendation I make.

The Data Science Skills I’d Learn in 2027 (If I Started Over)

I spent too long collecting tools and not enough time learning to judge whether my work was any good.