For example:
stack s:
head 3, 9, 6, 2 tail
tmp = 3
stack r:
empty
push 3 to r
stack r:
3
tmp = 9
3 < 9
push 9 to r
stack r:
3, 9
tmp = 6
9 > 6
push 9 to s
stack s:
9, 2
3 < 6
push 6 to r
stack r
3, 6
tmp = 9
6 < 9
push 9 to r
stack r:
3, 6, 9
tmp = 2
9, 6, 3, > 2
push 9, 6, 3, to s
stack s:
3, 6, 9
push 2 to r
stack r:
2
push 3, 6, 9, to r
stack r:
2, 3, 6, 9
If the head of r is smaller than tmp, we need to push all elements in r that is larger than tmp back to s, at worst case, we will have to push all elements in r back to s, (like when tmp = 2 in the example), so this operation will take O(n). The outer loop will take another O(n) time, so in total O(n^2).
public class SortAStack { public static Stacksort(Stack s) { Stack r = new Stack (); while (!s.isEmpty()) { int tmp = s.pop(); while(!r.isEmpty() && r.peek() > tmp) { s.push(r.pop()); } r.push(tmp); } return r; } public static void main(String[] args) { Stack s = new Stack (); s.push(1); s.push(5); s.push(4); s.push(2); s.push(6); s.push(9); s.push(3); for (int i : sort(s)) { System.out.println(i); } } }
No comments:
Post a Comment