patternjavaMinor
Stack with 'getMinimum' operation
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.
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:
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
Use composition for the "minimum" stack, as you have currently done.
.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.