Stacks and Queues in Java: A Brief Overview of Their Concepts and Implementations

What is a Stack?

A stack is a data structure that organizes elements in a Last In, First Out (LIFO) order. Imagine stacking plates: the last plate added to the top is the first one removed. This structure is ideal for problems where you need to reverse order or keep track of recent actions, such as undo operations in software.

What is a Queue?

A queue is a data structure that organizes elements in a First In, First Out (FIFO) order. Think of a line at a store where the first person in line is served first. Queues are suited for managing sequences of tasks or events where order matters, such as tasks in a job scheduling system.

Why Were Stack and Queue Created? Problems They Solve

Stack:

• Problem: Managing nested or sequential operations that need to be undone or reversed. Examples include undo operations, parsing expressions, and maintaining histories (e.g., browser back functionality).

• Solution: By following LIFO, a stack enables efficient last-in operations, allowing for quick access to the most recent action.

Queue:

• Problem: Ensuring fairness or sequence in processing tasks, where the first item to arrive should be processed first, such as scheduling jobs or managing customer service.

• Solution: By enforcing FIFO, a queue ensures tasks are processed in the exact order they arrive, making it ideal for task scheduling and order maintenance.

Stack Implementations in Java

1. Using java.util.Stack

Java provides a built-in Stack class, though it is a bit outdated and synchronized, which can make it slower in some scenarios.

import java.util.Stack;

public class StackExample {  
    public static void main(String[] args) {  
        Stack<Integer> stack = new Stack<>();  
        stack.push(10); // Add element  
        stack.push(20);  
        System.out.println(stack.peek()); // Access top element  
        stack.pop(); // Remove top element  
    }  
}

2. Using ArrayDeque for Stack

A more efficient alternative to Stack is ArrayDeque. It provides stack-like behavior but is faster due to fewer synchronization overheads.

import java.util.ArrayDeque;

public class ArrayDequeStack {  
    public static void main(String[] args) {  
        ArrayDeque<Integer> stack = new ArrayDeque<>();  
        stack.push(10);  
        stack.push(20);  
        System.out.println(stack.peek());  
        stack.pop();  
    }  
}

3. Custom Stack Implementation (Linked List)

Creating a custom stack can deepen your understanding of its operations. This stack uses a linked list for storage:

class Node {  
    int data;  
    Node next;  

    Node(int data) {  
        this.data = data;  
    }  
}

class LinkedListStack {  
    private Node top;  

    public void push(int value) {  
        Node newNode = new Node(value);  
        newNode.next = top;  
        top = newNode;  
    }  

    public int pop() {  
        if (top == null) throw new EmptyStackException();  
        int result = top.data;  
        top = top.next;  
        return result;  
    }  

    public int peek() {  
        if (top == null) throw new EmptyStackException();  
        return top.data;  
    }  

    public boolean isEmpty() {  
        return top == null;  
    }  
}

Queue Implementations in Java

1. Using LinkedList as Queue

Java’s LinkedList implements the Queue interface, making it a flexible option for queue functionality.

import java.util.LinkedList;  
import java.util.Queue;

public class LinkedListQueue {  
    public static void main(String[] args) {  
        Queue<Integer> queue = new LinkedList<>();  
        queue.offer(1); // Add element  
        queue.offer(2);  
        System.out.println(queue.peek()); // Access front element  
        queue.poll(); // Remove front element  
    }  
}

2. Using ArrayDeque as Queue

ArrayDeque provides an efficient queue implementation that performs faster than LinkedList for stack and queue operations.

import java.util.ArrayDeque;

public class ArrayDequeQueue {  
    public static void main(String[] args) {  
        ArrayDeque<Integer> queue = new ArrayDeque<>();  
        queue.offer(1);  
        queue.offer(2);  
        System.out.println(queue.peek());  
        queue.poll();  
    }  
}

3. Custom Queue Implementation (Circular Array)

A circular array queue handles fixed-size queues more efficiently by reusing empty space. It’s commonly used in real-time systems.

class CircularQueue {  
    private int[] data;  
    private int front, rear, size;

    public CircularQueue(int capacity) {  
        data = new int[capacity];  
        front = rear = size = 0;  
    }  

    public boolean enqueue(int value) {  
        if (size == data.length) return false; // Queue is full  
        data[rear] = value;  
        rear = (rear + 1) % data.length;  
        size++;  
        return true;  
    }  

    public int dequeue() {  
        if (size == 0) throw new NoSuchElementException("Queue is empty");  
        int result = data[front];  
        front = (front + 1) % data.length;  
        size--;  
        return result;  
    }  

    public int peek() {  
        if (size == 0) throw new NoSuchElementException("Queue is empty");  
        return data[front];  
    }  

    public boolean isEmpty() {  
        return size == 0;  
    }  
}

CRUD Operations Examples

Stack CRUD Operations

// import LinkedListStack

class LinkedListStackMain {  
    public static void main(String[] args) {  
        LinkedListStack stack = new LinkedListStack();  
        stack.push(1); // Create  
        stack.push(2);  
        int top = stack.peek(); // Read  
        stack.pop(); // Delete  
        boolean isEmpty = stack.isEmpty();  
    }  
}

Queue CRUD Operations

// import CircularQueue

class CircularQueueMain {  
    public static void main(String[] args) {  
        CircularQueue queue = new CircularQueue(3);  
        queue.enqueue(10); // Create  
        queue.enqueue(20);  
        int front = queue.peek(); // Read  
        queue.dequeue(); // Delete  
        boolean isEmpty = queue.isEmpty();  
    }  
}

5. Key Points

Stack:

• Operations: push (add), pop (remove), peek (view top).

• Order: LIFO, suitable for managing histories and recursive tasks.

• Implementations: Stack, ArrayDeque, and a custom linked list.

Queue:

• Operations: enqueue (add), dequeue (remove), peek (view front).

• Order: FIFO, ideal for task scheduling and order-sensitive processes.

• Implementations: LinkedList, ArrayDeque, and custom circular array.

Summary

Stacks and queues are foundational data structures used across programming to solve real-world problems involving order, sequence, and control flow. A stack is ideal for reversing operations, managing nested tasks, and tracking recent actions, while a queue is perfect for processing tasks in the order they arrive.

Java provides various ways to implement stacks and queues, allowing developers to select the best option for their specific requirements. Understanding these implementations will enhance your ability to manage data effectively and choose optimal solutions for real-world challenges.

That’s all for the moment! I truly hope this article helped you gain a deeper understanding of the topic you were looking for.

Thank you 🙏 for taking the time to read this post. I appreciate your engagement with my content. If you enjoyed this content, I’d really appreciate your support! Please like ❤️, share ✉, and subscribe to my blog for more helpful insights.

Stay tuned for more updates. 🔖 Happy coding!