google-site-verification: google61fe8ba583a51912.html
MACRO NEPAL
Deque and ArrayDeque in Java – Complete Guide
awiskar acharya
October 30, 2025
9:36 am

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.

Category : JAVA

Leave a Reply

Your email address will not be published. Required fields are marked *


Macro Nepal Helper