forked from jin-zhe/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumStack.java
More file actions
75 lines (68 loc) · 1.74 KB
/
Copy pathMinimumStack.java
File metadata and controls
75 lines (68 loc) · 1.74 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.Stack;
/**
* Task Description:
* Implement a data structure that supports "find minimum" on top of the other
* stack operations "push", "peek" and "pop" in O(1). Also, space Complexity for
* finding minimum element should be O(1)
*/
public class MinimumStack {
Stack<Integer> mainStack, minStack;
public MinimumStack() {
mainStack = new Stack<Integer>();
minStack = new Stack<Integer>();
}
/**
* Push an item to the stack
* @param num item to be pushed
*/
public void push (Integer num) {
if (minStack.empty()) {
minStack.push(num);
mainStack.push(num);
}
else {
int min = minStack.peek();
if (num <= min) {
minStack.push(num);
mainStack.push(num);
}
else { mainStack.push(num); }
}
}
/**
* Get the most recently pushed item
* @return the most recently pushed item
*/
public Integer peek() {
return mainStack.peek();
}
/**
* Remove the most recently pushed item
* @return the most recently pushed item
*/
public Integer pop() {
if (mainStack.peek() == minStack.peek()) { minStack.pop(); }
return mainStack.pop();
}
/**
* Gets the minimum item in the current stack
* @return minimum item
*/
public Integer getMin() {
return minStack.peek();
}
public static void main(String[] args) {
MinimumStack ms = new MinimumStack();
ms.push(2);
System.out.println(ms.peek()); // should print 2
ms.push(3);
System.out.println(ms.peek()); // should print 3
System.out.println(ms.getMin()); // should print 2
ms.push(1);
System.out.println(ms.peek()); // should print 1
System.out.println(ms.getMin()); // should print 1
ms.pop(); // pop 1
System.out.println(ms.peek()); // should print 3
System.out.println(ms.getMin()); // should print 2
}
}