An efficient Stack implementation with getMin() and getMax() methods

When we use stack to keep a collection of numbers, we might want to know what are the minimum and maximum numbers in the stack. 

Suppose we are pushing {72,12,55,78,22,34} into a stack, this is what happens

Action	Stack Elements (Top ... Bottom)	Min	Max
push(72)	72	72	72
push(12)	12,72	12	72
push(55)	55,12,72	12	72
push(78)	78,55,12,72	12	78
push(22)	22,78,55,12,72	12	78
push(34)	34,22,78,55,12,72	12	78

If we pop the stack above 3 times, the max should change to 72; if we pop 2 more times, the min should change to 72. It sounds like we need a data structure that keeps the current min and max when we push or pop the stack. Indeed, a stack is a perfect choice here. When pushing a number to the stack, we also push the current min and max values into the min and max stacks respectively. Similarly, when poping out a number from the stack, we also pop out from the min and max stacks, such that the top of the min and max stacks will always have the min and max values of the current stack respectively.

The complexity of the getMin() and getMax() methods are O(1), regardless of how many items are in the stack, same as the push(item) and pop() methods.

Here is an implementation of the Stack with getMin() and getMax() methods

import java.util.Stack;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class SmartStack<E extends Comparable<E>> {

    private ReentrantReadWriteLock readWriteLock = new ReentrantReadWriteLock();
    private ReentrantReadWriteLock.ReadLock readLock = readWriteLock.readLock();
    private ReentrantReadWriteLock.WriteLock writeLock = readWriteLock.writeLock();

    private Stack<E> mins = new Stack<E>();
    private Stack<E> maxs = new Stack<E>();
    private Stack<E> delegate = new Stack<E>();

    public E push(E item) {
        writeLock.lock();
        try {
            // stores the current min to the mins stack
            if (mins.isEmpty() || (!mins.isEmpty() && item.compareTo(mins.peek()) < 0)) {
                mins.push(item);
            } else {
                mins.push(mins.peek());
            }

            // stores the current max to the maxs stack
            if (maxs.isEmpty() || (!maxs.isEmpty() && item.compareTo(maxs.peek()) > 0)) {
                maxs.push(item);
            } else {
                maxs.push(maxs.peek());
            }

            return delegate.push(item);
        } finally {
            writeLock.unlock();
        }
    }

    public E pop() {
        writeLock.lock();
        try {
            E item = delegate.pop();
            // pop both mins and maxs stacks, such that peeking on them will tell us the current min or max
            mins.pop();
            maxs.pop();
            return item;
        } finally {
            writeLock.unlock();
        }
    }

    public E peek() {
        readLock.lock();
        try {
            return delegate.peek();
        } finally {
            readLock.unlock();
        }
    }

    public E getMin() {
        readLock.lock();
        try {
            return mins.peek();
        } finally {
            readLock.unlock();
        }
    }

    public E getMax() {
        readLock.lock();
        try {
            return maxs.peek();
        } finally {
            readLock.unlock();
        }
    }

    public boolean empty() {
        readLock.lock();
        try {
            return delegate.empty();
        } finally {
            readLock.unlock();
        }
    }

    public int search(E item) {
        readLock.lock();
        try {
            return delegate.search(item);
        } finally {
            readLock.unlock();
        }
    }
    
}

Here is the unit test of the above class written in Groovy

import org.junit.Before
import org.junit.Test

class SmartStackTest {

    SmartStack stack

    @Before
    public void before() {
        stack = new SmartStack()
        stack.push(72)
        stack.push(12)
        stack.push(55)
        stack.push(78)
        stack.push(22)
        stack.push(34)
    }

    @Test
    public void canGetCurrentMinValue() {
        assert stack.min == 12

        5.times { stack.pop() }

        assert stack.min == 72
    }

    @Test
    public void canGetCurrentMaxValue() {
        assert stack.max == 78

        4.times { stack.pop() }

        assert stack.max == 72
    }

    @Test
    public void canPeek() {
        assert stack.peek() == 34
    }

    @Test
    public void isEmpty() {
        assert !stack.empty()
    }

    @Test
    public void canSearch() {
        // the 1-based position from the top of the stack where the object is located
        assert stack.search(34) == 1
        assert stack.search(22) == 2
        assert stack.search(78) == 3
        assert stack.search(55) == 4
        assert stack.search(12) == 5
        assert stack.search(72) == 6
        // not in the stack should return -1
        assert stack.search(11112) == -1
    }
    
}