Efficient Stack Operations with Java’s Deque Interface

In this blog post, we’ll explore how to implement a stack using Java’s Deque interface. Stacks are a fundamental data structure in computer science, and understanding how to implement them using different underlying structures can deepen your understanding of both stacks and those structures. Here, we’ll use a LinkedList as our Deque implementation.

What is a Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Common operations for a stack include:

• Push: Add an element to the top of the stack.
• Pop: Remove the top element from the stack.
• Peek: View the top element without removing it.
• IsEmpty: Check if the stack is empty.

Why Use Deque?

The Deque (Double-Ended Queue) interface in Java provides methods to add and remove elements from both ends of the queue. This makes it a versatile choice for implementing a stack, as it allows us to efficiently perform stack operations.

The Code

import java.util.LinkedList;
import java.util.Deque;

public class StackUsingDeque {

    static class Stack {
        static Deque<Integer> stack = new LinkedList<>();

        public static boolean isEmpty(){
            return stack.isEmpty();
        }

        // add method using deque
        public static void push(int data) {
            stack.addLast(data);
        }

        // remove method using deque
        public static int pop() {
            if (stack.isEmpty()) {
                System.out.println("The deque is Empty");
                return -1;
            }
            int last = stack.removeLast();
            return last;
        }

        // peek method using deque
        public static int peek() {
            if (stack.isEmpty()) {
                System.out.println("The deque is Empty");
                return -1;
            }
            return stack.getLast();
        }
    }

    public static void main(String args[]){
        Stack s = new Stack();

        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);

        while (!s.isEmpty()) {
           System.out.println( s.pop());
        }
    }
}

Explanation

1. Class Definition: We define a static inner class Stack which contains our Deque implementation.
2. isEmpty Method: This method checks if the stack is empty by using the isEmpty method of Deque.
3. Push Method: Adds an element to the end of the deque using addLast.
4. Pop Method: Removes and returns the last element of the deque using removeLast. If the deque is empty, it prints a message and returns -1.
5. Peek Method: Returns the last element of the deque without removing it using getLast. If the deque is empty, it prints a message and returns -1.
6. Main Method: Demonstrates the stack operations by pushing elements onto the stack and then popping them off while printing each element.:

1. isEmpty()

• Time Complexity: O(1) - This method simply checks if the deque is empty, which is a constant-time operation.
• Space Complexity: O(1) - No additional space is used.

2. push(int data)

• Time Complexity: O(1) - Adding an element to the end of the deque is a constant-time operation¹.
• Space Complexity: O(1) - No extra space is used beyond the space required to store the new element.

3. pop()

• Time Complexity: O(1) - Removing the last element from the deque is a constant-time operation¹.
• Space Complexity: O(1) - No extra space is used.

4. peek()

• Time Complexity: O(1) - Accessing the last element of the deque is a constant-time operation¹.
• Space Complexity: O(1) - No extra space is used.

Summary

All the methods (isEmpty(), push(int data), pop(), and peek()) in this implementation have a time complexity of O(1) and a space complexity of O(1). This makes the stack operations very efficient when using a Deque as the underlying data structure.

Conclusion

Using Deque to implement a stack in Java is both efficient and straightforward. This implementation leverages the flexibility of Deque to provide all the necessary stack operations. Understanding this approach can help you appreciate the versatility of Java’s collection framework and improve your problem-solving skills in data structure implementation.

Feel free to experiment with the code and modify it to suit your needs. Happy coding! 🚀

---

If you have any questions or need further clarification, feel free to leave a comment below!