java - 如何获取某个数字在队列中出现的次数(Java)？

Question

假设我们有一个 queue可以在其中存储任何整数。

我需要做的(为了测试)是编写一个函数，该函数将创建(并返回)一个新队列，而不更改原始队列。

您可以更改它，但在函数结束时它必须与开始时一样

我们假设 class Queue 中的唯一方法是:

• 插入/添加
• 删除
• 偷看
• isEmpty(如果队列为空则返回 True)

在新队列中，我们将包含每个整数以及它在第一个队列中出现的次数。

除了初始队列之外，我还可以使用:堆栈、数组、新队列以及可能的 LinkedList。

也可以编写新函数。

直接的解决方案(我猜)是用任何方法复制第一个队列，然后使用 while(!isEmpty) 和一个数字计数器，然后将其添加到所需的队列并从复制的队列中删除一个。

我目前没有写下来，但我真的想不出更干净、更有效的方法来做到这一点，所以任何帮助将不胜感激。谢谢。

Answer 1

您可能需要一段时间才能想出更好的解决方案，但这就是我所做的:

public static Queue<Integer> countQueue(Queue<Integer> q) {
    LinkedList<Integer> valuesList = new LinkedList<>();
    // since we can't iterate on the Queue
    // we remove the head element
    while(!q.isEmpty()) {
        int x = q.remove();
        valuesList.add(x);
    }

    LinkedList<Integer> nonRepeated = new LinkedList<>();
    LinkedList<Integer> timesCount = new LinkedList<>();

    while(!valuesList.isEmpty()) {
        int value = valuesList.remove();
        q.add(value); // get the original queue back
        int index = nonRepeated.indexOf(value);
        if (index == -1) {
            nonRepeated.add(value);
            timesCount.add(1);
        } else {
            timesCount.set(index, timesCount.get(index)+1);
        }
    }
    Queue<Integer> output = new ArrayDeque<>();
    while(!nonRepeated.isEmpty()) {
        output.add(nonRepeated.remove());
        output.add(timesCount.remove());
    }

    return output;
}

如果您有兴趣创建一个方法来获取队列的大小，这可能是最简单的解决方案之一:

public static int getQueueSize(Queue<Integer> q) {
    int i=0;
    Queue<Integer> backupQueue = new ArrayDeque<>(); 
    while(!q.isEmpty()) {
        i++;
        backupQueue.add(q.remove());
    }
    while(!backupQueue.isEmpty())
        q.add(backupQueue.remove());
    return i;
}

每当使用队列、堆栈等时，您都需要注意数据结构的范例，例如 FIFO(先进先出)和 LIFO(后进先出)，这将决定您应该如何迭代结构上。