使用两个栈来实现队列
[!Tip]
本节源代码见Github链接🔗
问题描述
使用两个栈来实现队列
核心思路
使用两个栈S1和S2，入队操作只需要将元素入栈S1，出队操作需要判断：
- 若S2中有元素，则直接出栈S2；
- 若S2中无元素，则需要先将S1出栈并将元素入栈S2 （只需要入栈n-1个元素，最后一个元素即需要出队的元素）
实现代码
【👉🏻>>点击展开查看代码】
/**
* 用两个栈实现队列
*
* @className: QueueWithTwoStacks
* @author: Max Solider
* @date: 2023-06-10 21:29
*/public class QueueWithTwoStacks {
private static LLStack s1 = new LLStack();
private static LLStack s2 = new LLStack();
public static void enQueue(int data) {
if (s1.isFull()) {
return;
}
s1.push(String.valueOf(data));
}
public static String deQueue() {
if (s1.isEmpty() && s2.isEmpty()) {
return "";
}
if (!s2.isEmpty()) {
return s2.pop();
}
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
return s2.pop();
}
public static void main(String[] args) {
System.out.println(deQueue());
enQueue(3);
enQueue(13);
System.out.println(deQueue());
enQueue(2);
enQueue(5);
System.out.println(deQueue());
enQueue(4);
enQueue(15);
System.out.println(deQueue());
System.out.println(deQueue());
System.out.println(deQueue());
System.out.println(deQueue());
System.out.println(deQueue());
System.out.println(deQueue());
System.out.println(deQueue());
System.out.println(deQueue());
System.out.println(deQueue());
}
}
时间复杂度
平均时间复杂度为O(1)。
空间复杂度
空间复杂度为O(n)，用于栈空间。