栈元素排序
[!Tip]
本节源代码见Github链接🔗
问题描述
设计一个可以把栈中元素按照升序排列的排序算法，并且算法不能对栈的具体实现方式由限定
核心思路
用两个栈，一个原栈sStack，辅助栈rStack，将sStack中元素依次弹出放入rStack中，并在弹出过程中与rStack栈顶元素对比，若sStack待弹出元素大于rStack栈顶元素，则将rStack中栈顶元素放回sStack中。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 栈元素排序
*
* @className: StackSorter
* @author: Max Solider
* @date: 2023-06-09 08:32
*/public class StackSorter {
public static LLStack sort(LLStack s) {
LLStack r = new LLStack();
while (!s.isEmpty()) {
if (r.isEmpty()) {
r.push(s.pop());
}
String temp = s.pop();
while (!r.isEmpty() && Integer.valueOf(r.top()) < Integer.valueOf(temp)) {
s.push(r.pop());
}
r.push(temp);
}
return r;
}
public static void main(String[] args) {
LLStack stack = new LLStack();
stack.push("2");
stack.push("6");
stack.push("4");
stack.push("1");
stack.push("5");
stack = sort(stack);
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
时间复杂度
时间复杂度为O(n^2)，用于扫描栈。
空间复杂度
空间复杂度为O(n)，用于临时栈。