How to Use a Queue and Stack in Java: A Modern Developer Guide

In Java, implement a queue by instantiating the Queue interface with ArrayDeque or LinkedList for First-In-First-Out (FIFO) operations using offer() and poll(). For a stack, use the Deque interface with ArrayDeque for Last-In-First-Out (LIFO) operations using push() and pop(), avoiding the legacy java.util.Stack class.

Understanding Queue and Stack Data Structures in Java

Data structures dictate how computer programs store, organize, and process memory. Among linear data structures, queues and stacks serve as fundamental building blocks for algorithmic problem-solving, event processing, memory management, and system design. While both structures hold collections of elements, they process those elements using entirely inverse access patterns.

The First-In-First-Out (FIFO) Queue Concept

A queue models a real-world waiting line. It enforces a First-In-First-Out (FIFO) policy: the first element added to the collection is the first one to be removed.

In software architectures, queues manage asynchronous tasks, process incoming HTTP requests, schedule background jobs, and buffer data streams between independent services. Elements are added at the back (tail) of the queue and removed from the front (head).

The Last-In-First-Out (LIFO) Stack Concept

A stack models a physical pile of items, such as a stack of plates. It enforces a Last-In-First-Out (LIFO) policy: the most recently added element is the first one to be removed.

Stacks are essential for execution call stacks in programming runtimes, parsing mathematical expressions, undo/redo mechanisms in software applications, and graph traversal algorithms like Depth-First Search (DFS). Elements are both added and removed from a single point of entry, known as the top of the stack.

How to Implement and Use a Queue in Java

In the Java Collections Framework, a queue is represented primarily by the java.util.Queue interface. Because Queue is an interface, developers cannot instantiate it directly using the new keyword. Instead, an instantiation must choose a concrete implementation class depending on performance requirements, dynamic sizing capabilities, and thread-safety constraints.

Instantiating a Queue with ArrayDeque and LinkedList

The two most common non-concurrent implementations of the Queue interface are java.util.ArrayDeque and java.util.LinkedList.

1. ArrayDeque (Array Double Ended Queue): Backed by a resizable, circular array. It offers superior memory efficiency and faster operational throughput for standard queue operations because it avoids object allocation for individual node wrappers. In modern Java development, ArrayDeque is the default recommendation for single-threaded queue needs.
2. LinkedList: Backed by a doubly-linked node structure. Each element is wrapped inside a discrete node object containing references to both the previous and next nodes. While it permits constant-time insertions and deletions, it incurs higher memory overhead due to pointer tracking and pointer-chasing garbage collection overhead.

To declare and instantiate a modern Java queue, use the interface type on the left side of the assignment and the concrete class on the right:

Queue line = new ArrayDeque<>();

Alternatively, if linked node behavior is required:

Queue line = new LinkedList<>();

Essential Queue Operations: Exception-Throwing vs. Return-Value Methods

The java.util.Queue interface defines six core methods divided into two distinct functional categories based on how they handle boundary conditions, such as attempting to remove an element from an empty queue or inserting into a capacity-restricted queue.

Exception-Throwing Methods

These methods throw a runtime exception (IllegalStateException or NoSuchElementException) if the operation fails.

• add(e): Inserts the specified element at the tail of the queue. Throws IllegalStateException if no space is currently available in a capacity-restricted queue.
• remove(): Retrieves and removes the head of the queue. Throws NoSuchElementException if the queue is empty.
• element(): Retrieves, but does not remove, the head of the queue. Throws NoSuchElementException if the queue is empty.

Special-Value (Safe) Return Methods

These methods return a special value (false or null) instead of throwing an exception when an operation cannot be completed immediately. They are strongly preferred in capacity-bounded or dynamic operational workflows.

• offer(e): Inserts the specified element at the tail of the queue. Returns true upon success and false if the element cannot be added due to capacity limits.
• poll(): Retrieves and removes the head of the queue, returning null if the queue is completely empty.
• peek(): Retrieves, but does not remove, the head of the queue, returning null if the queue is empty.

