java - 反转方法反转队列的元素

Question

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

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

签名：

public Queue<T> reverse(Queue<T> myQueue) {

注意：不知道队列是使用节点还是数组。

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

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

Answer 1

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

这是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 2

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

Answer 3

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

public static <T> Queue<T> flip(Queue<T> q) {
    Queue<T> ret = new Queue<>();
    recursiveFlip(q, ret);
    return ret;
}

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

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

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

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

Answer 4

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

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

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