java - 在 Java 中实现队列的最快方法

我想知道我应该对此代码进行哪些更改以减少其执行时间。

import java.util.*;

public class ExamPeekableQueueImpl <E extends Comparable<E>> implements ExamPeekableQueue<E> {

    LinkedList<E> li = new LinkedList<E>();

    public ExamPeekableQueueImpl(){
    }

    public void enqueue(E e){
        if(li.isEmpty()){
            li.add(0, e);
        }
        else
        li.add(e);
    }

    public E dequeue(){
        li.pollFirst();
        return null;
    }

    public void printlist(){
        System.out.println(li.toString());
    }

    public E peekMedian(){
        int var = (((li.size())/2)+1);
        Collections.sort(li);
        //Integer var2 = li.get(var);
        System.out.println("the median is:" + li.get(var-1));
        return null;
    }

    public E peekMaximum(){
        Collections.sort(li);
        System.out.println("the maximum is:" + li.getLast());
        return null;
    }

    public E peekMinimum(){
        Collections.sort(li);
        System.out.println("the minimum is:" + li.getFirst());
        return null;
    }

    public int size(){
        li.size();
        return 0;
    }
}

另外我想知道是为了实现 queues ， LinkedList 更快还是 ArrayList 或任何其他数据结构。

最佳答案

目前你有 O(1) 插入和 O(nlogn) getMin/getMax/getMedian 。您可以使用已排序的数据结构将 logn 从 getter 移动到插入部分。或者，您可以保持插入不变，并通过对列表进行线性搜索并仅存储最小值来优化 getMin/getMax。对于 getMedian 没有什么可做的，因为 需要 一个排序集。

进一步的优化是在每个插入步骤期间存储最小值/最大值并更新两个值。这在插入时不会有任何(非常量)变化，并将您的 getMin/getMax 减少到 O(1)。 (感谢 Tedil )

这同样适用于 getMedian ，您可以将排序列表与链接列表并行保存。然后，您可以简单地从该列表的中间挑选中位数。当然，这会将插入时间更改为 O(logn) 或更糟(取决于您使用的列表)，并且还会使存储空间量增加一倍。所以它是一种比 getMin/getMax 更昂贵的优化。

关于java - 在 Java 中实现队列的最快方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12143685/