Queue Usage Code Mechanics

Consider a real-world print job manager processing document requests in the exact order they arrive:

1. Import required classes: import java.util.Queue; and import java.util.ArrayDeque;
2. Initialize the collection: Queue printJobs = new ArrayDeque<>();
3. Add items to the tail of the queue using safe insertions:
   
   
   • printJobs.offer("Document_A.pdf");
   • printJobs.offer("Document_B.pdf");
   • printJobs.offer("Document_C.pdf");
4. Inspect the item at the front of the queue without mutating the structure:
   
   
   • String nextUp = printJobs.peek(); (This evaluates to "Document_A.pdf", while the queue length remains 3).
5. Process and remove items sequentially from the head:
   
   
   • String processedJob = printJobs.poll(); (Returns "Document_A.pdf" and removes it).
   • String nextProcessedJob = printJobs.poll(); (Returns "Document_B.pdf" and removes it).
6. Safely inspect an empty or depleted queue:
   
   
   • Calling printJobs.poll() until empty returns null once all items are consumed, preventing application crashes.

How to Implement and Use a Stack in Java

Handling stack structures in Java requires understanding an important evolution within the Java standard library: the transition from legacy classes to modern collection interfaces.

Why Legacy java.util.Stack Should Be Avoided

When Java 1.0 was released in 1996, it introduced java.util.Stack as a concrete implementation of a LIFO stack. However, modern Java architectural standards consider java.util.Stack obsolete and strongly discourage its use in contemporary codebases for three major structural reasons:

1. Flawed Object-Oriented Design: java.util.Stack extends java.util.Vector. In class hierarchy design, inheritance implies an "is-a" relationship. Inheriting from Vector means a Stack is a vector, which exposes methods like get(index), insertElementAt(element, index), and remove(index). This completely destroys the encapsulation of a stack by allowing code to insert or delete elements in the middle of the collection rather than strictly enforcing top-only access.
2. Synchronization Overhead: Vector (and by extension Stack) synchronizes every individual operation using internal object locks. This introduces performance degradation in single-threaded environments and inefficient coarse-grained locking in multi-threaded contexts.
3. Lack of Interface Abstraction: java.util.Stack is a concrete class rather than an interface implementation, making it difficult to swap underlying data structure strategies without refactoring broad code dependencies.

Using Deque and ArrayDeque as a Modern Stack

Since Java 6, the standard and officially recommended replacement for a LIFO stack is the java.util.Deque (Double Ended Queue) interface instantiated with java.util.ArrayDeque.

A double-ended queue supports element insertion and removal at both ends. When restricted to operations at a single end (the head), a Deque functions as a fast, un-synchronized, properly encapsulated LIFO stack.

To instantiate a modern, high-performance stack in Java:

Deque stack = new ArrayDeque<>();

Essential Stack Operations: Push, Pop, and Peek

When utilizing Deque as a stack, use the explicit LIFO stack operations declared directly on the interface:

• push(e): Pushes an element onto the top of the stack (equivalent to adding at the front of the deque). If no space is available, it throws an IllegalStateException.
• pop(): Pops (retrieves and removes) the element from the top of the stack. If the stack is empty, it throws a NoSuchElementException.
• peek(): Retrieves, but does not remove, the element at the top of the stack. Returns null if the stack is empty.

Stack Usage Code Mechanics

Consider an undo history manager inside a text processing application:

1. Import required classes: import java.util.Deque; and import java.util.ArrayDeque;
2. Initialize the stack collection: Deque actionHistory = new ArrayDeque<>();
3. Push recent user actions onto the stack:
   
   
   • actionHistory.push("Typed 'Hello'");
   • actionHistory.push("Formatted Bold");
   • actionHistory.push("Inserted Image");
