Stacks and Queues in Java

Welcome to an exciting exploration of two fundamental data structures in Java: Stacks and Queues! These data structures organize and manage data effectively. Specifically, stacks are comparable to a pile of plates, while queues are akin to standing in line. Let's dive in!

Stacks: Last In, First Out (LIFO)

A stack follows the "Last In, First Out" or LIFO principle. Imagine a stack of plates where the last plate added is the first one to be removed. In Java, we can use ArrayDeque<E> or LinkedList<E> to implement a stack, with push for inserting (pushing) and pop for removing (popping, returning the element that is removed). Push (Insertion): Adds an element to the top of the stack. This makes the newly added element the last-in, which is the first to be removed when needed. Pop (Removal): Removes and returns the element at the top of the stack, following the Last In, First Out (LIFO) principle. Let's explore this with an example of a stack of plates. Java import java.util.ArrayDeque; import java.util.Deque; class StackOfPlates {private Deque<String> stack; public StackOfPlates() {stack = new ArrayDeque<>();} // Insert a plate at the top of the stack public void addPlate(String plate) {stack.push(plate);} // Remove the top plate from the stack public String removePlate() {if (stack.isEmpty()) {return "No plates left to remove!";} return stack.pop();}} public class Solution {public static void main(String[] args) {StackOfPlates plates = new StackOfPlates(); plates.addPlate("Plate"); // Pushing a plate plates.addPlate("Another Plate"); // Pushing another plate // Let's remove a plate; it should be the last one we added. System.out.println("Removed: " + plates.removePlate()); // Outputs: Removed: Another Plate}} The last plate added was removed first, demonstrating the LIFO property of a stack.

Queues: First In, First Out (FIFO)

A queue operates on the "First In, First Out" or FIFO principle, similar to waiting in line. In Java, we can implement a queue using the Queue<E> interface with a LinkedList or ArrayDeque, where add (enqueue) inserts at the end and remove or poll (dequeue) removes from the front. Add (Enqueue): Adds an element to the end of the queue, following the First In, First Out (FIFO) order. Poll (Dequeue): Removes and returns the element at the front of the queue. This is the oldest element, maintaining the FIFO order. Let's examine this with a queue of people. Java import java.util.LinkedList; import java.util.Queue; class QueueOfPeople {private Queue<String> queue; public QueueOfPeople() {queue = new LinkedList<>();} // Add a person to the end of the queue public void enqueuePerson(String person) {queue.add(person);} // Remove the first person from the queue (who has been waiting the longest) public String dequeuePerson() {if (queue.isEmpty()) {return "No people left to dequeue!";} return queue.poll();}} public class Solution {public static void main(String[] args) {QueueOfPeople people = new QueueOfPeople(); people.enqueuePerson("Person 1"); // Person 1 enters the queue people.enqueuePerson("Person 2"); // Person 2 arrives after Person 1 // Who's next in line? It must be Person 1! System.out.println("Removed: " + people.dequeuePerson()); // Outputs: Removed: Person 1}} Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Mastering Stack and Queue Operations with a Class

Stacks efficiently handle ordered data, much like a web browser's history. Queues are optimal when the order of arrival is essential, such as in a store queue.

Let's illustrate using a text editor that features an Undo mechanism (a Stack) and a Print Queue.

Undo Mechanism (Stack):

The makeChange(String action) method pushes each action onto the stack, simulating the latest edit. When an undo is performed using undoChange(), it removes this most recent change from the stack, just as pressing "Undo" would revert the last action. The stack's LIFO property ensures that the latest change is always the first undone.

Print Queue (Queue):

The addToPrint(String doc) method enqueues documents for printing, adding each one to the end of the queue. When printDoc() is called, it dequeues the document at the front, following the order of addition. This FIFO process simulates a print queue, where the earliest document in line is printed first.

Java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class TextEditor {
    private Deque<String> stack;
    private Queue<String> queue;

    public TextEditor() {
        stack = new ArrayDeque<>();
        queue = new LinkedList<>();
    }

    // Make a change (e.g., edit text, insert image, change font)
    public void makeChange(String action) {
        stack.push(action);  // Add to the stack of actions
    }

    // Undo the most recent change
    public String undoChange() {
        if (stack.isEmpty()) {
            return "No changes to undo!";
        }
        return stack.pop();  // Remove the last action from the stack
    }

    // Add a document to the queue for printing
    public void addToPrint(String doc) {
        queue.add(doc);
    }

    // Print the document that has been waiting the longest
    public String printDoc() {
        if (queue.isEmpty()) {
            return "No documents in print queue!";
        }
        return queue.poll();  // Remove the first document from the queue
    }
}

public class Solution {
    public static void main(String[] args) {
        TextEditor editor = new TextEditor();
        editor.makeChange("Changed font size");  // Make a change
        editor.makeChange("Inserted image");  // Make another change
        // Let's undo a change. It should be the last change we made.
        System.out.println("Undo: " + editor.undoChange());  // Undo: Inserted image

        editor.addToPrint("Proposal.docx");  // Queue a document for printing
        editor.addToPrint("Report.xlsx");  // Queue another document
        // Let's print a document. It should be the document that has been waiting the longest.
        System.out.println("Print: " + editor.printDoc());  // Print: Proposal.docx
    }
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

class TextEditor {
    private Deque<String> stack;
    private Queue<String> queue;

    public TextEditor() {
        stack = new ArrayDeque<>();
        queue = new LinkedList<>();
    }

    // Make a change (e.g., edit text, insert image, change font)
    public void makeChange(String action) {
        stack.push(action);  // Add to the stack of actions
    }

    // Undo the most recent change
    public String undoChange() {
        if (stack.isEmpty()) {
            return "No changes to undo!";
        }
        return stack.pop();  // Remove the last action from the stack
    }

    // Add a document to the queue for printing
    public void addToPrint(String doc) {
        queue.add(doc);
    }

    // Print the document that has been waiting the longest
    public String printDoc() {
        if (queue.isEmpty()) {
            return "No documents in print queue!";
        }
        return queue.poll();  // Remove the first document from the queue
    }
}

public class Solution {
    public static void main(String[] args) {
        TextEditor editor = new TextEditor();
        editor.makeChange("Changed font size");  // Make a change
        editor.makeChange("Inserted image");  // Make another change
        // Let's undo a change. It should be the last change we made.
        System.out.println("Undo: " + editor.undoChange());  // Undo: Inserted image

        editor.addToPrint("Proposal.docx");  // Queue a document for printing
        editor.addToPrint("Report.xlsx");  // Queue another document
        // Let's print a document. It should be the document that has been waiting the longest.
        System.out.println("Print: " + editor.printDoc());  // Print: Proposal.docx
    }
}

This code reintroduces the concepts of a Stack (Undo feature) and Queue (Print queue) in practical scenarios.