Deque and ArrayDeque in Java

Overview

Deque (Double Ended Queue) is a linear collection that supports element insertion and removal at both ends. ArrayDeque is a resizable-array implementation of the Deque interface.

Deque Interface

Basic Deque Operations

import java.util.*;
public class DequeInterfaceDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
// Add elements at both ends
deque.addFirst("First");     // Add to front
deque.addLast("Last");       // Add to end
deque.offerFirst("Front");   // Add to front
deque.offerLast("End");      // Add to end
System.out.println("Deque: " + deque);
// Examine elements
System.out.println("First element: " + deque.getFirst());
System.out.println("Last element: " + deque.getLast());
System.out.println("Peek first: " + deque.peekFirst());
System.out.println("Peek last: " + deque.peekLast());
// Remove elements
System.out.println("Remove first: " + deque.removeFirst());
System.out.println("Remove last: " + deque.removeLast());
System.out.println("Poll first: " + deque.pollFirst());
System.out.println("Poll last: " + deque.pollLast());
System.out.println("Final deque: " + deque);
}
}

Deque as Stack (LIFO)

import java.util.*;
public class DequeAsStack {
public static void main(String[] args) {
// Using Deque as Stack (recommended over Stack class)
Deque<String> stack = new ArrayDeque<>();
// Push operations (add to top)
stack.push("First");
stack.push("Second");
stack.push("Third");
stack.push("Fourth");
System.out.println("Stack: " + stack);
// Peek (view top without removal)
System.out.println("Top element: " + stack.peek());
System.out.println("Top element (peek): " + stack.peekFirst());
// Pop operations (remove from top)
System.out.println("Popped: " + stack.pop());
System.out.println("Popped (pollFirst): " + stack.pollFirst());
System.out.println("Stack after pops: " + stack);
// Check if empty
System.out.println("Is stack empty? " + stack.isEmpty());
// Empty the stack
while (!stack.isEmpty()) {
System.out.println("Popping: " + stack.pop());
}
}
}

Deque as Queue (FIFO)

import java.util.*;
public class DequeAsQueue {
public static void main(String[] args) {
// Using Deque as Queue
Deque<String> queue = new ArrayDeque<>();
// Enqueue operations (add to end)
queue.addLast("First");
queue.addLast("Second");
queue.addLast("Third");
queue.offerLast("Fourth");
System.out.println("Queue: " + queue);
// Peek at front
System.out.println("Front element: " + queue.getFirst());
System.out.println("Front element (peek): " + queue.peekFirst());
// Dequeue operations (remove from front)
System.out.println("Dequeued: " + queue.removeFirst());
System.out.println("Dequeued (poll): " + queue.pollFirst());
System.out.println("Queue after dequeues: " + queue);
// Process all elements
while (!queue.isEmpty()) {
System.out.println("Processing: " + queue.pollFirst());
}
}
}

ArrayDeque Class

Basic ArrayDeque Operations

import java.util.*;
public class ArrayDequeBasics {
public static void main(String[] args) {
// Creating ArrayDeque
ArrayDeque<Integer> arrayDeque = new ArrayDeque<>();
// Adding elements
arrayDeque.add(10);          // Add to end
arrayDeque.addFirst(5);      // Add to front
arrayDeque.addLast(15);      // Add to end
arrayDeque.offer(20);        // Add to end
arrayDeque.offerFirst(1);    // Add to front
arrayDeque.offerLast(25);    // Add to end
System.out.println("ArrayDeque: " + arrayDeque);
System.out.println("Size: " + arrayDeque.size());
// Accessing elements
System.out.println("First element: " + arrayDeque.getFirst());
System.out.println("Last element: " + arrayDeque.getLast());
System.out.println("Peek first: " + arrayDeque.peekFirst());
System.out.println("Peek last: " + arrayDeque.peekLast());
// Checking existence
System.out.println("Contains 15: " + arrayDeque.contains(15));
// Removing elements
System.out.println("Remove first: " + arrayDeque.removeFirst());
System.out.println("Remove last: " + arrayDeque.removeLast());
System.out.println("Poll first: " + arrayDeque.pollFirst());
System.out.println("Poll last: " + arrayDeque.pollLast());
System.out.println("After removals: " + arrayDeque);
}
}

