使用栈操作逆置栈中的内容
[!Tip]
本节源代码见Github链接🔗
问题描述
给定一个栈，如何只使用栈操作(push和pop)逆置栈中的内容
核心思路
将栈中所有元素递归出栈，直至栈空 每次递归向上步骤时，将上一步中出栈的元素插入栈底
实现代码
【👉🏻>>点击展开查看代码】
/**
* 使用栈操作逆置栈中的内容
*
* @className: StackReversal
* @author: Max Solider
* @date: 2023-06-08 23:04
*/public class StackReversal {
private static void reverseStack(LLStack stack) {
if (stack.isEmpty()) {
return;
}
String temp = stack.pop();
reverseStack(stack);
insertAtBottom(stack, temp);
}
private static void insertAtBottom(LLStack stack, String data) {
if (stack.isEmpty()) {
stack.push(data);
return; }
String temp = stack.pop();
insertAtBottom(stack, data);
stack.push(temp);
}
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");
reverseStack(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)，用于扫描长度为n的链表。
空间复杂度
空间复杂度为O(1)，用于存储临时变量。