4. Inspect the top of the stack without removing it:
   
   
   • String currentTop = actionHistory.peek(); (Evaluates to "Inserted Image").
5. Perform an undo action by popping the top element:
   
   
   • String undoneAction = actionHistory.pop(); (Returns "Inserted Image" and removes it from the stack).
   • String nextUndoneAction = actionHistory.pop(); (Returns "Formatted Bold").
6. Evaluate remaining items: The top element is now "Typed 'Hello'".

Specialized Queue Implementations in the Java Collections Framework

While standard FIFO queues process items purely based on entry sequence, complex enterprise software frequently demands custom ordering or safe concurrent execution.

PriorityQueue for Element Ordering

java.util.PriorityQueue implements the Queue interface, but instead of arranging elements by arrival time, it orders them based on priority. Elements are retrieved in sorted order using either their natural ordering (via the Comparable interface) or a custom Comparator supplied during queue construction.

• Internal Structure: PriorityQueue is backed by a balanced binary min-heap.
• Operational Performance: Insertion (offer) and removal (poll) operations run in O(log n) time, while inspection (peek) operates in O(1) constant time.
• Use Cases: Dijkstra's shortest-path algorithm, Huffman coding data compression, real-time operating system job schedulers, and emergency response sorting systems.

For example, to process system alerts by urgency level:

Queue severityQueue = new PriorityQueue<>();

Inserting numbers 5, 1, and 3 into severityQueue results in poll() returning 1 first, followed by 3, and finally 5, regardless of insertion sequence.

Thread-Safe Queues in Concurrent Applications

Standard implementations like ArrayDeque, LinkedList, and PriorityQueue are not thread-safe. If multiple concurrent threads modify these structures without external synchronization, data corruption, broken structural pointers, or infinite loops can occur.

For multi-threaded environments, the Java Concurrency Utilities package (java.util.concurrent) provides highly optimized, thread-safe queue structures.

BlockingQueue Implementations

A BlockingQueue extends Queue to support operations that wait (block) for space to become available when inserting an element, or wait for elements to become available when retrieving them. This makes them ideal for the Producer-Consumer design pattern.

• ArrayBlockingQueue: A bounded blocking queue backed by a fixed-size array. Once created, its capacity cannot change.
• LinkedBlockingQueue: An optionally bounded queue backed by linked nodes. Offers higher throughput in producer-consumer scenarios because producers and consumers modify separate node references (head vs. tail locks).
• PriorityBlockingQueue: A thread-safe variant of PriorityQueue with blocking retrieval operations.

Concurrent Non-Blocking Queues

• ConcurrentLinkedQueue: An unbounded, thread-safe, non-blocking queue based on lock-free algorithms utilizing Compare-And-Swap (CAS) atomic primitives. It delivers high concurrency performance when thread blocking is undesirable.

Comparing Java Queue and Stack Implementations

Choosing the correct data structure implementation depends on structural constraints, thread-safety requirements, memory considerations, and algorithmic complexity targets.

Memory Allocation, Cache Locality, and Time Complexity

Understanding why ArrayDeque outperforms LinkedList in most benchmarks requires examining CPU architecture and memory management:

1. Cache Locality: ArrayDeque stores elements in contiguous memory blocks (arrays). Modern CPU architectures utilize multi-level hardware caching (L1, L2, L3). Sequential array memory locations are loaded into CPU cache lines simultaneously, resulting in fast read/write access. LinkedList allocates individual Node objects across fragmented heap locations, causing frequent CPU cache misses.
2. Garbage Collection Overhead: Every element inserted into a LinkedList requires instantiating a new Node wrapper object, generating significant heap allocation and GC pressure. ArrayDeque resizes its internal array infrequently (doubling capacity when full), minimizing allocation churn.
3. Amortized Time Complexity: Inserting into ArrayDeque is amortized O(1). While array expansion triggers an O(n) array copy operation occasionally, the frequency decreases exponentially as the collection grows, yielding rapid overall performance.