ArrayDeque Constructors

import java.util.*;
public class ArrayDequeConstructors {
public static void main(String[] args) {
// 1. Default constructor (initial capacity: 16)
ArrayDeque<String> deque1 = new ArrayDeque<>();
deque1.add("A");
deque1.add("B");
System.out.println("Default: " + deque1);
// 2. With initial capacity
ArrayDeque<Integer> deque2 = new ArrayDeque<>(50);
for (int i = 0; i < 10; i++) {
deque2.add(i);
}
System.out.println("Capacity 50: " + deque2);
// 3. From existing collection
List<String> list = Arrays.asList("X", "Y", "Z");
ArrayDeque<String> deque3 = new ArrayDeque<>(list);
System.out.println("From collection: " + deque3);
// Demonstrate capacity growth
ArrayDeque<Integer> capacityDemo = new ArrayDeque<>(3);
System.out.println("\nInitial capacity demonstration:");
for (int i = 0; i < 10; i++) {
capacityDemo.add(i);
System.out.println("Added " + i + " - Size: " + capacityDemo.size());
}
}
}

Practical Examples

1. Sliding Window Maximum

import java.util.*;
public class SlidingWindowMaximum {
public static int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) return new int[0];
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// Remove indices that are out of current window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove smaller elements from the back
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// Add current element at the back
deque.offerLast(i);
// The element at the front is the largest for current window
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
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("Array: " + Arrays.toString(nums));
System.out.println("Sliding window maximum (k=" + k + "): " + 
Arrays.toString(result));
}
}

2. Browser History Implementation

import java.util.*;
class BrowserHistory {
private Deque<String> backStack;
private Deque<String> forwardStack;
private String currentPage;
public BrowserHistory(String homepage) {
this.currentPage = homepage;
this.backStack = new ArrayDeque<>();
this.forwardStack = new ArrayDeque<>();
}
public void visit(String url) {
backStack.push(currentPage);
currentPage = url;
forwardStack.clear(); // Clear forward history on new visit
System.out.println("Visited: " + currentPage);
}
public String back(int steps) {
while (steps > 0 && !backStack.isEmpty()) {
forwardStack.push(currentPage);
currentPage = backStack.pop();
steps--;
}
System.out.println("Back to: " + currentPage);
return currentPage;
}
public String forward(int steps) {
while (steps > 0 && !forwardStack.isEmpty()) {
backStack.push(currentPage);
currentPage = forwardStack.pop();
steps--;
}
System.out.println("Forward to: " + currentPage);
return currentPage;
}
public String getCurrentPage() {
return currentPage;
}
public void displayHistory() {
System.out.println("\nBrowser History:");
System.out.println("Back Stack: " + backStack);
System.out.println("Current: " + currentPage);
System.out.println("Forward Stack: " + forwardStack);
}
}
public class BrowserHistoryExample {
public static void main(String[] args) {
BrowserHistory browser = new BrowserHistory("homepage.com");
browser.visit("google.com");
browser.visit("github.com");
browser.visit("stackoverflow.com");
browser.displayHistory();
browser.back(2);
browser.displayHistory();
browser.visit("leetcode.com");
browser.displayHistory();
browser.forward(1);
browser.displayHistory();
}
}

3. Task Scheduler

