CODEWITHSUNDEEP
javagenericsqueue
Michael André Slimz
Michael André Slimz

Reputation: 67

Get max element in a Queue | Java

Is there an alternative way to get the max element in a Queue (Java)? (Please provide alternative approaches ) 

import java.util.*;

public class MaxQueueElement<E extends Comparable<E>> {

    public MaxQueueElement(Queue<E> queue){
        E max= queue.peek();   // initialize max with head of queue

        for(E e : queue){
            if(e.compareTo(max) > 0){
                max = e;
            }
        }

    System.out.println(max);

 }
}

Upvotes: 1

Views: 12296

Answers (6)

Shivam
Shivam

Reputation: 89

The get-max operation on a queue can be implemented in amortized O(1) time by maintaining the candidates for the max value in a separate double-ended queue (Deque).

  • On enqueue (or offer) operation, we check whether there are any elements at the back of the Deque which are lesser in value than the element being enqueued. These values can simply be removed – for these can never be the maximum value going forward.
  • On dequeue (or poll) operation, we check whether the first element in the Deque is equal to the first element in the regular queue and if yes, remove it too.
  • The max element is simply the first element of the Deque.

All operations have amortized O(1) time complexity.

Here's an implementation in Java:

public class QueueWithMax<T extends Comparable<T>> {
    Queue<T> queue;
    Deque<T> cMax; // candidates for Max value

    public QueueWithMax() {
        queue = new LinkedList<>();
        cMax = new LinkedList<>();
    }

    public void offer(T element) {
        queue.offer(element);
        while (!cMax.isEmpty() && element.compareTo(cMax.peekLast()) > 0) {
            cMax.pollLast();
        }
        cMax.offerLast(element);
    }

    public T poll() {
        if (cMax.peekFirst().equals(queue.peek()))
            cMax.pollFirst();
        return queue.poll();
    }

    public T getMax() {
        return cMax.peekFirst();
    }
}

Upvotes: 4

Rohith V
Rohith V

Reputation: 1123

I think you can also make use of Collections.max(queue) in case of queue

Upvotes: 0

Meepo
Meepo

Reputation: 368

I'm taking a computer science class, and we aren't allowed to use the for each loop. I'm not sure if it's the same with you. Note that the for each loop kind of defeats the purpose of a Queue since you want to only be handling the front and end of a queue. In my class specifically, we also want to have the queue be at it's original state before it was passed into the method without using an extra auxiliary data structure. Here's how I would go about it on a test:

public E findMaxQueueElement(Queue<e> queue) { //my test would ask me to return the max value
    E max = queue.remove();
    queue.add(max); //add it back to the end
    for(int i=0; i<queue.size()-1; i++) {
        E current = queue.remove();
        if (current.compareTo(max) > 0) {
            max = current;
        }
        queue.add(current);
    }
    return max;
}

With the limitations I provided, this should work. I hope this helps.

Upvotes: 1

lexicore
lexicore

Reputation: 43671

Unless the queue is not some special sorted queue like PriorityQueue, from the algorithmic point of view there is no better way. Since the queue does not have any intrinsic sorting properties, you have to check all the elements of the queue before you find one.

The code is more or less OK. It will fail if the queue contains null. This is normally not the case, but may happen.
The MaxQueueElement construct is somewhat strange.

Upvotes: 0

Darshan Mehta
Darshan Mehta

Reputation: 30819

You can use Java 8's stream to sort the Queue, it internally uses the same algorithm but will result in less noisy code, e.g.:

public void MaxQueueElement(Queue<E> queue){
    Optional<E> max = queue.stream()
        .max(Comparable::compareTo);

    if(max.isPresent()){
        System.out.println(max.get());
    }
}

Another approach would be to use PriorityQueue with comparator and get the first element from it. e.g.:

public void MaxQueueElement2(Queue<E> queue){
    PriorityQueue<E> pQueue = new PriorityQueue<>((E e1, E e2)->e1.compareTo(e2));
    pQueue.addAll(queue);
    System.out.println(pQueue.peek());

}

Upvotes: 0

Andy Turner
Andy Turner

Reputation: 140318

The only way to access all elements in a Queue is to use the iterator() method - you can't (generally) access the elements by index (as in, some implementations might, but Queue doesn't inherently).

As such, all you can do is to iterate the elements one at a time, storing the current maximum element. This is exactly what you're doing here.

There is nothing wrong with your algorithm - but the way you've implemented it could be improved:

  • Don't do this in the constructor of a class - you don't need to construct a new instance of anything, as the maximum value already exists. Do it in a (static) method.
  • Don't print out the result - that's of no use to man or beast. Return it to the caller.
  • Handle the cases where the queue is empty and may contain nulls. (Look at the Javadoc of Collections.max for ideas)

Upvotes: 1

Related Questions