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
– RNJ, Commented Aug 27, 2012 at 14:14
Sorting the collection every time you need the max, median, or min is certainly very inefficient. — assylias
– assylias, Commented Aug 27, 2012 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
– BalusC, Commented Aug 27, 2012 at 14:16
@brimborium: how is an exam different from homework/schoolwork? — BalusC
– BalusC, Commented Aug 27, 2012 at 14:21

Oleksi · Accepted Answer · 2012-08-27 14:31:05Z

3

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.

edited Aug 27, 2012 at 14:31

answered Aug 27, 2012 at 14:19

Oleksi

13.1k5 gold badges58 silver badges81 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

brimborium · Accepted Answer · 2012-08-27 14:30:56Z

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.

Community · Accepted Answer · 2017-05-23 12:20:10Z

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, 2017 at 12:20

CommunityBot

11 silver badge

answered Aug 27, 2012 at 14:18

Sednus

2,1331 gold badge18 silver badges36 bronze badges

Comments

Joe · Accepted Answer · 2012-08-27 14:36:21Z

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.

Nirmalya · Accepted Answer · 2013-04-04 15:12:37Z

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 4, 2013 at 15:12

Nirmalya

2055 silver badges17 bronze badges

Collectives™ on Stack Overflow

Fastest Way To Implement A Queue in Java

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related