import java.util.*;
class TaskScheduler {
private Deque<String> taskQueue;
private Deque<String> completedTasks;
public TaskScheduler() {
this.taskQueue = new ArrayDeque<>();
this.completedTasks = new ArrayDeque<>();
}
public void addTask(String task) {
taskQueue.addLast(task);
System.out.println("Added task: " + task);
}
public void addUrgentTask(String task) {
taskQueue.addFirst(task);
System.out.println("Added urgent task: " + task);
}
public String executeNextTask() {
if (taskQueue.isEmpty()) {
System.out.println("No tasks to execute");
return null;
}
String task = taskQueue.pollFirst();
completedTasks.push(task);
System.out.println("Executed: " + task);
return task;
}
public String undoLastTask() {
if (completedTasks.isEmpty()) {
System.out.println("No tasks to undo");
return null;
}
String task = completedTasks.pop();
taskQueue.addFirst(task);
System.out.println("Undid task: " + task);
return task;
}
public void displayTasks() {
System.out.println("\nTask Scheduler Status:");
System.out.println("Pending tasks: " + taskQueue);
System.out.println("Completed tasks: " + completedTasks);
}
}
public class TaskSchedulerExample {
public static void main(String[] args) {
TaskScheduler scheduler = new TaskScheduler();
scheduler.addTask("Write documentation");
scheduler.addTask("Fix bug #123");
scheduler.addUrgentTask("Critical security patch");
scheduler.addTask("Code review");
scheduler.displayTasks();
scheduler.executeNextTask();
scheduler.executeNextTask();
scheduler.displayTasks();
scheduler.undoLastTask();
scheduler.displayTasks();
scheduler.executeNextTask();
scheduler.executeNextTask();
scheduler.executeNextTask(); // No more tasks
}
}

4. Palindrome Checker

import java.util.*;
public class PalindromeChecker {
public static boolean isPalindrome(String str) {
if (str == null || str.length() <= 1) {
return true;
}
Deque<Character> deque = new ArrayDeque<>();
String cleanStr = str.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();
// Add all characters to deque
for (char c : cleanStr.toCharArray()) {
deque.addLast(c);
}
// Check from both ends
while (deque.size() > 1) {
if (deque.removeFirst() != deque.removeLast()) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] testStrings = {
"racecar",
"A man a plan a canal Panama",
"hello",
"Madam, in Eden, I'm Adam",
"12321",
"not a palindrome"
};
for (String str : testStrings) {
System.out.println("'" + str + "' is palindrome: " + isPalindrome(str));
}
}
}

Advanced Operations

Iterator and Descending Iterator

import java.util.*;
public class DequeIteration {
public static void main(String[] args) {
ArrayDeque<String> deque = new ArrayDeque<>();
deque.addAll(Arrays.asList("A", "B", "C", "D", "E"));
System.out.println("Original deque: " + deque);
// Forward iteration
System.out.println("\nForward iteration:");
Iterator<String> iterator = deque.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
// Descending iteration (reverse order)
System.out.println("\nDescending iteration:");
Iterator<String> descendingIterator = deque.descendingIterator();
while (descendingIterator.hasNext()) {
System.out.println(descendingIterator.next());
}
// For-each loop
System.out.println("\nFor-each loop:");
for (String element : deque) {
System.out.println(element);
}
// Stream API
System.out.println("\nStream processing:");
deque.stream()
.map(String::toLowerCase)
.forEach(System.out::println);
}
}

Bulk Operations

import java.util.*;
public class DequeBulkOperations {
public static void main(String[] args) {
ArrayDeque<Integer> deque1 = new ArrayDeque<>();
deque1.addAll(Arrays.asList(1, 2, 3, 4, 5));
ArrayDeque<Integer> deque2 = new ArrayDeque<>();
deque2.addAll(Arrays.asList(4, 5, 6, 7, 8));
System.out.println("Deque1: " + deque1);
System.out.println("Deque2: " + deque2);
// Add all elements from another collection
deque1.addAll(deque2);
System.out.println("After addAll: " + deque1);
// Remove all elements from another collection
deque1.removeAll(Arrays.asList(6, 7, 8));
System.out.println("After removeAll: " + deque1);
// Retain only common elements
deque1.retainAll(Arrays.asList(1, 2, 3, 9));
System.out.println("After retainAll: " + deque1);
// Clear all elements
deque1.clear();
System.out.println("After clear: " + deque1);
System.out.println("Is empty: " + deque1.isEmpty());
}
}

Performance Comparison

