Stack and Queue Implementations in Java
In a school library, returned books are piled on the desk. The librarian always picks up the book on top, which is the one that was returned last. At the canteen counter it is the opposite: the student who joined the line first is served first. These two everyday rules are two of the most useful data structures in programming: the stack (last in, first out) and the queue (first in, first out). In this lesson, you will build both from scratch in Java using arrays, use a stack to check brackets in an expression, and learn which JDK class to use for each.
What Are Stacks and Queues?
A stack in Java is a data structure that is used to store elements so that the last element added is the first one removed (LIFO: last in, first out). A queue is a data structure that is used to store elements so that the first element added is the first one removed (FIFO: first in, first out).
| Stack | Queue | |
|---|---|---|
| Rule | Last in, first out | First in, first out |
| Add | push (on top) | enqueue / offer (at the rear) |
| Remove | pop (from the top) | dequeue / poll (from the front) |
| Look without removing | peek (top) | peek (front) |
| Real-life example | A pile of books | A canteen line |
| Programming uses | Undo, method calls, bracket matching, DFS | Print jobs, task scheduling, BFS |
A Stack Built on an Array
A stack needs only an array and a counter that marks the top.
import java.util.Arrays;
public class BookStack {
private String[] items = new String[2];
private int size = 0;
void push(String item) {
if (size == items.length) {
items = Arrays.copyOf(items, size * 2); // grow when full
}
items[size++] = item;
}
String pop() {
if (size == 0) throw new IllegalStateException("stack is empty");
String item = items[--size];
items[size] = null; // let GC free it
return item;
}
String peek() {
if (size == 0) throw new IllegalStateException("stack is empty");
return items[size - 1];
}
boolean isEmpty() {
return size == 0;
}
public static void main(String[] args) {
BookStack desk = new BookStack();
desk.push("Math");
desk.push("Science");
desk.push("English");
System.out.println("top: " + desk.peek());
while (!desk.isEmpty()) {
System.out.println("pop " + desk.pop());
}
}
}top: English
pop English
pop Science
pop MathExplanation:
pushstores the item at indexsizeand increasessize. When the array is full, it doubles the array, so pushes stay O(1) on average.popdecreasessizeand returns that element. Setting the slot tonulllets the garbage collector free the object.- The books come out in reverse order: English, Science, Math.
A Queue Built on a Circular Array
A queue removes from the front and adds at the rear. Shifting every element after each removal would be O(n), so the usual trick is a circular array: head and tail indexes move forward and wrap around to 0 at the end.
public class CanteenQueue {
private final String[] items;
private int head = 0; // index of the front element
private int tail = 0; // index where the next element goes
private int size = 0;
CanteenQueue(int capacity) {
items = new String[capacity];
}
boolean offer(String item) {
if (size == items.length) return false; // full
items[tail] = item;
tail = (tail + 1) % items.length; // wrap around
size++;
return true;
}
String poll() {
if (size == 0) return null; // empty
String item = items[head];
items[head] = null;
head = (head + 1) % items.length;
size--;
return item;
}
public static void main(String[] args) {
CanteenQueue line = new CanteenQueue(3);
line.offer("Navika");
line.offer("Srihitha");
line.offer("Advitha");
System.out.println("room for one more? " + line.offer("one more"));
System.out.println("served " + line.poll());
line.offer("Navika again"); // reuses slot 0
while (line.size > 0) {
System.out.println("served " + line.poll());
}
}
}room for one more? false
served Navika
served Srihitha
served Advitha
served Navika againExplanation:
- With capacity 3, the fourth
offerreturns false: the queue is full. - Serving Navika frees slot 0. Because
tailwraps around with% items.length, "Navika again" goes into slot 0, behind Srihitha and Advitha in the queue. - Every operation is O(1); nothing is ever shifted.
Using a Stack: Checking Brackets
A classic use of a stack is checking that every bracket in an expression is closed in the right order. Push each opening bracket; for each closing bracket, pop and check that it matches.
import java.util.ArrayDeque;
import java.util.Deque;
public class Brackets {
static boolean balanced(String text) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : text.toCharArray()) {
switch (c) {
case '(', '[', '{' -> stack.push(c);
case ')', ']', '}' -> {
if (stack.isEmpty()) return false;
char open = stack.pop();
if (open != match(c)) return false;
}
default -> { } // ignore other characters
}
}
return stack.isEmpty();
}
static char match(char close) {
return switch (close) {
case ')' -> '(';
case ']' -> '[';
default -> '{';
};
}
public static void main(String[] args) {
System.out.println(balanced("total = (fees[i] + fine) * {rate}"));
System.out.println(balanced("(a + b]"));
System.out.println(balanced("((marks)"));
}
}true
false
falseExplanation: the first expression closes every bracket in reverse order of opening, so it is balanced. In (a + b], the ] pops a (, which doesn't match. In ((marks), one ( is still on the stack at the end. This example uses the JDK's ArrayDeque as the stack.
Which JDK Class to Use
| Need | Use | Avoid |
|---|---|---|
| Stack | Deque<T> s = new ArrayDeque<>(); with push, pop, peek | java.util.Stack (old, synchronized, extends Vector) |
| Queue | Queue<T> q = new ArrayDeque<>(); with offer, poll, peek | LinkedList (works, but slower) |
| Queue by priority | PriorityQueue | Sorting a list after every add |
| Queue shared between threads | ArrayBlockingQueue, LinkedBlockingQueue | Unsynchronized ArrayDeque |
Interview Corner
How do you build a queue using two stacks?
Push new elements onto stack A. To remove, if stack B is empty, pop everything from A and push it onto B (which reverses the order), then pop from B. Each element moves at most twice, so operations are O(1) on average.
Why use a circular array for a queue?
So that removing from the front is O(1) without shifting elements, and freed slots are reused.
Where does the JVM use a stack?
Every thread has a call stack: each method call pushes a frame, and returning pops it. Too many nested calls cause StackOverflowError.
Practice
- Easy: Use
BookStackto reverse the word "ANAMANENI" letter by letter (push each letter, then pop them all). Is it a palindrome? - Harder: Make
CanteenQueuegrow when full instead of returningfalse. Copy the elements into a new array twice the size, starting fromhead, and resetheadto 0 andtailtosize.
Key Takeaways
Was this tutorial helpful?