Stack and Queue in Java
Subject: Data Structures and Algorithms · Language: Java · Level: intermediate · 6 min read
Learn LIFO and FIFO with Stack, ArrayDeque, Queue operations, and where they are used in DSA.
Stack and queue are linear data structures, but they follow different access rules. A stack follows LIFO, which means Last In, First Out. A queue follows FIFO, which means First In, First Out.
These rules decide which element can be removed first. In an array, we can access many positions using indexes, but in stack and queue we usually work with the allowed end or front according to the rule. Stack and queue are very important in DSA because many problems are not only about storing data, but also about processing data in the correct order.
Stack
A stack works like a pile of plates. The plate placed last is removed first. This is why stack follows Last In, First Out.
In Java, `ArrayDeque` is commonly preferred for stack-style operations. Older Java also has a `Stack` class, but `ArrayDeque` is usually recommended for modern code.
```java
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
int top = stack.pop();
```
`push` adds an element to the top of the stack. `pop` removes and returns the top element. `peek` only reads the top element without removing it.
Stacks are useful when the most recent item should be handled first. This is why stacks are used in undo operations, recursion, browser backtracking, expression evaluation, and balanced parentheses problems.
Queue
A queue works like a line of people waiting for service. The person who enters first is served first. This is why queue follows First In, First Out.
```java
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);
queue.offer(20);
int front = queue.poll();
```
`offer` adds an element to the rear of the queue. `poll` removes and returns the front element. `peek` reads the front element without removing it.
Queues are useful when data must be processed in arrival order. They are used in scheduling, request handling, BFS, and level order traversal of trees.
Important Operations
- Stack: `push` inserts, `pop` removes top, `peek` reads top, `isEmpty` checks whether stack has no elements
- Queue: `offer` inserts, `poll` removes front, `peek` reads front, `isEmpty` checks whether queue has no elements
Always check whether a stack or queue is empty before removing elements if there is any chance it may not contain data. This prevents runtime errors and makes logic safer.
Underflow Idea
Underflow means trying to remove an element when the stack or queue is already empty. For example, calling `pop` on an empty stack has no valid element to remove. In Java collection-based code, checking `isEmpty()` before removal is a simple and safe habit. It also makes the logic clearer for students reading the program.
Types of Queue
A simple queue follows FIFO order, where insertion happens at the rear and deletion happens from the front. A circular queue connects the rear position back to the front position when space is available. It is commonly taught with arrays to use fixed-size memory efficiently.
A priority queue removes elements based on priority instead of normal arrival order. In Java, `PriorityQueue` gives the smallest value first by default for numbers.
Deque
`Deque` means double-ended queue. It allows insertion and deletion from both ends. `ArrayDeque` can be used as a stack and also as a queue. This is why it appears in both examples.
Where They Are Used
Stacks are used when the latest value must be processed first. Examples include function calls, recursion, undo operations, expression evaluation, backtracking, and checking balanced brackets. Queues are used when the earliest value must be processed first. Examples include scheduling, BFS, level order traversal, request handling, and producer-consumer problems.
In interviews, the most common beginner stack problem is balanced parentheses. The most common queue use is BFS or level order traversal.
```java
import java.util.*;
public class Main {
public static void main(String[] args) {
ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
stack.push(30); Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);
queue.offer(20);
queue.offer(30); System.out.println("Stack top removed = " + stack.pop());
System.out.println("Queue front removed = " + queue.poll());
}
}
```
In this program, stack removes `30` first because it was inserted last. Queue removes `10` first because it was inserted first. This output clearly shows the difference between LIFO and FIFO.
Practice Question
Use a stack to check whether parentheses in a string are balanced. Then create a queue, insert five numbers, and remove them one by one to observe FIFO order.