Welcome to our exploration of queues and deques. These structures frequently surface in everyday programming, managing everything from system processes to printer queues. In this lesson, our goal is to understand and implement queues and deques in Java. Let's dive in!

A queue, similar to waiting in line at a store, operates on the "First In, First Out" or FIFO principle. Java's LinkedList class enables the implementation of queues. This class includes methods such as add() for adding items and poll() for removing items.

Java
Copy to clipboard
1import java.util.LinkedList;
2import java.util.Queue;
3
4// Create a queue and add items
5Queue<String> q = new LinkedList<>();
6q.add("Apple");
7q.add("Banana");
8q.add("Cherry");
9
10// Remove an item
11System.out.println(q.poll());  // Expects "Apple"

The dequeued item, "Apple", was the first item we inserted, demonstrating the FIFO principle of queues.

Before trying to remove items from our queue, let's ensure it is not empty. This precaution will prevent runtime errors when attempting to dequeue from an empty queue.

Java
Copy to clipboard
1import java.util.LinkedList;
2import java.util.Queue;
3
4// Create a queue and enqueue items
5Queue<String> q = new LinkedList<>();
6q.add("Item 1");
7q.add("Item 2");
8
9// Check if the queue is non-empty, then dequeue an item
10if (!q.isEmpty()) {
11    System.out.println(q.poll());  // Expects "Item 1"
12}

A deque, or "double-ended queue," allows the addition and removal of items from both ends. Java provides the ArrayDeque class for implementing deques. We can add items to both ends of our deque using the addLast(item) method for the right end and the addFirst(item) method for the left. Similarly, we can remove elements from left and right ends using removeFirst and removeLast.

Java
Copy to clipboard
1import java.util.ArrayDeque;
2import java.util.Deque;
3
4// Create a deque and add items
5Deque<String> d = new ArrayDeque<>();
6d.addLast("Middle");
7d.addLast("Right end");
8d.addFirst("Left end");
9
10// Remove an item
11System.out.println(d.removeLast());  // Expects "Right end"
12
13// Remove an item from the left
14System.out.println(d.removeFirst()); // Expects "Left end"

The ArrayDeque class offers substantial functionality, though it does not have a built-in rotation method. We can implement rotation manually using a loop.

Java
Copy to clipboard
1import java.util.ArrayDeque;
2import java.util.Deque;
3
4// Create a deque
5Deque<String> d = new ArrayDeque<>();
6d.addLast("Apple");
7d.addLast("Banana");
8d.addLast("Cherry");
9
10// Rotate the deque to the right by 1 place
11for (int i = 0; i < 1; i++) {
12    d.addFirst(d.removeLast());
13}
14
15System.out.println(d);  // Expects [Cherry, Apple, Banana]

Here, the manual rotation loop shifts all items to the right by one position.

Congratulations on finishing this detailed study of queues and deques in Java! You've learned their operating principles and how to construct and manipulate them in Java.

Prospectively, we aim to comprehend additional data structures like these. This quest opens up a world of opportunities for expressing your ideas and solving complex problems. Are you ready for forthcoming practice exercises to consolidate this new knowledge? Let's continue our exploration!