java - 如何在Java中查找队列中元素的最后一次出现

Question

我试图在一个字符串中查找特定字符串的最后一次出现队列。我正在使用另一个队列和变量。不过我被困在这里，我应该使用堆栈还是队列来解决这个问题以及如何解决。任何帮助将不胜感激。

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;

public class StackQueue{
public static void remove(Queue<String> queue, String toRemove){
    if(queue.isEmpty()){throw new NullPointerException();}

    Queue<String> tmp = new LinkedList<>();
    Queue<String> tmp1 = new LinkedList<>();
    int count = 0;

    while(! queue.isEmpty()){
        String removed = queue.remove();        
        if(toRemove == removed){
            tmp.add(removed);
            count++;
        }
        else{
            tmp1.add(removed);
        }       
    }

    while (!tmp1.isEmpty()){
        queue.add(tmp1.remove());
    }
}
public static void main(String[] args){
    Queue<String> q = new LinkedList<>();
    q.add("a");
    q.add("e");
    q.add("b");
    q.add("a");     
    q.add("e");


    System.out.println(q);
    remove(q, "a");     
    System.out.println(q);
}
 }

Answer 1

Queue 不适合您的使用，事实上您的类 StackQueue 的名称暗示您可能需要一个 Deque(尽管这可能是巧合)。

Deque(双端队列)接口(interface)指定了您需要的确切方法，removeLastOccurrence(Object o)。本质上，Deque 允许您从两端添加删除操作，这也有助于 Stack 行为，因此如果更加灵活，您可以从两端进行删除操作。

A Queue 相比之下只提供从队列前面移除或通过搜索在 Queue 中找到的第一个匹配项(尽管这可能取决于实现，因为 remove(Object o) Collection 接口(interface)中指定的方法没有声明它必须是第一次出现...)

对于您的用例，Queue 的问题是该接口(interface)旨在仅允许类似队列的行为，防止在不强制转换的情况下使用底层实现，这将允许执行更多此类任务很容易(例如 LinkedList 或 ArrayDeque)。类型转换远非理想，如果实际实现发生变化怎么办？

如果您坚持使用Queue，那么另一种不需要创建另一个Queue 的解决方案是使用队列的Iterator 和迭代器.remove()。例如:

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {

    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.add("a");
        queue.add("b");
        queue.add("c");
        queue.add("a");
        queue.add("d");
        queue.add("a");
        queue.add("b");
        System.out.println("Before: " + queue);
        remove(queue, "a");
        System.out.println("After: " + queue);
    }

    public static void remove(Queue<String> queue, String toRemove){
        int indexToRemove = findLastIndex(queue, toRemove);
        removeIndex(queue, indexToRemove);
    }

    private static int findLastIndex(Queue<String> queue, String value) {
        int indexToRemove = -1;
        int index = 0;
        for (Iterator<String> iterator = queue.iterator(); iterator.hasNext(); index++) {
            String current = iterator.next();
            if (value.equals(current)) {
                indexToRemove = index;
            }
        }
        return indexToRemove;
    }

    private static void removeIndex(Queue<String> queue, int indexToRemove) {
        int index = 0;
        for (Iterator<String> iterator = queue.iterator(); iterator.hasNext() && index <= indexToRemove; index++) {
            iterator.next();
            if (index == indexToRemove) {
                iterator.remove();
            }
        }
    }
}