逆置队列元素
[!Tip]
本节源代码见Github链接🔗
问题描述
设计一个逆置队列元素的算法。要求算法在访问队列元素时，只能使用队列抽象数据类型中的操作
核心思路
借用辅助栈，将队列中的元素依次出队，并入栈，待队列中所有元素放入栈后，再将栈中元素依次入队
实现代码
【👉🏻>>点击展开查看代码】
/**
* 逆置栈中元素
*
* @className: QueueReversal
* @author: Max Solider
* @date: 2023-06-10 21:19
*/public class QueueReversal {
public static ArrayQueue reversal(ArrayQueue queue) {
LLStack stack = new LLStack();
while (!queue.isEmpty()) {
stack.push(String.valueOf(queue.deQueue()));
}
while (!stack.isEmpty()) {
queue.enQueue(Integer.valueOf(stack.pop()));
}
return queue;
}
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(10);
queue.enQueue(2);
queue.enQueue(1);
queue.enQueue(3);
queue.enQueue(7);
queue.enQueue(4);
queue.enQueue(5);
queue.enQueue(9);
queue.print();
queue = reversal(queue);
queue.print();
}
}
时间复杂度
时间复杂度为O(n)，用于扫描长度为n的队列。
空间复杂度
空间复杂度为O(n)，用于栈空间。