import java.util.*;
public class PerformanceComparison {
public static void main(String[] args) {
int size = 1000000;
// ArrayDeque as Stack vs Stack class
long startTime = System.currentTimeMillis();
Deque<Integer> arrayDequeStack = new ArrayDeque<>();
for (int i = 0; i < size; i++) {
arrayDequeStack.push(i);
}
while (!arrayDequeStack.isEmpty()) {
arrayDequeStack.pop();
}
long arrayDequeTime = System.currentTimeMillis() - startTime;
startTime = System.currentTimeMillis();
Stack<Integer> stackClass = new Stack<>();
for (int i = 0; i < size; i++) {
stackClass.push(i);
}
while (!stackClass.isEmpty()) {
stackClass.pop();
}
long stackClassTime = System.currentTimeMillis() - startTime;
System.out.println("ArrayDeque as Stack: " + arrayDequeTime + "ms");
System.out.println("Stack class: " + stackClassTime + "ms");
// ArrayDeque as Queue vs LinkedList
startTime = System.currentTimeMillis();
Deque<Integer> arrayDequeQueue = new ArrayDeque<>();
for (int i = 0; i < size; i++) {
arrayDequeQueue.offer(i);
}
while (!arrayDequeQueue.isEmpty()) {
arrayDequeQueue.poll();
}
long arrayDequeQueueTime = System.currentTimeMillis() - startTime;
startTime = System.currentTimeMillis();
Queue<Integer> linkedListQueue = new LinkedList<>();
for (int i = 0; i < size; i++) {
linkedListQueue.offer(i);
}
while (!linkedListQueue.isEmpty()) {
linkedListQueue.poll();
}
long linkedListTime = System.currentTimeMillis() - startTime;
System.out.println("ArrayDeque as Queue: " + arrayDequeQueueTime + "ms");
System.out.println("LinkedList as Queue: " + linkedListTime + "ms");
}
}

Key Features and Advantages

1. No Capacity Restrictions

import java.util.*;
public class CapacityDemo {
public static void main(String[] args) {
ArrayDeque<Integer> deque = new ArrayDeque<>(3);
System.out.println("Adding elements beyond initial capacity:");
for (int i = 0; i < 10; i++) {
deque.add(i);
System.out.println("Size: " + deque.size() + ", Deque: " + deque);
}
}
}

2. Null Elements Not Allowed

import java.util.*;
public class NullElementsDemo {
public static void main(String[] args) {
ArrayDeque<String> deque = new ArrayDeque<>();
deque.add("Valid");
// deque.add(null); // This would throw NullPointerException
System.out.println("Deque: " + deque);
}
}

Best Practices

import java.util.*;
public class DequeBestPractices {
public static void main(String[] args) {
// 1. Use interface type for declarations
Deque<String> deque = new ArrayDeque<>();
// 2. Choose appropriate initial capacity
Deque<Integer> largeDeque = new ArrayDeque<>(1000);
// 3. Use as Stack (LIFO)
Deque<String> stack = new ArrayDeque<>();
stack.push("A");
stack.push("B");
String top = stack.pop();
// 4. Use as Queue (FIFO)
Deque<String> queue = new ArrayDeque<>();
queue.offer("A");
queue.offer("B");
String front = queue.poll();
// 5. Prefer offer/poll/peek over add/remove/element for queues
Deque<String> safeDeque = new ArrayDeque<>();
safeDeque.offer("Element"); // Returns false if capacity restricted
String element = safeDeque.poll(); // Returns null if empty
String peeked = safeDeque.peek(); // Returns null if empty
// 6. Use descendingIterator for reverse order
Deque<Integer> numbers = new ArrayDeque<>(Arrays.asList(1, 2, 3, 4, 5));
Iterator<Integer> reverseIterator = numbers.descendingIterator();
// 7. Consider thread safety
Deque<String> synchronizedDeque = 
Collections.synchronizedDeque(new ArrayDeque<>());
}
}

Summary

ArrayDeque Advantages:

More efficient than Stack for LIFO operations
More efficient than LinkedList for most operations
No capacity restrictions (resizable)
Better memory usage than LinkedList
Faster iteration

Common Use Cases:

Stack operations (LIFO)
Queue operations (FIFO)
Double-ended queue operations
Sliding window algorithms
Undo/Redo functionality
Breadth-first search

Performance Characteristics:

Add/remove from both ends: O(1)
Access first/last element: O(1)
Search: O(n)
Iteration: O(n)

ArrayDeque is generally the best choice for stack and queue operations when thread safety is not required.