Stacks

This post builds on Data Structures and Big O Notation. You should be comfortable with Java loops, methods, and collections.

What are Stacks?

A stack is a collection that stores and retrieves elements in last-in, first-out order, usually shortened to LIFO. The newest element still in the collection is the next one removed. Elements are added and removed at one end, called the top.

Think of a pile of trays. Placing a tray on top makes it the next tray available; removing it exposes the tray underneath. A stack applies that same rule to data, regardless of whether an array or linked nodes store the elements.

This organization is useful when newer work must finish before older work can continue. An editor undoes the latest edit before an earlier one. A program returns from a nested method call to the method that called it. Both need access to the most recently added unfinished work.

A stack specifies an access rule rather than a particular storage layout. It does not promise quick access to any arbitrary item. We will first examine the operations that maintain LIFO order, then compare storage choices and use a stack to check nested delimiters.

What are Stacks characteristics?

Access through the top

Operation	Meaning	Example with bottom-to-top contents [A, B]
push(C)	Add an element to the top	Contents become [A, B, C]
peek()	Read the top without removing it	Returns B; contents stay [A, B]
pop()	Remove and return the top	Returns B; contents become [A]
isEmpty()	Check whether there are any elements	Returns false

Each row starts from the same example state. If we push A, then B, then C into an empty stack and pop three times, the result is C, B, A. The structure reverses the order of insertion.

flowchart LR
    A["Empty"] -->|"push A"| B["Top: A"]
    B -->|"push B"| C["Top: B; below: A"]
    C -->|"pop returns B"| D["Top: A"]

Removing from an empty stack is called underflow. An implementation must define what happens in that situation, such as throwing an exception or returning an empty result. A stack with a fixed capacity also needs a policy for an attempted push when full.

A queue answers a different question: which item arrived earliest? It usually serves the oldest item first. A stack serves the newest one first, which is useful when newer work must finish before older work can continue.

Storage and operation costs

The stack is an abstract data type: it specifies behavior. Arrays and linked nodes are ways to implement that behavior.

With an array, store elements consecutively and keep a count called size. If the bottom is at index 0, the top is at size - 1. Pushing writes into index size and increments the count. Popping decrements the count and retrieves that position. Removing an object reference should also clear its array slot so the stack does not retain an unused object.

No elements need to shift. When a resizable array fills, however, a push may allocate a larger array and copy existing elements. That individual push costs O(n). Growing capacity geometrically spreads these copies over many pushes, giving O(1) amortized push time: the average cost per operation over a sequence is bounded by a constant.

With a singly linked list, use the head as the top. Pushing creates a node whose next pointer refers to the previous head. Popping moves the head to its next node. Both require a constant number of pointer changes, although allocating a node has practical memory and runtime costs.

Implementation	Push	Pop and peek	Storage tradeoff
Fixed array	O(1) if space remains	O(1)	Capacity must be chosen in advance
Geometrically growing array	O(1) amortized, O(n) for a resize	O(1) for implementations that do not shrink on pop	Spare capacity; compact element storage
Linked nodes with head as top	O(1) structural work	O(1)	A node and link per element

These costs assume that we use the correct end. Removing the first element of an ordinary array-backed list shifts the remaining elements and costs O(n). Searching a stack for an arbitrary value also costs O(n); LIFO access does not provide fast lookup.

Stacks in action - code examples

Basic stack operations in Java

Java’s Deque<E> interface represents a double-ended queue. It can act as a stack when we insert and remove at the same end. Oracle recommends it over the legacy Stack class; push, pop, and peek operate at the deque’s front. See the Deque API.

Here, String is the element type, and ArrayDeque supplies the storage:

import java.util.ArrayDeque;
import java.util.Deque;

public class StackBasics {
    public static void main(String[] args) {
        Deque<String> history = new ArrayDeque<>();
        history.push("Open file");
        history.push("Insert heading");
        System.out.println(history.peek()); // Insert heading
        System.out.println(history.pop());  // Insert heading
        System.out.println(history.pop());  // Open file
        System.out.println(history.isEmpty()); // true
    }
}

peek() leaves the heading on the stack, so the next pop() still returns it. After the second pop, peek() would return null; pop() would throw NoSuchElementException. If an empty result is expected, pollFirst() removes the top and returns null when empty.

ArrayDeque rejects null elements and is not thread-safe. Its end operations are amortized O(1), while searching and removing an arbitrary matching element are linear operations. These guarantees and restrictions are documented in the ArrayDeque API.

