×
☰ See All Chapters

Java Queue

  • Queue & PriorityQueue were added in java 5 version. 

  • It stores the values in a heap (A heap is a new data structure and uses binary tree). 

  • It allows only comparable objects. 

  • The elements should be always accessed by using poll() method while iterating otherwise the values will be accessed in an undefined order. 

java-queue-0
 

PriorityQueue

  • PriorityQueue stores values in an undefined order, but when the elements are pulled from the queue it orders the values from the queue in a sorted order. Default is natural order or ascending order but if a custom comparator is used the values can be ordered in descending order. 

  • PriorityQueue is not synchronized. If a thread safe priority queue is required use class PriorityBlockingQueue. 

  • A basic queue always orders the values in the First In First Out order (FIFO). A priority queue orders values based on  priority. 

  • PriorityQueue doesn’t allow null. 

  • PriorityQueue allows duplicate values, but doesn’t allow dissimilar objects. 

  • The PriorityQueue by default gives highest priority to minimum value / ascending order / natural order in the queue for giving a value. The highest priority can be changed to maximum value / descending order by using a custom  comparator. In a priority queue, an element with high priority is served before an element with low priority. If two have the same priority, they are served according to their order in the queue. 

import java.util.PriorityQueue;

 

public class PriorityQueueDemo {

        public static void main(String[] args) {

                PriorityQueue pq1 = new PriorityQueue();

                PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>();

                // add values

                pq1.add(1);

                pq1.add(5);

                pq1.add(3);

                pq1.offer(4);

                pq1.offer(6);

                pq1.offer(2);

                System.out.println("All values: " + pq1);

                pq2.addAll(pq1);

 

                // peek will return the value from the head of the queue but does not remove the

                // element

                Object o1 = pq1.peek();

                System.out.println("Head of queue: " + o1);

                System.out.println("Size after after peek: " + pq1.size());

                System.out.println("All values after peek: " + pq1);

 

                int i = pq2.peek();

                System.out.println("Head of queue: " + i);

                System.out.println("Size after after peek: " + pq2.size());

                System.out.println("All values after peek: " + pq2);

 

                // poll will return the value from the head of the queue and will remove the

                // element

                int x = pq2.poll();

                System.out.println("Head of queue: " + x);

                System.out.println("Size after after poll: " + pq2.size());

                System.out.println("All values after poll: " + pq2);

                // element() returns the element at the head of the queue. The element is not

                // removed.

                Object o2 = pq1.element();

                System.out.println(o2);

                System.out.println("Size after after element: " + pq2.size());

                // remove() removes the element at the head of the queue, returning the element

                // in the process.

                Object o3 = pq1.remove();

                System.out.println(o3);

                System.out.println("Size after after remove: " + pq2.size());

        }

}

Class PriorityQueue and interface Queue allows only comparable objects

import java.util.PriorityQueue;

 

class Hello {

}

 

public class PriorityQueueDemo2 {

        public static void main(String[] args) {

                PriorityQueue pq = new PriorityQueue();

                // This is Ok

                pq.add(new Hello());

                // pq.add(new Hello());Adding more than one gives error

                System.out.println(pq);

        }

}

 

java-queue-1
 

Deque interface

  • Deque interface and ArrayDeque class were added in java 6. 

  • Deque interface supports double ended queue. 

  • Deque also supports basic queue (FIFO) and stack (LIFO). Deque interface has push() & pop() to support stack. It is more recommended to use ArrayDeque as stack rather the legacy Stack class. 

ArrayDeque class

  • ArrayDeque class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. 

  • ArrayDeque is using array structure. 

  • ArrayDeque allows dissimilar values. 

  • ArrayDeque does not allow null values. 

  • ArrayDeque is not synchronized. 

java-queue-2
 

ArrayDeque Example

import java.util.ArrayDeque;

 

public class ArrayDequeDemo {

        public static void main(String[] args) {

                ArrayDeque adq1 = new ArrayDeque();

                ArrayDeque<Integer> adq2 = new ArrayDeque();

 

                // add values

                adq1.add(1);

                adq1.add(5);

                adq1.add(3);

                adq1.add(4);

                adq1.add(6);

                adq1.add(2);

                System.out.println(adq1);

                // use offerFirst(), peekFirst(), pollFirst() methods to work with front end of

                // queue add values to front end of the queue

                adq2.offerFirst(10);

                adq2.offerFirst(20);

                adq2.offerFirst(30);

                adq2.offerFirst(40);

                adq2.offerFirst(50);

                System.out.println("All values: " + adq2);

 

                // get head from front end of the queue but does not remove

                int x = adq2.peekFirst();

                System.out.println("Head of queue from front end: " + x);

 

                // remove head from front end of the queue

                int a = adq2.pollFirst();

                System.out.println("Head of queue from front end: " + a);

 

                // remove head from front end of the queue

                a = adq2.pollFirst();

                System.out.println("Head of queue from front end: " + a);

 

                System.out.println("All values after poll: " + adq2);

                // use offerLast(), peekLast(), pollLast() methods to work with tail end of

                // queue

                // add values to rear end of the queue

                adq2.offerLast(11);

                adq2.offerLast(22);

                adq2.offerLast(33);

                adq2.offerLast(44);

 

                System.out.println("All values: " + adq2);

 

                // get head from rear end of the queue

                int y = adq2.peekLast();

                System.out.println("Head of queue from rear end: " + y);

 

                // remove head from rear end of the queue

                a = adq2.pollLast();

                System.out.println("Head of queue from rear end: " + a);

 

                // remove head from rear end of the queue

                a = adq2.pollLast();

                System.out.println("Head of queue from rear end: " + a);

 

                System.out.println("All values after poll: " + adq2);

        }

}

Output:

[1, 5, 3, 4, 6, 2]

All values: [50, 40, 30, 20, 10]

Head of queue from front end: 50

Head of queue from front end: 50

Head of queue from front end: 40

All values after poll: [30, 20, 10]

All values: [30, 20, 10, 11, 22, 33, 44]

Head of queue from rear end: 44

Head of queue from rear end: 44

Head of queue from rear end: 33

All values after poll: [30, 20, 10, 11, 22]

 

ArrayDeque Example 2

import java.util.ArrayDeque;

import java.util.Deque;

 

public class ArrayDequeDemo2 {

        public static void main(String[] args) {

 

                // using ArrayDeque as stack (LIFO)

                Deque<String> adq = new ArrayDeque<String>();

                adq.push("A");

                adq.push("B");

                adq.push("D");

                adq.push("E");

                adq.push("F");

 

                System.out.print("Popping the stack: ");

 

                while (adq.peek() != null) {

                        String s = adq.pop();

                        System.out.print(s + " ");

                }

        }

}

Output:

Popping the stack: F E D B A

 

 

 

 

All Chapters
Author