Stack and Queue Implementation in Java: Arrays, Linked Lists, and the Interview Problems That Use Them

Calling a Java collection is easy. Building a stack or queue by hand is harder because every operation must preserve the right index, capacity, and empty-state invariant.

Interviewers use these structures to expose off-by-one errors and vague pointer reasoning. The circular queue is especially useful because one missing modulo operation breaks the whole implementation.

Stack vs queue in one line each

A stack is LIFO: the last item pushed is the first item popped. push, pop, and peek all work at one end called the top.

A queue is FIFO: the first item enqueued is the first item dequeued. Insertion happens at the rear and removal happens at the front.

Both structures can use an array or a linked list:

The abstract operations do not change. Only the state used to implement them changes.

Array-backed stack

For a fixed capacity of five, keep int[] a = new int[5] and int top = -1. The value -1 means empty.

void push(int x) {
    if (top == a.length - 1) throw new IllegalStateException("full");
    a[++top] = x;
}

int pop() {
    if (top == -1) throw new IllegalStateException("empty");
    return a[top--];
}

int peek() {
    if (top == -1) throw new IllegalStateException("empty");
    return a[top];
}

Trace the operations. Push 5, 10, and 15, so top moves from -1 to 0, 1, and 2. The occupied part of the array is [5, 10, 15, _, _]. pop() returns 15 and moves top back to 1. peek() then returns 10 without changing top.

Overflow occurs when top == a.length - 1. Underflow occurs when a pop or peek is attempted at top == -1. Each normal operation is O(1).

Circular queue on an array

A linear array queue wastes cells after dequeues unless elements are shifted. A circular queue reuses them by wrapping each moving index with modulo arithmetic.

Use capacity 5, front = 0, rear = -1, and count = 0:

void enqueue(int x) {
    if (count == q.length) throw new IllegalStateException("full");
    rear = (rear + 1) % q.length;
    q[rear] = x;
    count++;
}

int dequeue() {
    if (count == 0) throw new IllegalStateException("empty");
    int value = q[front];
    front = (front + 1) % q.length;
    count--;
    return value;
}

Now run the trace one operation at a time:

1. Enqueue 10: rear = 0, array [10, _, _, _, _], count 1.

2. Enqueue 20: rear = 1, array [10, 20, _, _, _], count 2.

3. Enqueue 30: rear = 2, array [10, 20, 30, _, _], count 3.

4. Dequeue returns 10: front = 1, logical array [_, 20, 30, _, _], count 2.

5. Enqueue 40: rear = 3, array [_, 20, 30, 40, _], count 3.

6. Enqueue 50: rear = 4, array [_, 20, 30, 40, 50], count 4.

7. Enqueue 60: rear = (4 + 1) % 5 = 0. Store 60 at index 0, giving [60, 20, 30, 40, 50], count 5.

8. Enqueue 70: count already equals capacity 5, so reject it as full.

The final queue order from front to rear is 20, 30, 40, 50, 60. Physically, the array is [60, 20, 30, 40, 50], with front = 1, rear = 0, and count = 5. Logical order and physical index order are different after wrap-around.

Linked-list stack and queue in Java

A linked implementation trades contiguous storage for freedom from a fixed capacity. One node type serves both structures:

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

The stack needs a single top reference. Push links the new node in front of the old top; pop unlinks it and hands back its value.

Node top;

void push(int x) {
    Node n = new Node(x);
    n.next = top;
    top = n;
}

int pop() {
    if (top == null) throw new IllegalStateException("empty");
    int value = top.value;
    top = top.next;
    return value;
}

Push 5, 10, then 15 and the chain reads 15 -> 10 -> 5 from top. The first pop() returns 15 and moves top to the node holding 10, the same order the array version gave, with no overflow check to write.

The queue needs both ends. Enqueue appends at rear, dequeue removes at front, and removing the last node has to reset both:

Node front, rear;

void enqueue(int x) {
    Node n = new Node(x);
    if (rear == null) { front = rear = n; return; }
    rear.next = n;
    rear = n;
}

int dequeue() {
    if (front == null) throw new IllegalStateException("empty");
    int value = front.value;
    front = front.next;
    if (front == null) rear = null;
    return value;
}

Every operation here is still O(1). What you pay for it is one extra reference per element and one allocation per insertion, which is why the array version remains the faster choice whenever the maximum size is known in advance.

Java's library classes

For normal Java code, ArrayDeque is the useful default for both roles:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
int latest = stack.pop();

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);
Integer earliest = queue.poll();

The legacy java.util.Stack extends Vector and carries synchronised legacy behaviour. Prefer the Deque interface with ArrayDeque for a stack unless a specific concurrency requirement calls for another structure.

Queue is an interface, not a concrete class. Both ArrayDeque and LinkedList implement it. ArrayDeque does not allow null, so a null result from poll() or peek() can unambiguously mean empty. Methods such as remove() and element() throw on empty instead, so choose the method pair deliberately.

ArrayDeque is one member of a much larger library. The Java Collections Framework: ArrayList, HashMap, TreeMap walkthrough sets out the list and map types you will reach for beside it.

Interview follow-ups that reuse these ideas

Queue using two stacks

Keep inStack for arrivals and outStack for departures. Enqueue pushes onto inStack. On dequeue, transfer every item to outStack only if outStack is empty, then pop from outStack.

After pushing 1, 2, and 3, the top of inStack is 3. Transfer pops 3, then 2, then 1 and pushes them onto outStack, making 1 its top. Dequeues now return 1, 2, and 3 in FIFO order. One transfer costs O(n), but each element moves between stacks only once, so the amortised cost per operation is O(1).

Valid parentheses

Push every opening bracket. For each closing bracket, check that the stack is non-empty and its top is the matching opener. The input is balanced only if every closer matches and the stack is empty at the end.

Minimum stack

Keep a second stack of running minimums. When pushing a value, also push the new minimum. Pop both together. getMin() then reads the second stack's top in O(1).

Converting infix to postfix is the same idea again: a stack holds operators until a symbol of lower precedence arrives, then releases them in the order the expression needs. These follow-ups travel together, and the DSA Interview Questions: 7 Patterns for Placements breakdown groups them with the other patterns worth drilling.

Traps that cost the mark

• Without count, you need another convention to distinguish empty from full. One common design leaves one array slot unused. Do not use the same pointer state for both meanings.

• Forgetting % capacity lets front or rear move beyond the array.

• == compares Integer references, which can appear to work for cached small values and fail elsewhere. Unbox to int or use .equals() when comparing values.

• pop() on an empty stack throws. ArrayDeque.peek() and poll() return null on empty, while element() and remove() throw.

• In a linked queue, update both front and rear when the final node is removed. Leaving rear pointing to an old node corrupts the empty state.

How interviews frame this

Whiteboard prompts ask you to implement a queue without Queue, detect full in a circular buffer, or add getMin() to a stack. Reasoning prompts ask why ArrayDeque is preferred over Stack, or why the two-stack queue is amortised O(1) rather than worst-case O(1).

KnowledgeGate's question bank carries over 1,500 data-structures questions, stacks and queues included. The Coding & DSA category places them alongside linked lists, trees, and algorithm analysis.

The short version and your next step

For an array stack, make the meaning of top explicit. For a circular queue, track count, wrap both moving indices with modulo, and separate logical order from physical array order. In application code, prefer ArrayDeque for ordinary stack and queue work.

Next, build both structures from scratch in DSA using Java. Test empty, one-item, full, wrap-around, and repeated drain-and-refill cases before moving to the two-stack queue.