Keep stack operations consistent. Mixing push() with removeLast() removes from opposite ends and changes the processing order.

Check nested delimiters

Consider the text {[()]}. An opening delimiter creates unfinished work: we must eventually see its matching closing delimiter. A newly opened pair must close before the surrounding pair. That is exactly LIFO order.

We will store the expected closing delimiter for each opening delimiter. Reading ( pushes ), for example. When a closing delimiter appears, it must match the top. This avoids a separate lookup when closing a pair.

Our invariant is the fact that remains true after each successfully processed character: the stack contains the closing delimiters still required, with the next required closing delimiter on top.

For {[()]}, the important steps are:

Character	Action	Expected closers, top first
{	Push }	}
[	Push ]	], }
(	Push )	), ], }
)	Match and pop )	], }
]	Match and pop ]	}
}	Match and pop }	Empty

Counting openings and closings would miss an input such as ([)]: the counts agree, but ) arrives while ] is required. The stack retains nesting order as well as the number of unfinished pairs.

A complete checker

The Character type lets the generic collection hold Java characters; Java converts between char and Character automatically. We ignore characters other than the six delimiters. The || expression checks emptiness first, so Java’s short-circuit evaluation prevents pop() from running on an empty deque.

Save this as DelimiterChecker.java and run it with javac DelimiterChecker.java followed by java DelimiterChecker:

import java.util.ArrayDeque;
import java.util.Deque;

public class DelimiterChecker {
    public static boolean balanced(String text) {
        Deque<Character> expected = new ArrayDeque<>();

        for (int i = 0; i < text.length(); i++) {
            char current = text.charAt(i);
            switch (current) {
                case '(':
                    expected.push(')');
                    break;
                case '[':
                    expected.push(']');
                    break;
                case '{':
                    expected.push('}');
                    break;
                case ')':
                case ']':
                case '}':
                    if (expected.isEmpty() || expected.pop() != current) {
                        return false;
                    }
                    break;
                default:
                    // Other characters do not affect delimiter nesting.
                    break;
            }
        }
        return expected.isEmpty();
    }

    public static void main(String[] args) {
        String[] examples = {"{[()]}", "([)]", "(", ")", "", "a + (b * c)"};
        for (String example : examples) {
            System.out.println("\"" + example + "\": " + balanced(example));
        }
    }
}

The output is:

"{[()]}": true
"([)]": false
"(": false
")": false
"": true
"a + (b * c)": true

There are three failure conditions. A closer can arrive with nothing to close, it can disagree with the expected closer, or the input can end while openings remain. Checking only inside the loop would miss the third case. The empty string passes because it has no unmatched delimiters.

Each character is visited once and causes at most one push or pop. For input length n, the runtime is O(n) amortized. Extra space is O(d), where d is the maximum nesting depth, and O(n) in the worst case when every character opens another pair.

This method assumes a non-null string and checks delimiter characters literally. A Java source-code parser would also need to understand comments, quoted strings, and escapes. For example, a parenthesis inside a string literal should not be treated as source-code grouping.

What problems can Stacks solve?

A method call follows the same nesting pattern. Suppose main calls load, which calls parse. The active calls have frames holding information needed to resume them. parse returns to load, and load returns to main. The newest call finishes first. Sorting and Recursion introduces recursive calls, which add more frames in this order.

An explicit stack stores work in a collection instead of relying on nested calls. An iterative depth-first traversal can push nodes still to visit, and a backtracking algorithm can store choices to revisit. An explicit stack can avoid exhausting the call stack, but still consumes memory proportional to the work retained.

Undo history is another application: push reversible commands, then pop the newest command to undo it. A full editor usually also maintains redo history and defines what happens when a new edit follows an undo. The stack supplies the order; the application supplies the meaning of reversing an operation.

Use a stack when the most recent unfinished item should be handled next. If you need fair arrival order, choose a FIFO queue. If you need the smallest or highest-priority item next, choose a priority queue. The useful design decision is the access rule that matches the problem; storage and library choice follow from it.

Conclusion

A stack makes the most recent unfinished item available at the top. push adds that item, peek inspects it, and pop removes it. The LIFO rule stays the same across array and linked implementations, while their allocation and capacity costs differ.

The delimiter checker uses that rule to preserve nesting: each new opening creates the next closing delimiter we must see. The same reasoning applies to nested calls, undo operations, and backtracking. Start with the required processing order, then choose an implementation whose capacity, empty-state behavior, and operation costs fit the workload.