forked from Turingfly/cracking-the-coding-interview
-
Notifications
You must be signed in to change notification settings - Fork 0
/
SortStack.java
33 lines (31 loc) · 822 Bytes
/
SortStack.java
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
package chapter03StacksAndQueues;
import java.util.Stack;
/**
* Problem: Write a program to sort a stack such that the smallest items are on
* the top. You can use an additional temporary stack, but you may not copy the
* elements into any other data structure (such as an array). The stack supports
* the following operations: push, pop, peek, and isEmpty.
*
* Solution:
*
* Time Complexity: O(N2)
*
* Space Complexity: O(N)
*
*/
public class SortStack {
public void sort(Stack<Integer> stack1) {
Stack<Integer> stack2 = new Stack<>();
while (!stack1.isEmpty()) {
int tmp = stack1.pop();
while (!stack2.isEmpty() && stack2.peek() > tmp) {
stack1.push(stack2.pop());
}
stack2.push(tmp);
}
// move back to stack1
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
}
}