Implementing Stacks and Queues with Java's Deque

1. The Deque Interface: A Double-Ended Queue

The word Deque (pronounced "deck") is short for "Double-Ended Queue". As the name implies, it's a queue where you can add or remove elements from both the front (head) and the back (tail). This versatility is what makes it so powerful—it can behave like a stack, a queue, or a combination of both.

To start, let's get a high-level overview of what the Deque interface is and how it enables both stack and queue behaviors.

The Deque is an interface within the Java Collections Framework. Understanding its place in the hierarchy is key. It extends the Queue interface, which in turn extends the Collection interface.

Since Deque is an interface, you can't instantiate it directly. You must use a class that implements it. The two most common implementations are:

1. ArrayDeque: Implements the Deque using a resizable array. This is generally the more efficient choice for both stack and queue operations.
2. LinkedList: Implements the Deque using a doubly linked list. You're already familiar with the principles of linked lists from our last lesson.

For most use cases, ArrayDeque is the preferred implementation unless you specifically need the features of a LinkedList.

2. Implementing a Stack (LIFO) with Deque

A stack follows the Last-In, First-Out (LIFO) principle. Think of a stack of plates: the last plate you put on top is the first one you take off.

The Deque interface provides specific methods that map directly to stack operations:

• push(element): Adds an element to the front (head) of the deque.
• pop(): Removes and returns the element from the front of the deque.
• peek(): Returns, but does not remove, the element at the front of the deque.

You might wonder, "Why not just use Java's Stack class?" This is a critical point for a modern Java developer. The original java.util.Stack class is now considered a legacy class and its use is discouraged. The Deque interface and its implementations are superior for several reasons.

To summarize the key points from the article:

1. Flexibility: Deque is an interface, while Stack is a class that extends Vector. Since Java doesn't support multiple class inheritance, using an interface provides much more design freedom.
2. Performance: Stack methods are synchronized, which adds overhead for thread safety. If you don't need thread safety (which is common), an ArrayDeque will offer significantly better performance.

Let's see it in action. Here’s how you would use ArrayDeque as a stack:

import java.util.Deque;
import java.util.ArrayDeque;

public class StackExample {
    public static void main(String[] args) {
        // We program to the interface (Deque) but instantiate the concrete class (ArrayDeque)
        Deque<String> stack = new ArrayDeque<>();

        // Push elements onto the stack
        stack.push("First In");
        stack.push("Second In");
        stack.push("Third In (Last In)");

        System.out.println("Current stack: " + stack);

        // Peek at the top element
        System.out.println("Top element is: " + stack.peek());

        // Pop elements off the stack (LIFO)
        System.out.println("Popped: " + stack.pop()); // Removes "Third In"
        System.out.println("Popped: " + stack.pop()); // Removes "Second In"

        System.out.println("Final stack: " + stack);
    }
}

Output:

Current stack: [Third In (Last In), Second In, First In]
Top element is: Third In (Last In)
Popped: Third In (Last In)
Popped: Second In
Final stack: [First In]

Internally, the ArrayDeque manages head and tail pointers on its underlying array. This is analogous to how you managed the head pointer in your linked list, but it's done much more efficiently.

3. Implementing a Queue (FIFO) with Deque

A queue follows the First-In, First-Out (FIFO) principle. This is like a checkout line at a store: the first person to get in line is the first person to be served.

Deque also provides methods that map perfectly to queue operations:

• offer(element) or add(element): Adds an element to the back (tail) of the deque.
• poll() or remove(): Removes and returns the element from the front (head) of the deque.
• peek(): Returns, but does not remove, the element at the front of the deque.

A key distinction in the Java Collections API is how methods handle failure cases (like trying to remove from an empty collection).

• Methods like add, remove, and element will throw an exception.
• Methods like offer, poll, and peek will return a special value (false or null).

In most application code, it's preferable to use the methods that return special values (offer, poll, peek) as it's generally cleaner to check for null than to handle exceptions for normal control flow.

Here's an example of using ArrayDeque as a queue:

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Queue; // Can also use the Queue interface

public class QueueExample {
    public static void main(String[] args) {
        // Using the Queue interface is also common here
        Queue<String> queue = new ArrayDeque<>();

        // Add elements to the queue (FIFO)
        queue.offer("First In");
        queue.offer("Second In");
        queue.offer("Third In");

        System.out.println("Current queue: " + queue);

        // Peek at the front element
        System.out.println("Front element is: " + queue.peek());

        // Poll elements from the queue
        System.out.println("Polled: " + queue.poll()); // Removes "First In"
        System.out.println("Polled: " + queue.poll()); // Removes "Second In"

        System.out.println("Final queue: " + queue);
    }
}

Output:

Current queue: [First In, Second In, Third In]
Front element is: First In
Polled: First In
Polled: Second In
Final queue: [Third In]

As you might guess, the internal mechanics for queue operations involve moving both the head and tail pointers.

4. Practical Application: Validating Parentheses

To tie this all together, let's look at a classic problem from your DSA practice: validating parentheses. Given a string containing just the characters (, ), {, }, [ and ], we need to determine if the input string is valid. A string is valid if open brackets are closed by the same type of bracket and in the correct order.

This is a perfect use case for a stack. The algorithm is:

1. Iterate through each character of the string.
2. If the character is an opening bracket ((, {, [), push it onto the stack.
3. If the character is a closing bracket (), }, ]), check two things:
   • Is the stack empty? If so, there's no matching opening bracket, so the string is invalid.
   • If the stack is not empty, pop the top element. Does it match the current closing bracket? If not, the string is invalid.
4. After the loop finishes, if the stack is empty, all brackets were correctly matched and closed. If it's not empty, there are unclosed opening brackets.

The image below shows a complete Java implementation of this logic using a Deque as a stack.

Notice how the code uses addFirst as a push operation and getFirst/removeFirst to implement peek and pop. This is a powerful, real-world example of applying the concepts we've discussed today.

Conclusion

In this lesson, you've learned how to leverage Java's versatile Deque interface to implement both stacks and queues. This is a significant step up from building structures from scratch, allowing you to use robust, high-performance components from the Java Collections Framework.

Key Takeaways:

• Deque stands for "double-ended queue" and allows additions/removals from both ends.
• It is the modern, preferred way to implement stacks (LIFO) and queues (FIFO) in Java.
• ArrayDeque is the go-to implementation for its performance, while LinkedList is an alternative.
• For stacks, use push(), pop(), and peek().
• For queues, use offer(), poll(), and peek().
• The legacy Stack class should be avoided in new code due to design and performance limitations.

In our next lesson, we'll continue our exploration of core data structures by diving into HashMap. You'll learn how it stores key-value pairs and how to use it to solve common problems like frequency counting and building quick lookups.