Best Practices and Common Pitfalls to Avoid

Writing robust, high-performance Java code requires adhering to core patterns and avoiding historical anti-patterns.

Avoiding Null Values in Deque and Queue Collections

Standard collections like ArrayList allow storing null values. However, inserting null into a Queue or Deque should strictly be avoided, and is explicitly prohibited by implementations like ArrayDeque.

The reason stems from operational ambiguity: methods like poll() and peek() return null to signal that the collection contains no elements. If a collection permitted storing literal null values, a return value of null could mean either "the queue is empty" or "the next element in the queue is literally null."

Handling Empty Collection Exceptions

When retrieving items from a queue or stack, ensure your code handles empty states cleanly to avoid unexpected runtime exceptions.

• For Stacks: Check isEmpty() prior to invoking pop(), or use peek() and check for null.
• For Queues: Prefer poll() over remove() when processing dynamic streams where empty conditions are expected operational states rather than system errors.

Selecting the Right Implementation for Single-Threaded vs. Multi-Threaded Code

• Single-Threaded Workflows: Use ArrayDeque as your standard choice for both Queue and Deque (Stack) implementations.
• Multi-Threaded Workflows: Never wrap non-thread-safe collections in manual synchronized blocks if concurrent performance matters. Instead, leverage specialized concurrent primitives such as ArrayBlockingQueue, LinkedBlockingQueue, or ConcurrentLinkedQueue.

Frequently Asked Questions

Why is ArrayDeque preferred over java.util.Stack for stack implementations?

ArrayDeque is faster, lighter, and properly encapsulated. Legacy java.util.Stack extends Vector, which introduces performance-degrading synchronization on every operation and exposes methods like get(index) that violate strict LIFO stack ordering by permitting mid-stack access. ArrayDeque provides an un-synchronized, high-performance stack implementation via the Deque interface.

What is the difference between offer() and add() in a Java Queue?

Both methods insert an element at the tail of a queue. However, when working with capacity-restricted queues, add() throws an IllegalStateException if the queue is full, whereas offer() safely returns false. offer() is generally preferred in production environments to handle capacity bounds gracefully.

Can LinkedList be used as both a Queue and a Stack in Java?

Yes. LinkedList implements the Deque interface, which extends Queue. Therefore, LinkedList contains methods for both FIFO queue operations (offer, poll) and LIFO stack operations (push, pop). However, ArrayDeque is generally preferred over LinkedList due to lower memory consumption and better CPU cache performance.

How do I reverse a Queue using a Stack in Java?

You can reverse a queue by transferring all of its elements into a stack and then popping them back into the queue. Because the stack processes elements in Last-In-First-Out order, popping the elements restores them to the queue in reverse order.

Are Java Queue implementations thread-safe by default?

No. Standard implementations such as ArrayDeque, LinkedList, and PriorityQueue are not thread-safe. If your application accesses a queue across multiple concurrent threads, use thread-safe collections from the java.util.concurrent package, such as ArrayBlockingQueue, LinkedBlockingQueue, or ConcurrentLinkedQueue.

Recommended Next Steps for Java Developers

To master queues and stacks in enterprise Java applications, transition these concepts into practice through the following actionable steps:

1. Refactor Legacy Code: Audit existing codebases to locate instances of java.util.Stack or java.util.Vector. Refactor them to use Deque stack = new ArrayDeque<>().
2. Benchmark Cache Performance: Build simple micro-benchmarks comparing ArrayDeque and LinkedList under high element throughput to observe how memory allocation affects garbage collection pause times.
3. Explore Concurrency Patterns: Build a producer-consumer application utilizing ArrayBlockingQueue to safely coordinate task distribution between worker threads without manual lock management.
4. Consult Official Documentation: Review the official Java API documentation for the java.util.Deque interface to familiarize yourself with double-ended queue operation pairs for both head and tail insertion.