ArrayDeque in Java

ArrayDeque<E> is a resizable array implementation of a double-ended queue (Deque) that allows insertion and removal at both ends in O(1) time (amortized).

Creation

General Declaration

ArrayDeque<Integer> deque = new ArrayDeque<>();

Interface-based Declarations

// For Queue operations (FIFO)
Queue<Integer> queue = new ArrayDeque<>();

// For Stack operations (LIFO) - recommended over Stack class
Deque<Integer> stack = new ArrayDeque<>();

// For full Deque operations (both ends)
Deque<Integer> deque = new ArrayDeque<>();

Key Methods

1. Add Elements

Method	Description
add(E e)	Adds element at the tail (throws exception if fails)
offer(E e)	Adds at tail (returns false if fails)
addFirst(E e)	Inserts at the head
addLast(E e)	Inserts at the tail
offerFirst(E e)	Inserts at head, returns false if fails
offerLast(E e)	Inserts at tail, returns false if fails

2. Remove Elements

Method	Description
remove()	Removes from head (throws exception if empty)
poll()	Removes from head (returns null if empty)
removeFirst()	Removes first element (throws exception if empty)
removeLast()	Removes last element (throws exception if empty)
pollFirst()	Removes first element (returns null if empty)
pollLast()	Removes last element (returns null if empty)

3. Examine Elements (Peek)

Method	Description
element()	Retrieves head (throws exception if empty)
peek()	Retrieves head (returns null if empty)
getFirst()	Retrieves first element (throws exception if empty)
getLast()	Retrieves last element (throws exception if empty)
peekFirst()	Retrieves first element (returns null if empty)
peekLast()	Retrieves last element (returns null if empty)

4. Stack Operations (LIFO)

ArrayDeque can be used as a stack instead of the Stack class:

Method	Description
push(E e)	Same as addFirst()
pop()	Same as removeFirst()
peek()	Same as peekFirst()

5. Other Utilities

Method	Description
size()	Returns number of elements
isEmpty()	Checks if deque is empty
iterator()	Returns iterator from first to last
descendingIterator()	Returns iterator from last to first
clear()	Removes all elements
contains(Object o)	Checks if element exists
toArray()	Converts to array

Usage Patterns

As a Stack (LIFO: Last In, First Out)

// Recommended declaration for stack
Deque<Integer> stack = new ArrayDeque<>();

// Use these methods for stack operations
stack.push(E e)    // Insert at top
stack.pop()        // Remove from top
stack.peek()       // Look at top without removing

As a Queue (FIFO: First In, First Out)

// Recommended declaration for queue
Queue<Integer> queue = new ArrayDeque<>();

// Use these methods for queue operations
queue.offer(E e)   // Add at tail
queue.poll()       // Remove from head
queue.peek()       // Look at head without removing

As a Deque (Double Ended Queue)

// Declaration for full deque functionality
Deque<Integer> deque = new ArrayDeque<>();

// Insertions
deque.offerFirst(E e)  // Add at front
deque.offerLast(E e)   // Add at rear

// Removals
deque.pollFirst()      // Remove from front
deque.pollLast()       // Remove from rear

// Peek
deque.peekFirst()      // Look at front
deque.peekLast()       // Look at rear

Example Usage

import java.util.*;

public class ArrayDequeExample {
    public static void main(String[] args) {
        // Different ways to declare based on usage
        ArrayDeque<Integer> generalDeque = new ArrayDeque<>();
        Queue<Integer> queue = new ArrayDeque<>();
        Deque<Integer> stack = new ArrayDeque<>();
        Deque<Integer> deque = new ArrayDeque<>();

        // Using as general deque
        generalDeque.addFirst(10);   // [10]
        generalDeque.addLast(20);    // [10, 20]
        generalDeque.offerFirst(5);  // [5, 10, 20]
        generalDeque.offerLast(30);  // [5, 10, 20, 30]

        System.out.println(generalDeque.peekFirst()); // 5
        System.out.println(generalDeque.peekLast());  // 30

        generalDeque.removeFirst();  // removes 5 → [10, 20, 30]
        generalDeque.removeLast();   // removes 30 → [10, 20]

        // Using as stack
        stack.push(99);       // stack push → [99, 10, 20]
        System.out.println(stack.pop()); // 99

        // Using as queue
        queue.offer(100);     // add to rear
        queue.offer(200);     // add to rear
        System.out.println(queue.poll()); // remove from front

        System.out.println(generalDeque); // [10, 20]
    }
}

Method Selection Rule

• Use push, pop, peek → when acting like a stack
• Use offer, poll, peek → when acting like a queue
• Use offerFirst/Last, pollFirst/Last, peekFirst/Last → when acting like a deque

Note: Methods that return null or false on failure are generally safer than those that throw exceptions.