What is a Stack data structure?
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle: the element inserted most recently is the first one removed. Stacks support adding and removing elements at one end, commonly called the top.
Read full answerHide full answer
Applies tolanguage-independent (examples in Python 3.12)
Core Operations
A stack typically provides these operations:
-
Push: Insert an element at the top.
-
Pop: Remove and return the top element.
-
Peek: Return the top element without removing it.
-
is_empty: Check whether the stack contains no elements.
-
Size: Return the number of stored elements.
If A, B, and C are pushed in that order, the next element popped is C, followed by B and then A.
An empty stack has no top, so popping or peeking it is invalid. A one-element stack becomes empty after that element is popped. Duplicate and negative values are valid and are stored as separate entries; no ordering requirement is imposed on their values.
Python List Behavior
A Python list can act as a stack by treating its end as the top:
-
append(value)pushes a value. -
pop()removes and returns the top value. -
stack[-1]peeks at the top, but only after checking that the list is not empty. -
len(stack)returns the stack size.
Because pop() and stack[-1] act on the end of the list, they preserve LIFO ordering. Operations such as pop(0) and insert(0, value) should not be used as stack operations because they shift the remaining elements and take O(n) time.
Complexity
For a stack backed by a Python list:
| Operation | Best | Average | Worst | Reason |
|---|---|---|---|---|
Push / append |
O(1) | O(1) | O(n) | A resize during an append may copy all elements. |
| Pop | O(1) | O(1) | O(n) | A resize during a pop may copy or move elements. |
Peek / stack[-1] |
O(1) | O(1) | O(1) | Accessing the last element does not shift other elements. |
is_empty |
O(1) | O(1) | O(1) | The list length is directly available. |
Size / len |
O(1) | O(1) | O(1) | The list length is directly available. |
A sequence of pushes and pops has amortized O(1) time per operation, although an individual operation can take O(n) when the list resizes.
For n stored elements, the stack uses O(n) total space for its own storage and O(1) auxiliary space beyond that storage. These figures count the stack but not any separate input collection; an input that is copied into the stack must be counted separately. In a recursive algorithm, add O(d) space for the recursion stack, where d is the maximum recursion depth.
A linked-list implementation can provide O(1) worst-case push and pop by inserting and removing at the head, while still requiring O(n) total space for its nodes.
Common Uses
Stacks are useful whenever the most recent unfinished item must be handled first:
-
Function calls: The call stack stores active frames, including return information.
-
Undo operations: Each action can be pushed and later popped to reverse it.
-
Expression evaluation: Infix expressions can be converted to postfix using an operator stack; postfix or RPN expressions are evaluated with a value stack.
-
Balanced parentheses: Push opening delimiters and pop them when matching closing delimiters appear.
-
DFS iteration: An explicit stack stores nodes that still need to be visited.
-
Backtracking: The stack records choices so they can be reversed when a path fails.
Common Pitfalls
-
Popping or peeking an empty stack: Check whether the stack is non-empty before these operations.
-
Incorrect ordering:
pop()returns the newest element, not the oldest. -
Using the wrong end: Treat the end of the list as the top; avoid
pop(0)andinsert(0, value). -
Ignoring amortized behavior: Individual list resizes can cost O(n), although sequences of operations have amortized O(1) cost per operation.
-
Confusing storage with a queue: A stack is LIFO, while a queue is First In, First Out.
Interview Tips
Interviewers often follow up by asking you to implement valid-parentheses validation, a minimum stack, a function-call simulation, DFS with an explicit stack, or expression evaluation. Be ready to explain why a stack preserves ordering, handle empty-input cases, and state the time and space complexity in Big-O notation.