Java Notes
HubArray IntroductionArray OperationsArray Programs — FundamentalsArray Interview QuestionsJagged Array in JavaMulti Dimensional ArrayOne Dimensional Arraybreak and continue in JavaDo-While Loop in JavaFor Loop in JavaIf-Else Statements in JavaNested Loops in JavaSwitch-Case in JavaWhile Loop in JavaJava Compilation ProcessFeatures of JavaYour First Java ProgramHistory of JavaJava EditionsJava Program StructureJDK, JRE, and JVMWhat is Java?Immutable Strings in JavaString Class in JavaString Interview QuestionsString MethodsString Programs — FundamentalsStringBuffer in JavaStringBuilder in JavaComments in JavaData Types in JavaIdentifiers in JavaInput and Output in JavaKeywords in JavaOperators in JavaType Casting in JavaVariables in JavaAbstract Class in JavaAbstraction in JavaAnonymous Class in JavaClass and Object in JavaConstructor in JavaEncapsulation in JavaInheritance in JavaInner Class in JavaInterface in JavaMethod Overloading in JavaMethod Overriding in JavaObject Class in JavaObject Cloning in JavaOOPs IntroductionPolymorphism in Javastatic Keyword in Javasuper Keyword in Javathis Keyword in JavaWrapper Class in JavaCollections Framework OverviewCollections Practice ProgramsComparable vs Comparator in JavaGenerics in JavaIterator in JavaArrayList in JavaLinkedList in JavaStack in Java — Collections FrameworkVector in JavaHashMap in JavaHashtable in JavaLinkedHashMap in JavaTreeMap in JavaArrayDeque in JavaDeque Interface in JavaPriorityQueue in JavaHashSet in JavaLinkedHashSet in JavaTreeSet in JavaException Handling Best PracticesCustom Exceptions in JavaException Hierarchy in JavaFinally Block in JavaException Handling Introductionthrow and throws Keywords in JavaTry-Catch Block in JavaBuffered Streams in JavaByte Streams in JavaCharacter Streams in JavaDeserialization in JavaFile Class in JavaJava NIO PackageSerialization in JavaDate and Time API in Java 8Default and Static Methods in InterfacesFunctional Interface in Java 8Lambda Expression in Java 8Method Reference in Java 8Optional Class in Java 8Stream API in Java 8Creating Threads in JavaDaemon Threads in JavaExecutor Framework in JavaInter-Thread Communication in JavaMultithreading Programs in JavaRunnable Interface in JavaSynchronization in JavaThread Class in JavaThread IntroductionThread Life Cycle in JavaThread Priority in JavaBatch Processing in JDBCCallableStatement in JDBCJDBC ArchitectureJDBC IntroductionJDBC ProjectsMySQL Connection with JDBCPreparedStatement in JDBCResultSet in JDBCStatement Interface in JDBCTransaction Management in JDBCCookies in ServletsExpression Language (EL)GenericServletHttpServletJSP IntroductionJSP Tags and JSTLMVC ArchitectureRequest and Response ObjectsServlet IntroductionServlet Life CycleSession TrackingDependency InjectionAPI GatewayConfig ServerDocker DeploymentEureka Server - Service DiscoverySpring BeansCRUD ApplicationException Handling in Spring BootJWT Authentication — Java ProgrammingREST API with Spring BootSpring SecuritySpring Boot IntroductionSpring Data JPAValidation in Spring BootSpring Core ContainerSpring Framework IntroductionDynamic Programming in JavaGraph Data Structure in JavaHashing in JavaHeap (DSA)Linked List in JavaQueue in JavaRecursion in JavaSearching Algorithms in JavaSorting Algorithms in JavaStack in Java — DSA in JavaTime ComplexityTree Data Structure in JavaAdapter Design PatternBuilder Design PatternFactory Design PatternMVC Pattern — Java ProgrammingObserver Design PatternSingleton Design PatternArray Programs — PracticeBasic Java ProgramsCollection ProgramsJDBC ProgramsMultithreading ProgramsOOP ProgramsPlacement Coding QuestionsString Programs — PracticeBanking System — Java ProgrammingChat ApplicationE-Commerce BackendEmployee Management SystemLibrary Management System — Java ProgrammingSpring Boot Fullstack ProjectStudent Management System — Java ProgrammingCoding Interview QuestionsCollections Interview QuestionsCore Java Interview QuestionsJDBC Interview QuestionsMultithreading Interview QuestionsOOPs Interview QuestionsSpring Framework Interview QuestionsJava Cheat SheetImportant Formulas & ConceptsImportant Java ProgramsQuick Revision Notes — Java ProgrammingJava Master Course - Learning Roadmap
Complete guide to Java Deque interface — double-ended queue operations, stack and queue usage, method families, comparison of implementations, and best practices.
What is a Deque?
A Deque (pronounced "deck") stands for Double-Ended Queue — a linear data structure that allows insertion and removal at both ends (front and rear).
java example
public interface Deque<E> extends Queue<E> {
// First element (head/front) operations
void addFirst(E e);
boolean offerFirst(E e);
E removeFirst();
E pollFirst();
E getFirst();
E peekFirst();
// Last element (tail/rear) operations
void addLast(E e);
boolean offerLast(E e);
E removeLast();
E pollLast();
E getLast();
E peekLast();
// Stack operations
void push(E e); // addFirst
E pop(); // removeFirst
E peek(); // peekFirst
// Queue operations (inherited)
boolean offer(E e); // offerLast
E poll(); // pollFirst
E peek(); // peekFirst
}Method Families
Deque methods come in pairs — one throws an exception, one returns a special value:
First Element (Head) Operations
| Operation | Throws Exception | Returns null/false |
|---|---|---|
| Insert | addFirst(e) → IllegalStateException | offerFirst(e) → false |
| Remove | removeFirst() → NoSuchElementException | pollFirst() → null |
| Examine | getFirst() → NoSuchElementException | peekFirst() → null |
Last Element (Tail) Operations
| Operation | Throws Exception | Returns null/false |
|---|---|---|
| Insert | addLast(e) → IllegalStateException | offerLast(e) → false |
| Remove | removeLast() → NoSuchElementException | pollLast() → null |
| Examine | getLast() → NoSuchElementException | peekLast() → null |
Deque Used as Queue
| Queue Method | Equivalent Deque Method |
|---|---|
offer(e) | offerLast(e) |
poll() | pollFirst() |
peek() | peekFirst() |
add(e) | addLast(e) |
remove() | removeFirst() |
element() | getFirst() |
Deque Used as Stack
| Stack Method | Equivalent Deque Method |
|---|---|
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
Implementations Comparison
| Feature | ArrayDeque | LinkedList |
|---|---|---|
| Internal structure | Circular resizable array | Doubly-linked list |
| Memory per element | ~8 bytes (array slot) | ~48 bytes (Node object) |
| Cache performance | Excellent (contiguous) | Poor (scattered heap) |
| Null elements | ❌ Not allowed | ✅ Allowed |
| Random access | No (but fast internally) | No |
| Thread-safe | No | No |
| Performance | Faster (in practice) | Slower |
| Recommended | ✅ Yes (default choice) | Only if null elements needed |
Why ArrayDeque is Preferred
java example
// Official recommendation from Java docs:
// "This class is likely to be faster than Stack when used as a stack,
// and faster than LinkedList when used as a queue."
// PREFERRED
Deque<String> deque = new ArrayDeque<>();
// AVOID (more memory, worse cache performance)
Deque<String> deque = new LinkedList<>();Complete Example
Example
import java.util.*;
public class DequeDemo {
public static void main(String[] args) {
Deque<String> deque = new ArrayDeque<>();
// === Double-ended queue operations ===
deque.addFirst("B"); // [B]
deque.addFirst("A"); // [A, B]
deque.addLast("C"); // [A, B, C]
deque.addLast("D"); // [A, B, C, D]
System.out.println("Deque: " + deque); // [A, B, C, D]
System.out.println("First: " + deque.peekFirst()); // A
System.out.println("Last: " + deque.peekLast()); // D
deque.pollFirst(); // Remove A → [B, C, D]
deque.pollLast(); // Remove D → [B, C]
System.out.println("After polls: " + deque); // [B, C]
// === As a Stack (LIFO) ===
System.out.println("\n--- Stack mode ---");
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // [1]
stack.push(2); // [2, 1]
stack.push(3); // [3, 2, 1]
System.out.println("Stack: " + stack);
System.out.println("Pop: " + stack.pop()); // 3
System.out.println("Peek: " + stack.peek()); // 2
// === As a Queue (FIFO) ===
System.out.println("\n--- Queue mode ---");
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // [1]
queue.offer(2); // [1, 2]
queue.offer(3); // [1, 2, 3]
System.out.println("Queue: " + queue);
System.out.println("Poll: " + queue.poll()); // 1
System.out.println("Peek: " + queue.peek()); // 2
// === Iteration ===
System.out.println("\n--- Iteration ---");
Deque<String> items = new ArrayDeque<>(Arrays.asList("X", "Y", "Z"));
// Forward (first to last)
System.out.print("Forward: ");
Iterator<String> fwd = items.iterator();
while (fwd.hasNext()) System.out.print(fwd.next() + " ");
// Backward (last to first)
System.out.print("\nBackward: ");
Iterator<String> bwd = items.descendingIterator();
while (bwd.hasNext()) System.out.print(bwd.next() + " ");
}
}
Output
Deque as Queue (FIFO): [First, Second, Third] Poll: First Remaining: [Second, Third] Deque as Stack (LIFO): Push: X, Y, Z Deque: [Z, Y, X] Pop: Z Remaining: [Y, X]
Practical Use Cases
1. Sliding Window Maximum
Example
public static int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deque = new ArrayDeque<>(); // Stores indices
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// Remove elements outside window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove smaller elements from back (they'll never be max)
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
// nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
// Output: [3, 3, 5, 5, 6, 7]
2. BFS with Level Tracking
Example
public static void bfsLevels(TreeNode root) {
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
System.out.println(level);
}
}
3. Palindrome Check
java example
public static boolean isPalindrome(String str) {
Deque<Character> deque = new ArrayDeque<>();
for (char c : str.toLowerCase().toCharArray()) {
if (Character.isLetterOrDigit(c)) {
deque.addLast(c);
}
}
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) {
return false;
}
}
return true;
}
System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true4. Undo/Redo with Bounded History
java example
public class UndoRedoManager<T> {
private final Deque<T> undoStack = new ArrayDeque<>();
private final Deque<T> redoStack = new ArrayDeque<>();
private final int maxHistory;
public UndoRedoManager(int maxHistory) {
this.maxHistory = maxHistory;
}
public void execute(T state) {
undoStack.push(state);
if (undoStack.size() > maxHistory) {
// Use removeLast to trim from bottom of stack!
((ArrayDeque<T>) undoStack).removeLast();
}
redoStack.clear();
}
public T undo() {
if (undoStack.isEmpty()) return null;
T state = undoStack.pop();
redoStack.push(state);
return undoStack.peek();
}
public T redo() {
if (redoStack.isEmpty()) return null;
T state = redoStack.pop();
undoStack.push(state);
return state;
}
}Thread-Safe Deque Implementations
java example
// ConcurrentLinkedDeque — non-blocking, unbounded
Deque<String> concurrentDeque = new ConcurrentLinkedDeque<>();
// LinkedBlockingDeque — bounded, blocking operations
BlockingDeque<String> blockingDeque = new LinkedBlockingDeque<>(100);
blockingDeque.putFirst("item"); // Blocks if full
blockingDeque.putLast("item"); // Blocks if full
String item = blockingDeque.takeFirst(); // Blocks if empty
String item2 = blockingDeque.takeLast(); // Blocks if emptyDeque vs Queue vs Stack
| Feature | Queue | Stack (legacy) | Deque |
|---|---|---|---|
| Insert/remove ends | Rear/Front only | Top only | Both ends |
| Java interface | Queue<E> | — (class) | Deque<E> extends Queue |
| Recommended impl | ArrayDeque | ArrayDeque | ArrayDeque |
| FIFO | Yes | No | Yes (as queue) |
| LIFO | No | Yes | Yes (as stack) |
| Both ends | No | No | Yes |
Common Mistakes
1. Using LinkedList as Deque
java example
// WRONG — LinkedList has poor cache performance
Deque<Integer> deque = new LinkedList<>();
// CORRECT — ArrayDeque is faster
Deque<Integer> deque = new ArrayDeque<>();2. Adding Null to ArrayDeque
java example
Deque<String> deque = new ArrayDeque<>();
deque.offer(null); // NullPointerException!
// ArrayDeque uses null as a sentinel — can't store null3. Confusing Stack Direction
Example
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // Adds to FIRST (head)
stack.push(2); // Adds to FIRST (head)
// Deque is: [2, 1] — 2 is the "top" (first)
// Don't confuse with addLast!
4. Using java.util.Stack
java example
// LEGACY — don't use
Stack<Integer> stack = new Stack<>();
// MODERN — use Deque
Deque<Integer> stack = new ArrayDeque<>();Interview Questions
Q1: What is a Deque and how does it differ from a Queue?
A: A Deque (Double-Ended Queue) allows insertion and removal at both ends, while Queue only supports insertion at the rear and removal from the front (FIFO).
Q2: Why is ArrayDeque preferred over LinkedList for Deque operations?
A: ArrayDeque uses a contiguous circular array (better cache performance, less memory overhead). LinkedList uses scattered nodes (48 bytes per node, cache misses).
Q3: Can ArrayDeque be used as both Stack and Queue?
A: Yes. As stack: push/pop/peek operate on the first end. As queue: offer/poll/peek use last/first ends.
Q4: What is the time complexity of Deque operations in ArrayDeque?
A: All operations (addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast) are O(1) amortized.
Q5: Can ArrayDeque hold null elements?
A: No. ArrayDeque uses null internally as a marker for empty slots. Attempting to add null throws NullPointerException.
Q6: What is the difference between offer() and add() in Deque?
A: add() throws an exception if the operation fails (e.g., capacity-restricted deque is full). offer() returns false. For ArrayDeque (unbounded), they behave identically.
Q8: What is the difference between Deque and Queue interfaces?
A: Queue supports operations at one end only (add at tail, remove from head — FIFO). Deque (Double-Ended Queue) supports operations at BOTH ends (addFirst/addLast, removeFirst/removeLast). Deque extends Queue, so every Deque is also a Queue but with additional capabilities.
Q9: How can Deque be used as both Stack and Queue?
A: As Queue (FIFO): offerLast() to enqueue, pollFirst() to dequeue. As Stack (LIFO): push() (addFirst) to push, pop() (removeFirst) to pop. The Deque interface explicitly documents these dual usage patterns.
Q10: What are the two categories of Deque methods?
A: Each operation has two forms: (1) Throwing — addFirst(), removeFirst(), getFirst() throw exceptions on failure. (2) Special value — offerFirst(), pollFirst(), peekFirst() return null/false on failure. Use throwing methods when failure is a bug; use special-value methods when empty is a valid state.
Q11: What implementations of Deque are available in Java?
A: (1) ArrayDeque — resizable circular array, fastest for most cases. (2) LinkedList — doubly-linked list, also implements List. (3) ConcurrentLinkedDeque — thread-safe, lock-free. (4) LinkedBlockingDeque — bounded, blocking, thread-safe. Choose based on thread-safety needs and whether you need List functionality.
Q12: Why is Deque preferred over Stack class for stack operations?
A: Java docs officially recommend Deque over Stack because: (1) Stack extends Vector with unnecessary synchronization, (2) Stack exposes random-access methods violating LIFO contract, (3) Deque provides a clean, consistent interface, (4) ArrayDeque implementation is significantly faster than Stack.
Summary
| Aspect | Deque Interface |
|---|---|
| Extends | Queue |
| Operations | Both ends — first and last |
| Can serve as | Queue (FIFO), Stack (LIFO), or both |
| Best implementation | ArrayDeque (default choice) |
| Thread-safe impl | ConcurrentLinkedDeque, LinkedBlockingDeque |
| Key advantage | Replaces both Queue and Stack with one interface |
| Null elements | Depends on implementation (ArrayDeque: No) |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Deque Interface in Java.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Java Master Course topic.
Search Terms
java-master-course, java master course, java, master, course, collections, framework, queue
Related Java Master Course Topics
Continue learning this concept
Collections FrameworkArrayDeque in JavaComplete guide to Java ArrayDeque — circular array implementation, resizing strategy, performance advantages over LinkedList and Stack, internal working, and practical usage patterns.Collections FrameworkPriorityQueue in JavaComplete guide to Java PriorityQueue — binary heap implementation, min-heap and max-heap, internal working, heapify operations, comparison with other queues, and practical applications.Collections FrameworkCollections Framework OverviewComplete guide to Java Collections Framework covering hierarchy, interfaces, implementations, algorithms, and choosing the right collection for your use case.Collections FrameworkCollections Practice ProgramsComprehensive Java Collections practice programs covering List, Set, Map, Queue operations with solutions, explanations, and time complexity analysis.Collections FrameworkComparable vs Comparator in JavaDeep dive into Comparable and Comparator interfaces in Java — natural ordering, custom sorting, lambda expressions, method references, and practical comparisons with examples.Collections FrameworkGenerics in JavaComplete guide to Java Generics — type parameters, bounded types, wildcards, type erasure, generic methods, generic classes, and common patterns with practical examples.