Lesson 4

Exploring Queues: From Concept to Java Implementation

Introduction to Queues

Hello there! Today, we will unveil Queues in coding, likening them to a line in a coffee shop or a queue of print requests. Queues in computer science are First-In, First-Out (FIFO) structures. Consider this example: you're at a theme park — the first person in line for the roller coaster gets on first. Today's lesson revolves around this straightforward yet powerful concept. So, let's dive in!

Implementing a Queue in Java

Let's explore the implementation of Queues in Java. An array is ideal for implementing a Queue. Let's define the Queue:

Java
1public class Queue { 2 int front, rear, size, capacity; 3 int array[]; 4 public Queue(int capacity) { 5 this.capacity = capacity; // Set the max size 6 front = size = 0; // Initialize front and size 7 rear = capacity - 1; // Initialize rear 8 array = new int[this.capacity]; 9 } 10 11 // Will return true if the Queue is full 12 boolean isFull(Queue queue) { 13 return (queue.size == queue.capacity); 14 } 15}

In the Queue class above, the isFull() method checks if our queue is already at maximum capacity.

Queue Enqueue Operation

Enqueue, a fancy term, denotes adding an item to the queue — the item lines up at the rear. Here's how it plays out in our Queue class:

Java
1void enqueue(int item) { 2 if (isFull(this)) // Check if the queue is full 3 return; 4 this.array[this.rear] = item; // Add item at rear position 5 this.rear = (this.rear + 1) % this.capacity; // Move rear 6 this.size = this.size + 1; // increment size 7}

The enqueue() method checks if our queue has enough space before adding the item.

Queue Dequeue Operation

Just as enqueue adds an element to our queue, dequeue removes it. It extracts the element at the queue's front, reducing its size. However, we encounter an underflow condition if there are no elements to remove.

Java
1int dequeue() { 2 if (isEmpty(this)) // Check if the queue is empty 3 return Integer.MIN_VALUE; 4 5 int item = this.array[this.front]; // Item at front 6 this.front = (this.front + 1) % this.capacity; // Move front 7 this.size = this.size - 1; // decrement size 8 return item; // return removed item 9}

The dequeue() method checks for emptiness before dispatching the item.

Complexity Analysis of Queue Operations

The time complexity of enqueue and dequeue operations remains constant: O(1). However, the space complexity varies with the size of the queue, making it O(n).

Using Java's Queue Interface

While it is essential to understand the queue's inner structure, we won't implement it ourselves. Instead, we will use the Java's built-in queue. Think of any system that needs to handle requests in a fair, first-come-first-served order. These are all excellent candidates for using a queue. Here's how you can declare, initialize, and utilize a Queue using Java's built-in Queue interface:

Java
1// Import the necessary package 2import java.util.Queue; 3import java.util.LinkedList; 4 5public class Main { 6 public static void main(String[] args) { 7 // Create and initialize a Queue using a LinkedList 8 Queue<Integer> queue = new LinkedList<>(); 9 10 // Add elements {0, 1, 2, 3, 4} to queue 11 for (int i=0; i<5; i++) 12 queue.add(i); 13 14 // Display contents of the queue. 15 System.out.println("Elements of queue-"+queue); 16 17 // To remove the head of queue. 18 int removedele = queue.remove(); 19 System.out.println("removed element-" + removedele); 20 21 System.out.println(queue); 22 23 // To view the head of queue 24 int head = queue.peek(); 25 System.out.println("head of queue-" + head); 26 27 // Rest all methods of collection interface 28 int size = queue.size(); 29 System.out.println("Size of queue-" + size); 30 } 31}

In the above example, we create an instance of Queue using LinkedList. What follows includes key Queue operations:

  • add(): Inserts the specified element into the Queue.
  • remove(): Removes and returns the head of the Queue.
  • peek(): Retrieves, but does not remove, the head of the Queue, returning null if the queue is empty.
  • size(): Returns the number of elements in the Queue.

Java's queue interface is versatile and can accommodate diverse data types.

In Summary: Queues

We've learned about the Queue, its operations, and its implementation in Java. Furthermore, these techniques are fundamental for smooth functioning in daily life. They are invaluable and versatile in various applications, from data buffering in hardware to process scheduling in operating systems.

With your newfound knowledge of the Queue data structure, it's time to level up! Coming next are some practice problems to enhance your understanding of these concepts. Let's dive in!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.