WikiGalaxy
Dequeue Operation
Introduction to Dequeue Operation:
A dequeue (double-ended queue) is a data structure that allows insertion and deletion of elements from both ends. It supports operations such as adding or removing items from either the front or the back of the queue, making it versatile for various applications.
Example 1: Basic Dequeue Operations
In this example, we demonstrate basic operations like adding and removing elements from both ends of a dequeue.
import java.util.*;
public class DequeueExample {
public static void main(String[] args) {
Deque deque = new LinkedList<>();
// Adding elements to the front and back
deque.addFirst("Front");
deque.addLast("Back");
// Removing elements from the front and back
System.out.println("Removed: " + deque.removeFirst());
System.out.println("Removed: " + deque.removeLast());
}
}
Console Output:
Removed: Front
Removed: Back
Example 2: Using Dequeue for Palindrome Check
This example uses a dequeue to check if a given string is a palindrome by comparing characters from both ends.
import java.util.*;
public class PalindromeCheck {
public static boolean isPalindrome(String str) {
Deque deque = new LinkedList<>();
for (char c : str.toCharArray()) {
deque.addLast(c);
}
while (deque.size() > 1) {
if (deque.removeFirst() != deque.removeLast()) {
return false;
}
}
return true;
}
public static void main(String[] args) {
System.out.println("Is 'racecar' a palindrome? " + isPalindrome("racecar"));
System.out.println("Is 'hello' a palindrome? " + isPalindrome("hello"));
}
}
Console Output:
Is 'racecar' a palindrome? true
Is 'hello' a palindrome? false
Example 3: Dequeue as a Stack
A dequeue can be used as a stack, where elements are added and removed from the same end.
import java.util.*;
public class DequeueAsStack {
public static void main(String[] args) {
Deque stack = new LinkedList<>();
// Push elements onto the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Pop elements from the stack
System.out.println("Popped: " + stack.pop());
System.out.println("Popped: " + stack.pop());
}
}
Console Output:
Popped: 30
Popped: 20
Example 4: Dequeue as a Queue
A dequeue can also function as a regular queue, where elements are added at the back and removed from the front.
import java.util.*;
public class DequeueAsQueue {
public static void main(String[] args) {
Deque queue = new LinkedList<>();
// Enqueue elements
queue.addLast("First");
queue.addLast("Second");
// Dequeue elements
System.out.println("Dequeued: " + queue.removeFirst());
System.out.println("Dequeued: " + queue.removeFirst());
}
}
Console Output:
Dequeued: First
Dequeued: Second
Example 5: Using Dequeue for Sliding Window Problem
Dequeue can be used to solve the sliding window problem efficiently by maintaining the maximum of each window of size k.
import java.util.*;
public class SlidingWindowMaximum {
public static int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
int ri = 0;
Deque deque = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
// Remove numbers out of range k
while (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
// Remove smaller numbers in k range as they are useless
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// Add new number at the end of deque
deque.offer(i);
// The first number is the largest one in the window
if (i >= k - 1) {
result[ri++] = nums[deque.peek()];
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] result = maxSlidingWindow(nums, k);
System.out.println(Arrays.toString(result));
}
}
Console Output:
[3, 3, 5, 5, 6, 7]
