Stack and Queue in Java

Introduction

Stacks and queues are linear data structures that follow a particular order to add or remove entities.

In this tutorial, you will be introduced to stack and queue in Java. We will cover the critical concepts of stack and queue in Java, highlighting their practical application, implementations, functionalities, and how to develop stack and queue data structures using classes and objects.

Overview

Java uses stacks and queues as its fundamental data structures, but they can also be called classes. Both stacks and queues are linear data structures because elements are stored and accessed sequentially.

Understanding their principles and differences is crucial for effective programming and tackling coding interview questions. Let’s learn more about Java stacks and queues and look at Java stack and queue examples.

What Is a Stack?

A stack in Java is a basic data structure that adheres to the Last-In-First-Out (LIFO) concept. It may be pictured as a stack of things, with the most recent item added being the initial one to be taken away. By allowing actions like push (including an element to the top) and pop (by eliminating and restoring the top element), stacks offer an effective approach to organizing and altering data

In Java, stacks are represented by the Stack class, a subclass of the Vector class.

Example:

import java.util.Stack;
public class StackExample {
    public static void main(String[] args) {
        // Create a stack
        Stack<Integer> stack = new Stack<>();
        // Push an element onto the stack
        int element = 42;
        stack.push(element);
        // Pop the top element from the stack
        int topElement = stack.pop();
        System.out.println("Popped element: " + topElement);
        // Peek at the top element of the stack
        int peekElement = stack.peek();
        System.out.println("Top element: " + peekElement);
        // Check if the stack is empty
        boolean isEmpty = stack.isEmpty();
        System.out.println("Is stack empty? " + isEmpty);
        // Get the size of the stack
        int size = stack.size();
        System.out.println("Size of the stack: " + size);
    }
}

In this example, we first create a stack by declaring a variable of type Stack and use the new keyword to create an instance of the Stack class. You can replace DataType with the desired data type for the elements stored in the stack.

Then, we push an element onto the stack using the push() method to add an element to the top. We are using Integer as the data type for the stack. We set the element to 42 and push it onto the stack.

Finally, we use the pop() method to remove and retrieve the top element from the stack. The removed element is returned by this method, and the result is printed to the console.

Methods in Stack Class

Several methods are available to modify and access stack elements in the Java Stack class. Among the most common methods are:

1. push(element): Adds a new element to the stack's top.

2. pop(): Removes and returns the topmost element in the stack.

3. peek(): Returns the topmost stack element without deleting it.

4. empty(): Returns a boolean result that determines if the stack is empty.

5. size(): Gives the stack's element count.

Applications of Stack in Java

• Stacks check for balanced parentheses, match XML and HTML tags, and validate code syntax.
• A stack allows the evaluation of expressions, especially infix, postfix, and prefix expressions. A stack can convert infix expressions to postfix or prefix forms.
• Stacks are frequently used by backtracking algorithms, including depth-first search (DFS), to retain track of visited nodes and return to earlier stages during exploration.

Here is a real-world application (back-button functionality) of Java stacks:

In this example, the BrowserBackButton class represents the functionality of a browser's back button. The pageStack stack stores the URLs of visited pages. The visitPage() method adds a new page URL to the stack when a page is visited. The goBack() method pops the top URL from the stack and simulates navigating back to the previous page. If the stack is empty, it indicates no pages left to go back to.

In the main() method, we create an instance of BrowserBackButton and simulate visiting different web pages. Then, we call the goBack() method multiple times to simulate pressing the back button and navigating to previous pages. Finally, we try to go back when there are no more pages in the history, which shows the appropriate message.

import java.util.Stack;
public class BrowserBackButton {
    private Stack<String> pageStack;
    public BrowserBackButton() {
        pageStack = new Stack<>();
    }
    public void visitPage(String url) {
        // Add the URL to the stack when a new page is visited
        pageStack.push(url);
        System.out.println("Visited page: " + url);
    }
    public void goBack() {
        if (!pageStack.isEmpty()) {
            String previousPage = pageStack.pop();
            System.out.println("Navigating back to: " + previousPage);
        } else {
            System.out.println("Cannot go back. No pages in history.");
        }
    }
    public static void main(String[] args) {
        BrowserBackButton browser = new BrowserBackButton();
        // Visit different web pages
        browser.visitPage("https://www.example.com");
        browser.visitPage("https://www.example.com/page1");
        browser.visitPage("https://www.example.com/page2");
        // Press the back button to navigate back
        browser.goBack();
        browser.goBack();
        browser.goBack();
        browser.goBack(); // Trying to go back when no pages are left
    }
}

What Is the Queue?

A queue is a basic data structure representing a group of elements in a predetermined sequence. It adheres to the First-In-First-Out (FIFO) principle, which states that the first element added is also the first one taken out. And this is where the difference between stack and queue (in data structure terms) comes into the picture — while queue follows FIFO, stack follows LIFO data structure type.

