Deque Interface
- In Java, the Deque (short for Double-Ended Queue) interface represents a collection of components that can be added or removed from both ends—either the front or the back.
- It is a part of the java.util package and extends both the Queue and Deque interfaces.
- The Deque interface could be a basic information structure in Java since it permits for productive addition, removal, and review of components from both ends, giving the usefulness of both a stack and a queue.
- Let’s jump into the points of interest of the Deque interface, its methods, and its applications.
1. Core Features of Deque
- The elemental property of a Deque is that it awards the addition and removal of components from both ends, giving fundamental flexibility when compared to a standard Queue or Stack.
- In spite of the fact that a Queue habitually takes after the First-In-First-Out (FIFO) arrange, and a Stack takes after Last-In-First-Out (LIFO), the Deque can carry on as both, depending on how you utilize it.
For example:
- FIFO (Queue behavior): You’ll include components to the back utilizing offerLast() or addLast(), and remove them from the front utilizing pollFirst() or removeFirst().
- LIFO (Stack behavior): You’ll include components to the front utilizing offerFirst() or addFirst(), and remove them from the front utilizing pollFirst() or removeFirst() (acting like a stack).
2. Key Methods within the Deque Interface
The Deque interface gives a variety of methods for inserting, removing, and reviewing components from both ends. The key methods are:
Insertion Methods:
- addFirst(E e): Inserts the desired component at the front of the deque. Throws an exception in case the operation fails.
- addLast(E e): Inserts the required component at the end of the deque. Throws an exception if the operation fails.
- offerFirst(E e): Inserts the required component at the front of the deque. Returns false in case the operation fails.
- offerLast(E e): Inserts the required component at the end of the deque. Returns false in the event that the operation fails.
Removal Methods:
- removeFirst(): Removes and returns the first component of the deque. Throws an exception in case the deque is empty.
- removeLast(): Removes and returns the final component of the deque. Throws an exception in case the deque is empty.
- pollFirst(): Removes and returns the first component of the deque. Returns null in case the deque is empty.
- pollLast(): Removes and returns the final component of the deque. Returns null in case the deque is empty.
Accessor Methods:
- getFirst(): Retrieves, but does not remove, the first component of the deque. Throws an exception in case the deque is empty.
- getLast(): Retrieves, but does not remove, the final component of the deque. Throws an exception in case the deque is empty.
- peekFirst(): Retrieves, but does not remove, the first component of the deque. Returns null in case the deque is empty.
- peekLast(): Retrieves, but does not remove, the final component of the deque. Returns null in case the deque is empty.
Size and Checking Methods:
- isEmpty(): Returns true in case the deque contains no components, otherwise false.
- size(): Returns the number of components within the deque.
- clear(): Removes all components from the deque.
3.Deque Implementations
A few classes in Java execute the Deque interface, most strikingly:
- ArrayDeque: A resizable array usage of the Deque interface. It is faster than LinkedList when utilized for stack and queue operations but does not permit capacity to shrink.
- LinkedList: Actualizes both the List and Deque interfaces, giving a doubly linked list structure for more effective insertions and deletions from both ends compared to arrays.
Whereas ArrayDeque is for the most part preferred for execution reasons due to its lower overhead, LinkedList may be more reasonable after you require true bidirectional access or when you’re utilizing Deque as a List as well.
4. Applications of Deque
The Deque interface can be utilized in various scenarios where information should be accessed and controlled at both ends:
- Palindrome Checking: Since Deque permits you to effortlessly remove characters from both ends, it is an perfect structure for checking if a string may be a palindrome.
- Sliding Window Problem: In issues where you wish to track the least or most extreme in a sliding window of an array, Deque is frequently utilized to keep track of indices or components in an productive way.
- Task Scheduling: In a few planning algorithms, tasks may ought to be prioritized or dequeued from both ends, and Deque permits for adaptable planning.
5. Advantages of Using Deque
- Proficient Operations: Operations at both ends of the deque are by and large constant time O(1) (amortized for array-backed usage), making it exceedingly productive for stack and queue-like operations.
- Adaptability: The capacity to utilize the Deque as both a stack and a queue makes it flexible and versatile for different algorithmic tasks.
Example 1: Palindrome Checker Using Deque
In this example, we are going utilize a Deque to check in case a string may be a palindrome (a word that reads the same forwards and backwards). We’ll include characters to the deque from both ends and after that compare them.
import java.util.ArrayDeque;
import java.util.Deque;
public class PalindromeChecker {
public static boolean isPalindrome(String str) {
// Create a Deque to store characters
Deque<Character> deque = new ArrayDeque<>();
// Add all characters to the deque
for (char c : str.toCharArray()) {
deque.addLast(c); // Add to the back (end) of the deque
}
// Compare characters from both ends
while (deque.size() > 1) {
char front = deque.removeFirst(); // Remove from the front
char back = deque.removeLast(); // Remove from the back
if (front != back) {
return false; // If characters don’t match, it’s not a palindrome
}
}
return true; // All characters match, it’s a palindrome
}
public static void main(String[] args) {
System.out.println(isPalindrome(“madam”)); // true
System.out.println(isPalindrome(“hello”)); // false
}
}
Clarification:
- Add Characters: We include each character of the string to the Deque utilizing addLast(), which inserts characters at the end of the deque.
- Check Palindrome: We remove characters from both the front and the back utilizing removeFirst() and removeLast(), independently, and compare them. In case they don’t facilitate at any point, the string isn’t a palindrome.
Example 2: Using Deque as a Stack and Queue
In this example, we demonstrate how to utilize Deque as both a stack (LIFO) and a queue (FIFO).
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
// Using Deque as a Stack (LIFO)
deque.addFirst(10); // Push 10 to the front
deque.addFirst(20); // Push 20 to the front
deque.addFirst(30); // Push 30 to the front
System.out.println(“Using Deque as a Stack:”);
System.out.println(“Pop: ” + deque.removeFirst()); // Pop 30
System.out.println(“Pop: ” + deque.removeFirst()); // Pop 20
System.out.println(“Pop: ” + deque.removeFirst()); // Pop 10
// Using Deque as a Queue (FIFO)
deque.addLast(40); // Enqueue 40 at the end
deque.addLast(50); // Enqueue 50 at the end
deque.addLast(60); // Enqueue 60 at the end
System.out.println(“\nUsing Deque as a Queue:”);
System.out.println(“Dequeue: ” + deque.removeFirst()); // Dequeue 40
System.out.println(“Dequeue: ” + deque.removeFirst()); // Dequeue 50
System.out.println(“Dequeue: ” + deque.removeFirst()); // Dequeue 60
}
}
Output:
Using Deque as a Stack:
Pop: 30
Pop: 20
Pop: 10
Using Deque as a Queue:
Dequeue: 40
Dequeue: 50
Dequeue: 60
Clarification:
- Stack (LIFO): We utilize addFirst() to include components to the front of the deque (like pushing to a stack). We at that point utilize removeFirst() to pop components from the front (like popping from a stack).
- Queue (FIFO): We utilize addLast() to enqueue components at the end of the deque. We at that point utilize removeFirst() to dequeue components from the front (like removing from a queue).