ReviseAlgo Logo

Stacks & Queues

Stack Operations & Design

Master Stack operations, parenthesis matching, expression evaluations, and classic Stack design patterns like MinStack.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What are Stack Operations & Design?

Stack Operations are the core API interfaces used to modify stacks: push (insert), pop (delete), peek (view top), and isEmpty. Stack Design refers to composing multiple stacks or lists to implement custom behaviors (like retrieval of the minimum element in constant time).

Why is it Important?

Many computer science validation tasks require tracking nested relationships. Stacks are uniquely suited for parsing nested environments:
  • Checking nested brackets: {[()]}.
  • Evaluating mathematical equations: 3 + (4 * 2).
  • Reverting paths during depth-first searches (backtracking).

    • Where is it Used?

  • Web Browsers: Storing navigation steps to support the Back/Forward history buttons.
  • IDE Parsers: Highlighting mismatched brackets in code files.

    • 2. Mental Model: The Bracket Nest

    Think of parenthesis matching as nesting dolls:

  • When you see an opening bracket ((, [, {), you open a doll and push it onto your stack.
  • When you see a closing bracket (), ], }), it must match the outermost open doll (the top of your stack).
  • If it matches, you close both dolls and pop it off the stack.
  • If it doesn't match, or if there are no open dolls left, the structure is invalid.

    • 3. Core Algorithms & Implementations

    1. Valid Parentheses (LeetCode 20)

    Using a stack to validate matching open/close bracket pairs.

    2. MinStack Design (LeetCode 155)

    Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.
  • Solution: Maintain a secondary minStack that stores the running minimum value corresponding to each element in the main stack.

    • 4. Visual Trace: Parenthesis Matching

    Trace showing validation checks for input "{()}":

    5. Real-World Applications

  • Calculator Engine: Postfix notation evaluation (Reverse Polish Notation) uses a stack to parse digits and execute operator priorities safely.
  • Syntax Analyzers: Compilers building abstract syntax trees (AST) from raw source code formats.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test nesting and boundary checks:
  • "Given a string containing arithmetic operations, evaluate it." (Basic Calculator -> requires two stacks: one for operators, one for digits).
  • "Implement a Queue using Stacks." -> Use two stacks (input and output). Push elements onto input. To dequeue, if output is empty, pop all elements from input and push them onto output, then pop from output (O(1) amortized time).

    • Common Mistakes

    Warning: 1. Empty Stack Pop Crashes: Attempting to execute stack.pop() when stack.isEmpty() is true. Always check isEmpty() before popping.
    > 2. Space overhead of MinStack: Storing duplicates in minStack unnecessarily. Optimize by only pushing onto minStack if the new value is ≤ the current minimum.

    7. Summary

  • Operations: Push, pop, and peek take O(1) time.
  • Parentheses: Stacks match opening/closing boundaries cleanly.
  • MinStack: Secondary stack caches minimum values for O(1) retrieval.

    • 8. Quiz

    Question 1: What is the time complexity of the pop operation in a MinStack implemented with a secondary stack? Answer: O(1) time complexity. We compare values and pop from both stacks in constant time.
    Question 2: How do you evaluate a Postfix expression (e.g. '3 4 +') using a stack? Answer: Scan from left to right. If you see a number, push it onto the stack. If you see an operator, pop the top two numbers, apply the operator, and push the result back. At the end, the stack contains the final evaluated answer.
    Question 3: In C++, what is the difference between std::stack top() and pop()? Answer: top() returns a reference to the top element of the stack without removing it. pop() removes the top element but returns void (nothing). In Java, pop() does both: it removes and returns the top element.
    Question 4: True or False: If parenthesis matching finishes scanning the string and the stack is not empty, the string is valid. Answer: False. If the stack is not empty, it means there are unclosed opening brackets (e.g. ( ( )), making the string invalid.
    Question 5: Can you implement a Stack using a singly linked list? What is the insertion complexity? Answer: Yes, by inserting and deleting nodes exclusively at the head. Since head updates require no traversals, all stack operations take guaranteed O(1) time.