Unravel › Java concepts › Algorithms and data structures
Building your own stack or queue
Writing your own stack or queue (push, pop, enqueue, dequeue) on an array or linked nodes is a standard exercise that shows how the library classes work: an array plus an index, or nodes plus head and tail references.
Learn these first
At a glance
A stack is a pile of plates with an index finger on the top plate.
- 1Array stack: int[] data; int top = 0; push(x) { data[top++] = x; }, pop() { return data[--top]; }, peek() { return data[top - 1]; }, empty when top == 0Grow the array by doubling when it is full.
- 2Linked stack: the top is the head of a linked list; push and pop change the head in O(1)
- 3Circular queue on an array: keep head and tail indexes and wrap with % capacity; full when size == capacityLinked queue: enqueue appends at the tail node, dequeue removes at the head.
- 4Check boundaries: popping an empty stack should throw (NoSuchElementException or IllegalStateException) rather than return garbage
- Decide what an empty or full structure does: throw, return null or Optional, or block (a BlockingQueue)
- Make it generic (Stack<T>) and be careful with a generic array: (T[]) new Object[n] causes an unchecked cast warning, which is acceptable here because the array is private
- Amortised doubling makes push O(1) on average: growing copies n items but happens only after n pushes
import java.util.NoSuchElementException;public class IntStack { private int[] data = new int[4]; private int top; public void push(int x) { if (top == data.length) data = java.util.Arrays.copyOf(data, top * 2); data[top++] = x; } public int pop() { if (top == 0) throw new NoSuchElementException("stack is empty"); return data[--top]; } public int peek() { return data[top - 1]; } public boolean isEmpty() { return top == 0; }}Read the full explanation (about 1 min)
Writing your own stack or queue (push, pop, enqueue, dequeue) on an array or linked nodes is a standard exercise that shows how the library classes work: an array plus an index, or nodes plus head and tail references.
A mental model
A stack is a pile of plates with an index finger on the top plate. A queue is a line with a marker at the front and one at the back.
How it works
Array stack: int[] data; int top = 0; push(x) { data[top++] = x; }, pop() { return data[--top]; }, peek() { return data[top - 1]; }, empty when top == 0. Grow the array by doubling when it is full.
Linked stack: the top is the head of a linked list; push and pop change the head in O(1).
Circular queue on an array: keep head and tail indexes and wrap with % capacity; full when size == capacity. Linked queue: enqueue appends at the tail node, dequeue removes at the head.
Check boundaries: popping an empty stack should throw (NoSuchElementException or IllegalStateException) rather than return garbage.
Going deeper
Decide what an empty or full structure does: throw, return null or Optional, or block (a BlockingQueue).
Make it generic (Stack<T>) and be careful with a generic array: (T[]) new Object[n] causes an unchecked cast warning, which is acceptable here because the array is private.
In production code use ArrayDeque; own implementations are for learning or special needs (bounded ring buffers).
Under the hood
Amortised doubling makes push O(1) on average: growing copies n items but happens only after n pushes. A ring buffer avoids shifting items by moving the head index instead.
Common mistakes
- Off-by-one with
top. - Not handling empty or full states.
- Shifting the array on each dequeue (O(n)).
- Leaking references by not nulling removed slots.
How Unravel recognises it
When you paste code, Unravel looks for these signs of building your own stack or queue. Spotting them yourself is a good habit when you read unfamiliar code:
- Method names you declare:
push()pop()enqueue()dequeue()peek()offer()isEmpty()size()isFull()
Part of a learning path
- Algorithms and data structures · previous: Linked lists · next: Trees and tree traversal
Related concepts
Frequently asked questions
What is Building your own stack or queue?
Writing your own stack or queue (push, pop, enqueue, dequeue) on an array or linked nodes is a standard exercise that shows how the library classes work: an array plus an index, or nodes plus head and tail references.
What are the most common mistakes with Building your own stack or queue?
Off-by-one with top. Not handling empty or full states. Shifting the array on each dequeue (O(n)). Leaking references by not nulling removed slots.
How can I see Building your own stack or queue in real code?
Paste your own Java into Unravel and it will point out where building your own stack or queue appears, explain how it works at the detail level you choose, and draw the flow of the code around it.