Stacks

A stack is one of the simplest data structures, yet it plays a major role in solving many complex problems. From managing function calls and undo operations to parsing expressions and validating syntax, stacks appear naturally whenever a problem requires reversing order, tracking history, or managing nested state.

In technical interviews at FAANG companies, stacks are frequently tested not because they are difficult to implement, but because recognizing when to use a stack requires strong problem intuition. Many problems that appear complicated at first become straightforward once you identify the underlying stack behavior.

What is a Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.

This means:

• The last element added to the stack is the first one to be removed.
• All insertions and removals happen at the same end, commonly called the top of the stack.

You can think of a stack like a pile of plates as shown below. You place a plate on top, and when you remove one, you take the top plate first.

Intuition behind Stacks

Stacks are best understood through problems involving nesting and backtracking.

Consider navigating a series of nested folders on a computer. Each time you enter a folder, you push it onto your navigation history. When you press the “back” button, you return to the most recently visited folder that hasn’t been exited yet. This behavior directly mirrors how a stack operates.

The key idea is simple:

Key characteristics of a Stack

So far we have understood what stacks actually are and where they usually appear.

A stack enforces a strict access discipline that shapes how problems are solved using it. Unlike arrays or lists, you cannot freely access or remove elements from the middle of a stack. All operations are constrained to a single end, which simplifies reasoning about state and order.

The defining characteristics of a stack are:

• Last In, First Out (LIFO) access: the most recently added element is always the first one to be removed.
• Single point of interaction (the top): insertions, removals, and inspections all occur at the top of the stack.
• Constant-time operations: push, pop, and peek operations all run in O(1) time.
• Implicit state tracking: the stack naturally preserves the order of unresolved or pending operations, making it ideal for nested and backtracking problems.

These constraints may seem limiting, but they are precisely what make stacks powerful. By restricting access, stacks eliminate ambiguity and enforce a clear, predictable flow of execution.

How Stacks work

At a conceptual level, stacks operate by managing unfinished work. Whenever a new context, operation, or state begins, it is placed on top of the stack. When that context is completed, it is removed, revealing the previous state underneath.

Basic Stack operations

Stacks expose a small and well-defined set of operations. While each operation is simple on its own, together they enable stacks to manage nested states, track unresolved work, and reverse execution order.

Push (Add an element)

The push operation adds a new element to the top of the stack. Conceptually, this represents entering a new state or starting a new operation that must be completed later.

stack = []

# Push elements onto the stack
stack.append(10)
stack.append(20)
stack.append(30)

Example: If you push 10, then 20, then 30, the stack now looks like this:

The most recently added element (30) sits at the top and will be the first one removed.

Pop (Remove the top element)

The pop operation removes and returns the element at the top of the stack. This represents completing the most recent unresolved operation.

stack = [10, 20, 30]

top_element = stack.pop()  # Removes 30

Example: After popping once, the stack becomes:

The value 30 is returned, and the stack now resumes from the previous state.

Peek / Top (Inspect without removing)

The peek (or top) operation allows you to inspect the top element of the stack without removing it. This is useful when you need to check the current state before deciding what to do next.

stack = [10, 20, 30]

top_element = stack[-1]  # 30

Example: The stack remains unchanged:

You can see the most recent element without modifying the stack.

Is empty (Safety check)

The is empty check determines whether the stack contains any elements. This operation is essential for preventing invalid actions, such as popping from an empty stack.

stack = []

is_empty = len(stack) == 0  # True

Example: If the stack is empty and you attempt to pop, a runtime error would occur. Checking first ensures safe stack usage.

Complexity analysis

Understanding the cost of stack operations helps evaluate their impact when used inside larger algorithms.

Time complexity

All core stack operations run in constant time because they only interact with the top of the stack and do not depend on the number of elements stored.

• Push: O(1): Adding an element to the top of the stack requires a single insertion operation.
• Pop: O(1): Removing the top element involves a single removal operation, with no shifting or traversal.
• Peek: O(1): Accessing the top element is a direct lookup and does not modify the stack.

These constant-time guarantees make stacks especially useful inside loops and performance-critical algorithms.

Space complexity

• O(n), where n is the number of elements stored in the stack.

The stack must store every element that has been pushed but not yet popped. In the worst case, all elements remain in the stack at the same time, requiring linear space.

Stack vs. Queue

Understanding how stacks differ from queues helps in choosing the right data structure.

Using Stacks in algorithms

Stacks are rarely used on their own. In interview problems, they usually serve as the core mechanism inside a larger solution.

Stacks are particularly useful when an algorithm needs to:

• Track previous elements while processing new ones
• Handle nested or hierarchical structures
• Defer decisions until more information is available
• Process data in reverse order

Rather than storing values arbitrarily, stacks preserve the order of unresolved work. Recognizing this role is key to identifying stack-based solutions in interviews.

Common pitfalls when using Stacks

One of the most common mistakes is failing to recognize stack patterns in disguise. Many problems require stack logic even though the word “stack” never appears in the prompt.

Other common issues include:

• Popping from an empty stack
• Using stacks when order does not matter
• Overusing recursion when an explicit stack would be safer
• Mismanaging stack state in nested logic