Stacks and Queues in Java

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.

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.

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.

Sign up

Join the 1M+ learners on CodeSignal

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