反向方法反转队列的元素

这不是硬件或任务。 这是我自己练习的东西。

给定一个队列，写一个Reverse方法反转队列的元素。 MyQueue保持不变。

签名：

public Queue reverse(Queue myQueue) { 

注意：不知道Queue是使用节点还是数组创建的。

队列已经实现了我们可以使用的方法：

 void enqueue(T element) T dequeue(); boolean isFull(); boolean isEmpty(); int size(); 

Answer 1

1. 将输入队列的元素出列到堆栈中
2. 从堆栈中弹出元素，将每个元素排入输出队列。

Answer 2

您可以使用堆栈来反转队列。

以下是Java中的内容：

 public void reverse(Queue q) { Stack s = new Stack(); //create a stack //while the queue is not empty while(!q.isEmpty()) { //add the elements of the queue onto a stack s.push(q.serve()); } //while the stack is not empty while(!s.isEmpty()) { //add the elements in the stack back to the queue q.append(s.pop()); } } 

队列的append和serve方法是添加和删除该队列的元素。

这是一个例子：

队列包含元素：

1 2 3 4

当元素添加到堆栈时，数字1将位于列表的底部，4位于顶部：

1 2 3 4 < - 顶部

现在弹出堆栈并将元素放回队列中：

4 3 2 1

我希望这有帮助。

Answer 3

您可以在没有任何其他数组或列表的情况下执行此操作，只需通过递归：

 public static  Queue flip(Queue q) { Queue ret = new Queue<>(); recursiveFlip(q, ret); return ret; } private static  void recursiveFlip(Queue src, Queue dest) { T buffer = src.dequeue(); if(!src.isEmpty()) { recursiveFlip(src, dest); } dest.enqueue(buffer); } 

第一个元素将堆叠在堆栈的“浅”部分中，而最后一个元素将堆叠在“更深”部分中，并且当递归到达结尾时，将首先添加“更深”的值，最后添加“浅”。

但请注意，每个元素意味着更深入递归，因此如果队列太大，将发生堆栈溢出错误。

此外，原始队列不会“翻转”。

Answer 4

我使用了两种不依赖于队列大小的方法。 第一个使用Stack ，第二个使用Java 8 Stream API （最快）。

在我的测试中反转队列的最有效的解决方案是：

 private Queue reverse(Queue queue) { List collect = queue.stream() .collect(Collectors.toList()); Collections.reverse(collect); return new LinkedList<>(collect); }