How do you implement a basic data structure, such as a stack or a queue, in Java?
Understanding and implementing fundamental data structures like stacks and queues is crucial for any Java developer. These structures organize data in specific ways (LIFO for Stack, FIFO for Queue) and underpin many algorithms and applications. In Java, you can implement them from scratch using arrays or linked lists, or leverage highly optimized built-in collection classes.
Implementing a Custom Stack (LIFO)
A stack is a Last-In, First-Out (LIFO) data structure. Imagine a pile of plates: you can only add a plate to the top, and you can only remove the top-most plate. The primary operations are:
- push(element): Adds an element to the top of the stack.
- pop(): Removes and returns the top element from the stack. Throws an exception if the stack is empty.
- peek(): Returns the top element without removing it. Throws an exception if the stack is empty.
- isEmpty(): Checks if the stack is empty.
We can implement a simple custom stack using an ArrayList internally to manage the elements.
import java.util.ArrayList;
import java.util.EmptyStackException;
public class MyStack<T> {
private ArrayList<T> elements;
public MyStack() {
elements = new ArrayList<>();
}
public void push(T item) {
elements.add(item);
}
public T pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return elements.remove(elements.size() - 1);
}
public T peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return elements.get(elements.size() - 1);
}
public boolean isEmpty() {
return elements.isEmpty();
}
public int size() {
return elements.size();
}
}
In this implementation, push adds to the end of the ArrayList, and pop and peek retrieve from the end, perfectly simulating LIFO behavior.
public class StackDemo {
public static void main(String[] args) {
MyStack<Integer> stack = new MyStack<>();
stack.push(10);
stack.push(20);
stack.push(30);
System.out.println("Stack size: " + stack.size()); // Output: 3
System.out.println("Top element: " + stack.peek()); // Output: 30
System.out.println("Popped: " + stack.pop()); // Output: 30
System.out.println("Popped: " + stack.pop()); // Output: 20
System.out.println("Is stack empty? " + stack.isEmpty()); // Output: false
stack.push(40);
System.out.println("Top element: " + stack.peek()); // Output: 40
System.out.println("Popped: " + stack.pop()); // Output: 40
System.out.println("Popped: " + stack.pop()); // Output: 10
System.out.println("Is stack empty? " + stack.isEmpty()); // Output: true
}
}
Implementing a Custom Queue (FIFO)
A queue is a First-In, First-Out (FIFO) data structure. Like a line of people waiting, the first person in line is the first to be served. The primary operations are:
- enqueue(element): Adds an element to the rear of the queue.
- dequeue(): Removes and returns the front element from the queue. Returns null or throws an exception if the queue is empty.
- peek(): Returns the front element without removing it. Returns null or throws an exception if the queue is empty.
- isEmpty(): Checks if the queue is empty.
A LinkedList is often a good choice for implementing a custom queue because it allows efficient additions to the rear and removals from the front without costly element shifting.
import java.util.LinkedList;
import java.util.NoSuchElementException;
public class MyQueue<T> {
private LinkedList<T> elements;
public MyQueue() {
elements = new LinkedList<>();
}
public void enqueue(T item) {
elements.addLast(item); // Add to the end (rear)
}
public T dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return elements.removeFirst(); // Remove from the beginning (front)
}
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return elements.getFirst(); // Get from the beginning without removing
}
public boolean isEmpty() {
return elements.isEmpty();
}
public int size() {
return elements.size();
}
}
Here, enqueue uses addLast() and dequeue/peek use removeFirst()/getFirst() to maintain the FIFO order efficiently.
public class QueueDemo {
public static void main(String[] args) {
MyQueue<String> queue = new MyQueue<>();
queue.enqueue("Alice");
queue.enqueue("Bob");
queue.enqueue("Charlie");
System.out.println("Queue size: " + queue.size()); // Output: 3
System.out.println("Front element: " + queue.peek()); // Output: Alice
System.out.println("Dequeued: " + queue.dequeue()); // Output: Alice
System.out.println("Dequeued: " + queue.dequeue()); // Output: Bob
System.out.println("Is queue empty? " + queue.isEmpty()); // Output: false
queue.enqueue("David");
System.out.println("Front element: " + queue.peek()); // Output: Charlie
System.out.println("Dequeued: " + queue.dequeue()); // Output: Charlie
System.out.println("Dequeued: " + queue.dequeue()); // Output: David
System.out.println("Is queue empty? " + queue.isEmpty()); // Output: true
}
}
Using Java's Built-in Collections (Recommended)
While implementing custom data structures is great for learning, Java's java.util package provides highly optimized and robust implementations for common data structures. For stacks and queues, the Deque interface (Double-Ended Queue) and its implementation ArrayDeque are generally preferred.
Stack using ArrayDeque
For stack functionality, java.util.ArrayDeque is recommended over the legacy java.util.Stack class because ArrayDeque is generally faster and doesn't suffer from synchronization overhead when not needed (unlike Vector, which Stack extends). ArrayDeque implements Deque, which provides push(), pop(), and peek() methods.
import java.util.ArrayDeque;
import java.util.Deque;
public class BuiltinStackDemo {
public static void main(String[] args) {
Deque<String> stack = new ArrayDeque<>();
stack.push("Task 1");
stack.push("Task 2");
stack.push("Task 3");
System.out.println("Stack: " + stack); // Output: [Task 3, Task 2, Task 1]
System.out.println("Top element: " + stack.peek()); // Output: Task 3
System.out.println("Popped: " + stack.pop()); // Output: Task 3
System.out.println("Stack after pop: " + stack); // Output: [Task 2, Task 1]
System.out.println("Is stack empty? " + stack.isEmpty()); // Output: false
}
}
Queue using ArrayDeque or LinkedList
For queue functionality, the java.util.Queue interface is used. Common implementations are java.util.LinkedList and java.util.ArrayDeque. Both are good choices, with ArrayDeque often being slightly more performant for typical queue operations because it's backed by an array and avoids the overhead of linked nodes.
- offer(element): Adds an element to the rear of the queue (returns true/false).
- poll(): Removes and returns the front element (returns null if empty).
- peek(): Returns the front element without removing (returns null if empty).
import java.util.ArrayDeque;
import java.util.Queue;
public class BuiltinQueueDemo {
public static void main(String[] args) {
Queue<String> queue = new ArrayDeque<>(); // Or new LinkedList<>()
queue.offer("Order 1");
queue.offer("Order 2");
queue.offer("Order 3");
System.out.println("Queue: " + queue); // Output: [Order 1, Order 2, Order 3]
System.out.println("Front element: " + queue.peek()); // Output: Order 1
System.out.println("Polled: " + queue.poll()); // Output: Order 1
System.out.println("Queue after poll: " + queue); // Output: [Order 2, Order 3]
System.out.println("Is queue empty? " + queue.isEmpty()); // Output: false
}
}
In summary, while implementing custom stacks and queues helps solidify understanding of their underlying mechanisms, for production-grade Java applications, ArrayDeque is the preferred and most efficient choice for both stack and queue operations due to its flexibility and performance characteristics.