“This is the 28th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
Java queue
A queue is a queue at both ends of a collection of objects on which operations can only be performed.
Queues have two ends, called heads and tails.
In a simple queue, objects are added to the tail and removed from the head, removing the first added object first.
The Java Collections Framework supports the following types of queues.
• Simple queues allow insertion at the tail and removal from the head.
• Priority queues assign priority to each element and allow the element with the highest priority to be removed from the queue.
• Delay queues add delay to each element and delete the element only when its delay has passed.
• A double-ended queue allows its components to be inserted and removed from the head and tail.
• Blocking queues block threads, adding elements to them when they are full, and prevent them from removing elements from them when they are empty.
• Transport queues are blocking queues where object switching occurs between producer and consumer threads.
• A blocking dual-end queue is a combination of a dual-end queue and a blocking queue.
Introduction to queues
• Queues can be defined as ordered lists that allow insertion at one end, called REAR, and deletion at the other, called FRONT.
• Queues are called fifO lists.
• For example, queues of people waiting for railway tickets.
Application of queues
Since queues perform operations on a first-in, first-out basis, this is fairly fair for ordering operations. The various applications of queues are described below.
Queues are widely used as a wait list for a single shared resource (printer, disk, CPU).
• Queues are used for asynchronous data transfer (for example, data is not transferred at the same rate between two processes). Pipes, file IO, sockets.
• Queues are used as buffers in most applications such as MP3 media players, CD players, etc.
• Queues are used to maintain playlists in media players for adding and removing songs from playlists.
• Queues are used in the operating system to handle interrupts.
Temporal complexity
| Temporal complexity | access | search | insert | delete |
|---|---|---|---|---|
| On average | Theta (n) | Theta (n) | Theta (1) | Theta (1) |
| The worst | Theta (n) | Theta (n) | Theta (1) | Theta (1) |
Simple queue
Simple queues are represented by instances of the Queue interface.
Queues allow you to perform three basic operations:
• Add elements from the tail
• Remove the element from its header
• Review at the top of the element
The Queue interface defines two methods for each of the three operations. If the operation is not possible, one method throws an exception and the other method returns false or NULL to indicate failure.
| methods | describe |
|---|---|
| boolean add(E e) | If possible, add an element to the queue. Otherwise, it throws an exception. |
| boolean offer(E e) | If an element cannot be added, it is added to the queue without throwing an exception. It returns false on failure and true on success. |
| E remove() | Deletes the header of the queue. If the queue is empty, it throws an exception. This method returns the removed item. |
| E poll() | Removes an element from the queue. If the queue is empty instead of throwing an exception, null is returned. |
| Eelement() | Peek at the head of the queue without removing it from the queue. If the queue is empty, it throws an exception. |
| E peek() | View the queue and return NULL if the queue is empty instead of throwing an exception. |
LinkedList and PriorityQueue are the two implementation classes for the Queue interface. LinkedList also implements the List interface.
example
The following code shows how to use a linked list as a FIFO queue.
import java.util.LinkedList; import java.util.NoSuchElementException; import java.util.Queue; public class Main { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.add("Java"); // offer() will work the same as add() queue.offer("SQL"); queue.offer("CSS"); queue.offer("XML"); System.out.println("Queue: " + queue); // Let"s remove elements until the queue is empty while (queue.peek() ! = null) { System.out.println("Head Element: " + queue.peek()); queue.remove(); System.out.println("Removed one element from Queue"); System.out.println("Queue: " + queue); } System.out.println("queue.isEmpty(): " + queue.isEmpty()); System.out.println("queue.peek(): " + queue.peek()); System.out.println("queue.poll(): " + queue.poll()); try { String str = queue.element(); System.out.println("queue.element(): " + str); str = queue.remove(); System.out.println("queue.remove(): " + str); } catch (NoSuchElementException e) { System.out.println("queue.remove(): Queue is empty."); }}}Copy the codeThe code above produces the following results.