In Java, we can use the Queue interface to represent a queue. Several classes implement the Queue interface in the Java Collections Framework, such as LinkedList and ArrayDeque.

Example:

import java.util.Queue;
import java.util.LinkedList;
public class QueueExample {
    public static void main(String[] args) {
        // Create a queue
        Queue<Integer> queue = new LinkedList<>();
        // Add an element to the queue
        int element = 42;
        queue.add(element);
        // Remove the element from the front of the queue
        int frontElement = queue.remove();
        System.out.println("Removed element: " + frontElement);
        // Peek at the element from the front of the queue
        int peekElement = queue.peek();
        System.out.println("Front element: " + peekElement);
        // Check if the queue is empty
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is queue empty? " + isEmpty);
        // Get the size of the queue
        int size = queue.size();
        System.out.println("Size of the queue: " + size);
    }
}

In this example, we first create a queue by declaring a variable of type Queue and use a class that implements the Queue interface. Then, we will use Integer as the data type for the queue. We set the element to the value 42 and add it to the queue using the add() method.

Finally, we will remove the element from the front of the queue using the remove() method to remove and retrieve the element from the front. The removed element is returned by this method, and we print the results to the console.

Methods of Queue in Java

Java's Queue interface offers several ways to interact with queues. Here are a few of the common methods:

1. add(element): Adds a piece to the rear of the queue.

2. remove(): Removes and returns the element at the front of the queue.

3. isEmpty(): Checks if the queue is empty and returns a boolean value.

4. size(): Returns the number of elements in the queue.

Applications of Queue in Java

1. Task Scheduling: Tasks are scheduled and managed systematically using queues.

2. Breadth-First Search (BFS): Implementing BFS algorithms for traversing graphs or trees requires queues.

3. Multi-threaded Synchronization: Thread-safe access is made possible through queues, which aid in resource sharing and synchronization across several threads.

Here is a real-world application (task scheduling) of Java queues:

In this example, the TaskScheduler class represents a task scheduling system. The taskQueue queue stores the incoming tasks. The enqueueTask() method adds a new task to the end of the queue. The processTasks() method continuously dequeues and processes tasks from the front of the queue until the queue becomes empty. Each task is simulated by a delay of 1 second.

In the main() method, we create an instance of TaskScheduler and enqueue multiple tasks. Then, we call the processTasks() method to start processing the tasks in the order they were enqueued.

import java.util.Queue;
import java.util.LinkedList;
public class TaskScheduler {
    private Queue<String> taskQueue;
    public TaskScheduler() {
        taskQueue = new LinkedList<>();
    }
    public void enqueueTask(String task) {
        // Enqueue a new task to the end of the queue
        taskQueue.add(task);
        System.out.println("Enqueued task: " + task);
    }
    public void processTasks() {
        while (!taskQueue.isEmpty()) {
            String task = taskQueue.remove();
            System.out.println("Processing task: " + task);
            // Simulate some processing time
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println("All tasks processed.");
    }
    public static void main(String[] args) {
        TaskScheduler scheduler = new TaskScheduler();
        // Enqueue tasks
        scheduler.enqueueTask("Task 1");
        scheduler.enqueueTask("Task 2");
        scheduler.enqueueTask("Task 3");
        // Process tasks in the order they were enqueued
        scheduler.processTasks();
    }
}

Types of Queues in Java

In Java, queues can be implemented using the java.util.Queue interface or its subclasses. Here are some common types of queues:

1. LinkedList Queue: It provides efficient insertion and removal of components at both ends of the queue

2. ArrayDeque Queue: It provides dynamic array-based operations for adding and removing elements.

3. Priority Queue: It orders elements based on their natural ordering or a custom comparator, allowing for removal based on priority.

4. Blocking Queue: Provides additional blocking and synchronization operations for thread safety.

5. Synchronous Queue: It enables simultaneous element passing by acting as a meeting point between two threads.

Similarities Between Stack and Queue in Java

Java Stack and Queue Difference

Conclusion

Stacks and queues are essential Java data structures with specific functions. Counting function calls, doing undos and redos, and evaluating expressions are popular uses for stacks. Queues, on the other hand, are helpful for sequential data management, message passing, breadth-first search, and job scheduling.

By understanding its features, applications, and implementations, you can use stack and queue in Java to arrange and modify data methodically and efficiently.

FAQs

1. Are stacks and queues thread-safe in Java?

There are thread-safe substitutes for Java's standard implementations of stacks and queues, such as java.util.Stack and java.util.LinkedList, which are not thread-safe by default.

2. Are there any limitations to the size of a stack or a queue in Java?

In Java, the size of a stack or queue is normally constrained by the amount of memory available on the machine, although certain particular implementations could have additional size restrictions.

3. How do I choose between using a stack or a queue in Java?

Java allows you to use either a stack or a queue depending on the needs of your application and whether you need to retain the order of insertion (queue) or prioritize the order of the items (stack).

Take the Free Java Quiz & See Your Rank!

Take Quiz