逆置队列中前k个元素
[!Tip]
本节源代码见Github链接🔗
问题描述
给定一个整数k和一个整数队列，将队列中前k个元素逆置，其余元素顺序保持不变。例如，假设队列为[11, 12, 13, 14, 15, 16, 17, 18, 19, 20]，k为4，重新排列后队列为[14, 13, 12, 11, 15, 16, 17, 18, 19, 20]
核心思路
借助一个辅助栈，通过栈来将队列中的元素重排序
实现代码
【👉🏻>>点击展开查看代码】
/**
* 逆置队列中前k个元素
*
* @className: ReverseQueueFirstKElements
* @author: Max Solider
* @date: 2023-06-11 09:40
*/public class ReverseQueueFirstKElements {
public static void reverseQueueFirstKElements(int k, ArrayQueue queue, int size) {
if (queue.isEmpty() || size < k) {
return;
}
LLStack stack = new LLStack();
for (int i = 0; i < k; i++) {
stack.push(String.valueOf(queue.deQueue()));
}
while (!stack.isEmpty()) {
queue.enQueue(Integer.valueOf(stack.pop()));
}
for (int i = 0; i < size - k; i++) {
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);
reverseQueueFirstKElements(4, queue, 8);
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)，需要辅助栈。