20211129.md

Algorithm

用一个栈实现另一个栈的排序

Description

一个栈中的元素都是整型，现在想通过申请另一个栈实现栈顶到栈底元素从大到小排序，请实现当前操作

Solution

public static void sortStackByStack(Stack<Integer> stack){
    Stack<Integer> temp = new Stack<>();
    while(stack.isEmpty()){
       int cur = stack.pop();
       while(!temp.isEmpty() && temp.peek()>cur){
          stack.push(temp.pop());
       }
       temp.push(cur);
    }
    while(!temp.isEmpty()){
      stack.push(temp.pop());
    }
}

Discuss

1. 申请一个辅助栈Temp(从小到大)，当前元素记为cur
2. cur<=Temp的栈顶元素，直接将cur压栈到Temp
3. cur>Temp的栈顶元素, 逐一弹出Temp中的元素，压入stack，直到cur<=Temp,将cur压入Temp
4. 最后将temp的元素全部弹出压入到stack栈

Review

Tip

Share