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

一颗蔬菜 2019-09-23 PM 77℃ 0条

【题目】

一个栈中元素的类型为整型,现在想将该栈从栈顶到栈底按从大到小的顺序排序,只允许申请一个栈,除此之外可以申请新的变量,但不能申请额外的数据结构。如何完成排序?

【解答】

将要排序的栈记为stack,申请的辅助栈记为help。在stack上执行pop操作,弹出的元素记为cur。

  • 如果cur小于或等于help的栈顶元素,就将cur直接压入help。
  • 如果cur大于help栈顶元素,就将help的元素逐一弹出,逐一压入到stack,直到cur小于help栈顶元素,再将cur压入help。

一直执行以上操作,直到stack中的全部元素都压入help。最后将help中的所有元素逐一压入stack中,即完成所有排序。

【代码实现】

import java.util.Stack;

public class SortStackByStack {

    public void sort(Stack stack1) {
        if (stack1.isEmpty()) {
            return;
        }
        Stack<Integer> help = new Stack<Integer>();
        while (!stack1.isEmpty()) {
            int cur = stack1.pop();
            while (!help.isEmpty() && cur > help.peek()) {
                stack1.push(help.pop());
            }
            help.push(cur);
        }
        
        while (!help.isEmpty()) {
            stack1.push(help.pop());
        }
    }  
} 
标签: 算法

非特殊说明,本博所有文章均为博主原创。