A queue in Java (and in many other programming languages) is a collection or list that organizes elements in a sequence. The elements are distinct by their characteristics of FIFO, which stands for First-In-First-Out: the element that gets added first also gets removed first.
In simpler terms, think of a real-life queue like people standing in line for buying tickets - the person who comes first, gets served first.
Java provides a Queue interface which is part of Java’s collections framework. It supports different types of methods including insertion, removal and inspection methods:
Insertion Methods: These methods add an element to the end of the queue.
- add(e): This method throws an exception if it fails to insert the element.
- offer(e): This method returns false if it fails to insert the element.
Removal Methods: These remove an element from the front/head of the queue.
- remove(): When the queue is empty, this method throws an exception.
- poll(): If there’s no element when trying to poll(), it will not throw any exception but return
Time Complexities
The time complexity for different operations on a queue data structure are as follows:
Insertion (enqueue): This operation puts an element at the end of the queue. The time complexity is O(1), because this operation always takes the same amount of time, regardless of the size of the queue.
Removal (dequeue): This removes an element from the front/head of the queue. The time complexity is also O(1), since this operation too does not depend on the size of the queue.
Peek/Front: This returns the element at the front/head of the queue without removing it. The time complexity for this operation is again O(1) because you are only accessing and returning a single element.
IsEmpty/IsFull: Checking if a queue is empty or full has a constant time complexity, O(1).
In short, all primary operations on a Queue data structure – insertion, removal, and peeking – occur in constant time i.e., their performance is quick and independent from size of the Queue.
Examples
Java:
1import java.util.LinkedList;
2import java.util.Queue;
3
4public class Main {
5 public static void main(String[] args) {
6
7 Queue<Integer> queue = new LinkedList<>();
8
9 // Adds elements {0, 1, 2, 3, 4} to the queue
10 for (int i=0; i<5; i++)
11 queue.add(i);
12
13 // Display contents of the queue.
14 System.out.println("Elements of queue: "+queue);
15
16 // To remove the head of the queue.
17 int removedElement = queue.remove();
18 System.out.println("Removed element: " + removedElement);
19
20 // To view the head of queue
21 int head = queue.peek();
22 System.out.println("head of queue: " + head);
23
24 // Rest all methods of collection interface like size and contains can be used with this implementation.
25 int size = queue.size();
26 System.out.println("Size of queue: " + size);
27 }
28}
Python:
1from collections import deque
2
3#initialize a queue by creating instance from deque class from collections module.
4queue = deque()
5
6#enqueue elements at end of queue
7for i in range(5):
8 queue.append(i)
9
10#prints “deque([0, 1, 2, 3, 4])”
11print('Initial deque:',queue)
12
13#dequeue elements from front of dequeue
14removed_element = queue.popleft()
15print('Dequeued element:', removed_element)
16
17#accessing first element (this does not dequeue)
18first_elem = queue[0]
19print('First element:', first_elem)
20
21#getting length
22size_of_queue=len(queue)
23print('Size of dequeue:',size_of_queue)
Practical Use Cases
Telecommunications: In telecommunication networks, queues are used to control packets of information and manage bandwidth. This helps prioritize data transfer requests and organize them efficiently.
Computer Systems: Most computer systems use queues as part of their job scheduling function, ensuring tasks are carried out in the correct order.
Customer Service: Queues can simulate real-world waiting lines as seen in customer service scenarios such as ticket booking systems or call handling.
Print Jobs: Print jobs typically use queue data structures where the first request is the first one to be executed (First-In-First-Out mechanism).
E-commerce Websites: High-demand services like ticketing websites use queues to handle user requests during peak times, ensuring fairness access and system stability.
Data Streaming Services: Data streaming architectures use queues for managing real-time data processing - these streams might involve continuous aggregations, filtering, and categorizing of incoming live data which is then queued up accordingly for onward consumption by event-processing applications.
Operating Systems: In multi-tasking environments, various processes have to wait for CPU time slice or I/O operations – such process control management uses Queue like structure called “Process Control Blocks” for task scheduling.
Priority Queue
A priority queue is a special type of queue in which elements are queued based on their priority. Unlike the common queue data structure where an element is dequeued in FIFO order, the one with highest priority will be dequeued from a priority queue before the one with lower priority. If two elements have the same priority, they are served according to their ordering in the queue.
In some applications, certain tasks need to be prioritized over others, hence they need to be performed first - this is where a Priority Queue comes into play.
Here’s how you can use it:
In Java:
1import java.util.*;
2
3class Example {
4 public static void main(String args[]) {
5 PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();
6
7 // Adding items to the pQueue using add()
8 pQueue.add(10);
9 pQueue.add(20);
10 pQueue.add(15);
11
12 // Printing the top element of PriorityQueue
13 System.out.println(pQueue.peek());
14
15 // Removing the top priority element (or head) and printing
16 System.out.println(pQueue.poll());
17
18 // Printing all elements
19 Iterator itr = pQueue.iterator();
20 while(itr.hasNext())
21 System.out.println(itr.next());
22 }
23}
In Python:
1import heapq
2
3# Creating empty priority queue
4priority_queue = []
5
6# Adding elements to the queue
7heapq.heappush(priority_queue, 10)
8heapq.heappush(priority_queue, 30)
9heapq.heappush(priority_queue, 20)
10
11# Removing element from the queue
12print(heapq.heappop(priority_queue)) # prints 10
13
14# printing remaining elements
15for i in range(len(priority_queue)):
16 print(heapq.heappop(priority_queue), end=", ") # prints 20, 30,
Again, do keep in mind that high and low priorities can be subjective to implementation. In above examples lowest value had the highest priority.
Advantages
Priority queues have several advantages:
- Versatility: Priority queues are versatile and can be used to model a wide variety of scenarios.
- Efficiency: They are efficient for high priority items since these items take precedence over lower priority items.
- Responsiveness: By prioritizing tasks, a system can better manage its resources, resulting in more responsive performance.
Use cases for Priority Queues
- Job scheduling on computers: One of the most common uses of Priority Queue is in the operating system where it is used to schedule jobs based on their priority.
- Traffic shaping/ Packet routing in Networks: In networking, packets are assigned a priority and then they are transmitted based on the priority using the priority queues concept.
- Medical Systems - Especially in emergency healthcare situations, patients must be treated based on the severity of their condition rather than the order they arrive in. Thus, doctors use a form of a priority queue when triaging patients for treatment.
- Event-driven simulations: Sometimes events must be processed based on their time of occurrence which means a high-priority task usually means one that should be done soonest (like queuing up animations or AI scripts).
- Huffman coding, used for lossless data compression is implemented using priority queue data structure.
Comments