Sort Stack
出处
How to sort a stack in ascending order (i.e. pop in ascending order) with another stack?
Solution
本题明确要求利用两个栈实现一种特定的输出顺序。由于栈限制了输出的顺序,所以要调整栈内部的元素顺序比较困难。但从另一个角度想,我们也许可以在入栈的时候就控制插入的位置,使得栈内的元素都是有序的,即只要保证新栈的元素一定是有序的即可。同时,考虑到栈具有LIFO的输出性质,将一个栈中的元素倾倒到另一个栈,在倾倒回来,元素之间保持原有顺序。
于是我们可以构建如下算法:假设有Stack A和Stack B,Stack A中的元素没有顺序。我们需要把Stack A中的数据有序地加入到Stack B中。每当我们从Stack A中取出一个元素,当该元素不符合Stack B的当前排列顺序时,我们倾倒Stack B的元素,直到该元素可以按顺序入栈。然后,我们恢复之前倾倒的元素。根据栈“将一个栈中的元素倾倒到另一个栈,在倾倒回来,元素之间保持原有顺序”的性质,特别地,我们可以将Stack A看成性质中的“另一个栈”。
Complexity
由于调整一个元素的顺序可能要求将之前的n个元素来回倾倒,故时间复杂度O(n2)
Code
Stack<Integer> sortStack(Stack<Integer> input){
Stack<Integer> output = new Stack<Integer>();
while (!input.isEmpty()){
int value = input.top();
input.pop();
while (!output.isEmpty() && output.top() < value){
input.push(output.top());
output.pop();
}
output.push(value)
}
return output;
}