Fastest Way To Implement A Queue in Java

Question

I wanted to know what changes should I be making to this code to reduce its execution time.

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;
    }   
}

Also I wanted to know is whether for implementing queues, LinkedList is faster or ArrayList or any other data structure.

Where do you need the improvement? Adding or peaking? If peaking then why not try a treeset? Or do you allow duplication? Some more info please — RNJ, Aug 27 '12 at 14:14
Sorting the collection every time you need the max, median, or min is certainly very inefficient. — assylias, Aug 27 '12 at 14:15
The last question is by the way a very typical homework question. Sure that this isn't homework? You might want to rephrase the question as such, so that you get better answers. — BalusC, Aug 27 '12 at 14:16
The change that will bring you the biggest speed improvement will be to format it... — brimborium, Aug 27 '12 at 14:17
@BalusC I think it's not homework but exam preparation as there are classnames like `ExamPeekableQueue` — brimborium, Aug 27 '12 at 14:19
@brimborium: how is an exam different from homework/schoolwork? — BalusC, Aug 27 '12 at 14:21
“We follow two rules in the matter of optimization: (1) Don’t do it. (2) (for experts only) Don’t do it yet.” - That is, not until you have a perfectly clear and unoptimized solution – M. A. Jackson — davidmontoyago, Aug 27 '12 at 14:21
@BalusC It's not exam, but exam preparation (I doubt he has internet connection during the exam). And as such I think we can treat the question normally, because this task will not directly influence his grade/whatever, but only indirectly (by him learning something). For homework we would not supply code or give too much specifics to not break the learning concept of the teachers. — brimborium, Aug 27 '12 at 14:25
Wouldnt sorting the queue each time , just ruin the point of it being a queue in the first place?? also why the size method always return zero ?and the other methods return null? — Sednus, Aug 27 '12 at 14:26
Also note that, as it is, your code for `dequeue` is random, if you call one of your `peekMax/Min/Median` first, the list will be sorted and the result of `dequeue` will possibly change. — assylias, Aug 27 '12 at 14:27
@Sednus Because task 1b) will be *"Implement the size() method"* ;) — brimborium, Aug 27 '12 at 14:28
checking if its empty before adding it its unnecessary overhead — Sednus, Aug 27 '12 at 14:30
@brimborium the reason one might tag a "school related" question as homework is to indicate to people that you are looking to learn, not just implement. If we assumed this was NOT a homework assignment, I would just say "Use a LinkedList or any other implementation of java.util.Queue" — pap, Aug 27 '12 at 14:51

Oleksi · Answer 1 · 2012-08-27T14:31:05.993

This is a loaded question.

What operation do you want to speed up? Right now, your peekMin/Max/Mid code is quite slow because you have to sort each time. However, your insert code is fast. If you want, you can maintain a sorted data structure internally. This would slow down your insert method, but speed up your peek methods. There is often a tradeoff of speed between operations like this. It's rare to be able to just speed up ALL the operations on some data structure, so you need to pick what operations you think are common, and optimize those.

It's about what operations you want to speed up.

brimborium · Accepted Answer · 2012-08-27T14:30:56.187

Currently you have O(1) for insertion and O(nlogn) for getMin/getMax/getMedian. You can move the logn from the getters to the insertion part by using a sorted data structure. Or you can leave the insertion as it is and optimize getMin/getMax by doing a linear search through the list and just storing the minimal value. For getMedian there is nothing to do as you need a sorted set for that.

A further optimization would be to store the min/max and update the two values during each insertion step. This will not have any (non-constant) change on insertion and will reduce your getMin/getMax to O(1). (thanks to Tedil)

The same applies for getMedian, where you would keep a sorted list in parallel to your linked list. You can then simply pick the median out of the middle of that list. Of course this will change insertion time to O(logn) or worse (depending on the list you use) and will also double the amount of storage space. So it is a more expensive optimization than the one for getMin/getMax.

score 0 · Answer 3 · edited May 23 '17 at 12:20

0

To answer your latter question. please take a look at this topic to learn about the differences between using arrays or linked list in structures.

Also, as an advice, when declaring structures, always use the interface as the type so that you can change the implementation without affecting the functionality.

edited May 23 '17 at 12:20

Community

1
1

answered Aug 27 '12 at 14:18

Sednus

2,095
1
18
35

score 0 · Answer 4 · answered Aug 27 '12 at 14:36

It depends.

Actually, one thing most people answering/commenting don't realize is that Collections.sort gives about N performance on a nearly sorted list. (N log N is the performance if the list is not at all sorted.)

As others, have said, maybe you should be sorting when you change the list rather than read the list. Maybe you should be using an Ordered Set rather than list. (If you really need a list to hold multiple copies of an item, consider using a Ordered Map and making the number of occurrences the value.)

You can also consider making a an object that stores the Collection and keeps track of the min and max without sorting it. This would work well if finding medians is rare or if you can get away from needing the median.

score 0 · Answer 5 · answered Apr 04 '13 at 15:12

0

In the peekMaximum() and peekMinimum() methods, instead of sorting the LinkedList you can directly use the methods Collections.max(li) and Collections.min(li).

I think that will save the time wasted to sort the list.

answered Apr 04 '13 at 15:12

Nirmalya

195
4
16

Fastest Way To Implement A Queue in Java

5 Answers5