交叉排列队列中前后部分的元素
[!Tip]
本节源代码见Github链接🔗
问题描述
给定一个整数队列，将队列中前半部分和后半部分的元素相互交叉排列。例如，假设队列为[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]，重新排列后队列为[11, 16, 12, 17, 13, 18, 14, 19, 15, 20]
核心思路
需要时间复杂度和空间复杂度都为O(n)，借助一个辅助队列，移动元素直到队列和栈中各自存放一半的元素，且都是按原顺序排列。最后将队列和栈中的元素交叉入队，直到栈空
实现代码
【👉🏻>>点击展开查看代码】
/**
* 交叉排列队列中的元素
*
* @className: InterLeavingQueue
* @author: Max Solider
* @date: 2023-06-10 22:55
*/public class InterLeavingQueue {
public static void interLeavingQueue(int size, ArrayQueue queue) {
if (queue.isEmpty()) {
return;
}
LLStack stack = new LLStack();
for (int i = 0; i < size / 2; i++) {
stack.push(String.valueOf(queue.deQueue()));
}
while (!stack.isEmpty()) {
queue.enQueue(Integer.valueOf(stack.pop()));
}
for (int i = 0; i < size / 2; i++) {
queue.enQueue(queue.deQueue());
}
for (int i = 0; i < size / 2; i++) {
stack.push(String.valueOf(queue.deQueue()));
}
while (!stack.isEmpty()) {
queue.enQueue(Integer.valueOf(stack.pop()));
queue.enQueue(queue.deQueue());
}
}
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(10);
queue.enQueue(1);
queue.enQueue(2);
queue.enQueue(3);
queue.enQueue(4);
queue.enQueue(5);
queue.enQueue(6);
queue.enQueue(7);
queue.enQueue(8);
interLeavingQueue(8, queue);
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
}
}
时间复杂度
时间复杂度为O(n)，每次移动元素的时间复杂度都是O(n)。
空间复杂度
空间复杂度为O(n)，需要辅助栈。