栈系列之-排序

2019-11-29 本文已影响0人愤怒的谜团

一、栈实现排序概述

将一个栈内的元素实现排序，光靠一个栈肯定是不够的，因为无法实现元素的调动，所以需要一个辅助栈，还有变量。
实现步骤（创建两个栈，OriginStack和sortedStack）

OriginStack为原始栈，里面存储着需要排序的数据
sortedStack初始为一个空栈
将stack的元素elem弹栈，然后压栈进sortedStack，当然这是有条件的，如果sortedStack为空直接压栈进sortedStack，如果不为空，将elem与sortedStack.GetTop()进行比较，如果elem<=sortedStack.GetTop(),则直接压栈进sortedStack，如果elem>sortedStack.GetTop(),则将sortedStack的元素弹栈然后压栈进stack，然后继续执行比较，这里是个循环，直至达到elem<=sortedStack.GetTop()这个条件或者sortedStack为空栈。
然后将sortedStack的元素依次压栈进OriginStack，OriginStack就是一个从大到小排序的栈了。

二、栈实现排序代码-java

import java.util.Stack;

public class SortedStack {
    Stack<Integer> OriginStack;
    Stack<Integer> sortedStack;
    public SortedStack(Stack<Integer> originStack){
        this.OriginStack = originStack;
        this.sortedStack = new Stack<Integer>(); //创建一个辅助栈
    }

    public void sort(){
        if (OriginStack.size() == 0){return;}

        while (OriginStack.size() != 0){
            //当原始栈存在数据，就一直执行while循环，一直到原始栈为空为止。
            Integer elem = OriginStack.pop();
            if (sortedStack.size() == 0){
                //sortedStack为空，直接压栈
                sortedStack.push(elem);
            }else if (elem <= sortedStack.peek()){
                //满足elem <= sortedStack.peek()，直接压栈
                sortedStack.push(elem);
            }else{
                //当elem > sortedStack.peek()则进行循环，将sortedStack的元素依次对比压栈进OriginStack
                while (elem > sortedStack.peek()){
                    OriginStack.push(sortedStack.pop());
                    if (sortedStack.size() == 0){
                        break;
                    }
                }
                sortedStack.push(elem);
            }
        }
        while (sortedStack.size() != 0){
            OriginStack.push(sortedStack.pop());
        }
    }
    public String toString(){
        return OriginStack.toString();
    }

    public static void main(String[] args) {
        Stack<Integer> oriStack = new Stack<>();
        oriStack.push(9);
        oriStack.push(1);
        oriStack.push(0);
        oriStack.push(2);
        System.out.println(oriStack.toString()); // [9, 1, 0, 2]

        SortedStack sortedStack = new SortedStack(oriStack);
        sortedStack.sort();
        System.out.println(sortedStack.toString());  // [0, 1, 2, 9]
    }
}