A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added to the queue is the first to be removed. Think of a queue in real life – like people waiting in line at a ticket counter, where the person who arrives first gets served first.
Types of Queue
Queues have different variants based on specific requirements:
- Simple Queue: A basic queue where elements are added at the rear and removed from the front.
- Circular Queue: A queue where the last element points back to the first element to make better use of space.
- Priority Queue: A queue where elements are removed based on priority rather than the order they were added.
- Deque (Double-Ended Queue): A queue that allows insertion and deletion of elements from both ends.
Declaration & Initialization
In Java, you can declare and initialize a queue using the Queue interface and a class like LinkedList or PriorityQueue:
|
1 2 3 4 5 |
// Using LinkedList Queue<Integer> queue = new LinkedList<>(); // Using PriorityQueue Queue<Integer> priorityQueue = new PriorityQueue<>(); |
Basic Operations
- Enqueue: The operation of adding an element to the queue is called enqueue.
- Dequeue: The operation of removing an element from the front of the queue is called dequeue.
- Front: The element at the front of the queue is the first element that will be dequeued.
- Rear: The element at the end of the queue is the last element to be enqueued.
- Peek: The operation that allows you to view the element at the front of the queue without removing it.
Insertion (Enqueue): Add an element at the rear of the queue.
|
1 |
queue.add(10); // Adds 10 to the queue |
Deletion (Dequeue): Remove an element from the front of the queue.
|
1 |
int value = queue.poll(); // Removes and returns the front element |
Traversal: Iterate through the queue to view its elements.
|
1 2 3 |
for (int element : queue) { System.out.println(element); } |
Queue Implementation Using Array
We can implement a simple queue using arrays or linked lists. Let’s look at a basic implementation using an array
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
class Queue { private int[] queue; private int front; private int rear; private int capacity; public Queue(int size) { capacity = size; queue = new int[capacity]; front = 0; rear = -1; } // Add element to the queue public void enqueue(int item) { if (rear == capacity - 1) { System.out.println("Queue is full!"); } else { queue[++rear] = item; System.out.println(item + " enqueued to queue."); } } // Remove element from the queue public void dequeue() { if (front > rear) { System.out.println("Queue is empty!"); } else { System.out.println(queue[front++] + " dequeued from queue."); } } // View the element at the front of the queue public void peek() { if (front <= rear) { System.out.println("Front element is: " + queue[front]); } else { System.out.println("Queue is empty!"); } } } |
Queue Implementation Using the LinkedList
Queues can be implemented in Java using a variety of methods, but the most common way is through the Queue interface or the LinkedList class. Here’s a simple example using LinkedList:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.LinkedList; import java.util.Queue; public class QueueExample { public static void main(String[] args) { // Create a queue using LinkedList Queue<Integer> queue = new LinkedList<>(); // Enqueue elements queue.add(10); queue.add(20); queue.add(30); // Dequeue elements System.out.println("Dequeued: " + queue.poll()); // 10 // Peek at the front element System.out.println("Front element: " + queue.peek()); // 20 // Check if the queue is empty System.out.println("Is queue empty? " + queue.isEmpty()); // false } } |
Advantages & Disadvantages
| Advantages | Disadvantages |
|---|---|
| Simple and easy to implement | Not suitable for random access |
| Ideal for real-time processing | Fixed size in simple queue |
| Efficient for tasks with FIFO order | Overhead in certain implementations (like priority queues) |
Real-World Examples
- Printer Queue: In offices, print jobs are queued up and processed in the order they were received.
- Call Center Systems: Incoming calls are placed in a queue and answered in the order they arrive.
- Task Scheduling: Operating systems often use queues to manage tasks that need to be executed in the order they arrive.
