HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Stack with 'getMinimum' operation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
withoperationstackgetminimum

Problem

Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure and no other data structure like arrays, list, .. etc.

Looking for code review, optimizations, best practices.

public class StackMinimum{
       /*
        * Composition triumphs over inheritance :)
        */
       private final Stack stack1 = new Stack();
       private final Stack stack2 = new Stack();

       public void push(T item) {
           stack1.push(item);
           if (stack2.isEmpty() || ((Comparable) item).compareTo(stack2.peek())  stack1 = new StackMinimum();
        stack1.push(1);
        stack1.push(2);
        stack1.push(3);

        assertEquals(1, (int)stack1.getMinimum());

        stack1.push(-1);
        assertEquals(-1, (int)stack1.getMinimum());

        stack1.pop();
        assertEquals(1, (int)stack1.getMinimum());

        while(!stack1.isEmpty()) {
            assertEquals(1, (int)stack1.getMinimum());
            stack1.pop();
        }
    }
}

Solution

You have a bug: .getMinimum() loses track if you push the same new minimum value twice.

You should use both inheritance and composition.

Use inheritance for the "main" stack, because your data structure is a stack — one with an extra feature. That gives you the read-only operations .peek(), .size(), and .isEmpty() for free.

Use composition for the "minimum" stack, as you have currently done.

Context

StackExchange Code Review Q#55386, answer score: 4

Revisions (0)

No revisions yet.