# Stack with 'getMinimum' operation

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<T>{
/*
* Composition triumphs over inheritance :)
*/
private final Stack<T> stack1 = new Stack<T>();
private final Stack<T> stack2 = new Stack<T>();

public void push(T item) {
stack1.push(item);
if (stack2.isEmpty() || ((Comparable<T>) item).compareTo(stack2.peek()) < 0) {
stack2.push(item);
}
}

public T pop() {
T item = stack1.pop();
if (item.equals(stack2.peek())) {
stack2.pop();
}
return item;
}

public T peek() {
return stack1.peek();
}

public int size() {
return stack1.size();
}

public T getMinimum () {
return stack2.peek();
}

public boolean isEmpty() {
return stack1.isEmpty();
}
}

public class StackMinimumTest {

@Test
public void test() {
StackMinimum<Integer> stack1 = new StackMinimum<Integer>();
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();
}
}
}

-
+1 for : Composition triumphs over inheritance –  Sleiman Jneidi Jun 26 '14 at 22:27
Use Generics. StackMinimum<T extends Comparable<T>>. Don't cast. –  Boris the Spider Jun 27 '14 at 8:19
Currently the code is bugged. push 5, 3, 3, then pop, and it will report the minimum as 5. Or push 5, 5 then pop twice : EmptyStackException. –  bowmore Jun 27 '14 at 15:17

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.

-
Unfortunately Stack extends Vector, so I guess you have to implement a lot of other methods (like remove) to keep its behavior consistent. –  palacsint Jun 26 '14 at 23:46
Good job spotting the .getMinimum() bug. Changing the < to <= will fix the bug (I think). –  The Dark Jun 27 '14 at 1:29
That is the first thing that I noticed. Solution by TheDark works, but a simpler solution would be to always push with the minimum value. So pop will also always pop from minimum stack. –  justhalf Jun 27 '14 at 8:07
1. I would rename stack1 to delegate and stack2 to minimumStack or something similar to express their purpose and make the code easier to understand.

2. I would use ObjectUtils.min (or max?) instead of

((Comparable<T>) item).compareTo(stack2.peek()) < 0)


compareTo always forces me to check the javadoc to figure out what does its return value mean.

3. Having a loop in the test method is a test smell: Conditional Test Logic

4. The test does not cover the peek nor the size method.

-
I don't agree with introducing a (fairly weighty) dependency like commons lang for no gain. The return of compareTo is very well defined and has been since the dark ages. –  Boris the Spider Jun 27 '14 at 8:18
@BoristheSpider: Yes, I can accept the first part. Anyway, it's just a single <dependency> with Maven. If it's an interview question it shows that the interviewee have some knowledge of the existing libraries (and probably don't reinvent the wheel). Finally, you can still create a similar method in your code to make it readable. I know that compareTo is quite old but this does not mean that anyone should memorize that (instead of focusing on business problems). Extracting out the comparison to a helper method (similar to min) would express the dev's intent and make maintenance easier. –  palacsint Jun 27 '14 at 9:03
Sure, completely agree with extracting if conditions into boolean methods. Just think there need to be more compelling reasons for including dependencies - although cheap to include with Maven, they have their own maintenance costs. –  Boris the Spider Jun 27 '14 at 9:07

It looks very good for me, you can use the extend keyword on generics to insure type safety and to avoid unnecessary casts. And this is called a Bounded type

class StackMinimum<T extends Comparable>{
public void push(T item) {
stack1.push(item);
// to need for the cast here
if (stack2.isEmpty() || item.compareTo(stack2.peek()) < 0) {
stack2.push(item);
}
}
}


Only Comparable types will be welcomed in your stack

-
Shouldn't this be Comparable<T>? –  codesparkle Jun 27 '14 at 0:11
@codesparkle No, it shouldn't, the type is bounded to T where T is Comparable –  Sleiman Jneidi Jun 27 '14 at 0:17
Comparable is the raw usage of the generic interface Comparable<T>. The language specification says: The use of raw types is allowed only as a concession to compatibility of legacy code. The use of raw types in code written after the introduction of generics into the Java programming language is strongly discouraged. (emphasis mine) –  codesparkle Jun 27 '14 at 0:28
Sorry, forgot the link to the JLS –  codesparkle Jun 27 '14 at 0:36
This answer is close, but wrong. Raw types should never be used. –  Boris the Spider Jun 27 '14 at 8:20

As others have noted, Stack extends Vector. As such Stack is a List. The easiest and most readable way to add getMinimum() would be to do this :

import java.util.Collections;
import java.util.Stack;

public class SpecialStack<T extends Comparable<? super T>> extends Stack<T> {

public T getMinimum() {
return Collections.min(this);
}
}


I'm guessing this is homework. As such, you can probably not get around using Stack for this exercise, but note that Stack, as a subclass of Vector, carries synchronized overhead, which in most cases you won't need. So for real life purposes you're better off using ArrayDeque, as even Stack's javadoc suggests itself.

-