A stack is an abstract data type that follows the Last In, First Out (LIFO) principle. The element that is inserted last is the first one to be removed. Everyday examples include a pile of plates in a cafeteria, a stack of books, or the back button of a web browser. In a stack of plates, the topmost plate is the easiest to take, and new plates are placed on top; the plate at the bottom is removed only after all plates above it have gone.
In computer science, the stack is a linear data structure supporting a small, well-defined set of operations. The two fundamental operations are push, which inserts an element at the top, and pop, which removes the element from the top. A useful extra operation is peek (also called top), which returns the top element without removing it. Because all insertions and deletions occur at one end, the stack is extremely efficient and simple to implement.
This chapter explains the concept of the stack, its operations and terminologies such as overflow and underflow, and shows how to implement a stack in Python using a list. It also explores common applications: reversing a sequence, checking balanced parentheses, converting between infix, prefix and postfix expressions, and the call stack used internally by Python during function calls and recursion. The stack is a favourite topic for both conceptual questions and code-writing questions in the board examination.
A stack provides three primary operations. Push adds a new element to the top of the stack. Pop removes and returns the top element. Peek (top) returns the top element without removing it, allowing the program to inspect the most recently added value. An additional convenience operation isEmpty checks whether the stack is empty.
Every stack has a fixed conceptual capacity in most textbooks. Attempting to push onto a full stack produces a condition called overflow, and attempting to pop from an empty stack produces underflow. In Python's list-based implementation, overflow is rarely a concern because lists grow dynamically, but the empty-stack case must still be guarded.
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack[-1]) # peek -> 20
top = stack.pop() # pop -> 20
print(top, stack) # 20 [10]
Python lists are ideal for implementing a stack. The append() method acts as push, pop() acts as pop (removing the last element), and the index -1 provides peek. The following class wraps these operations with meaningful method names.
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.isEmpty():
return self.items.pop()
else:
return None
def peek(self):
if not self.isEmpty():
return self.items[-1]
else:
return None
def size(self):
return len(self.items)
def display(self):
print(self.items)
Using the class:
s = Stack()
s.push(5)
s.push(10)
s.push(15)
s.display() # [5, 10, 15]
print(s.pop()) # 15
print(s.peek()) # 10
print(s.size()) # 2
The leftmost element of the list is the bottom of the stack, and the rightmost element is the top.
Because a stack removes elements in reverse order of insertion, pushing all characters of a string and then popping them yields the reversed string. This is a classic and simple demonstration of LIFO behaviour.
def reverse_string(s):
stack = list(s)
result = ""
while stack:
result += stack.pop()
return result
print(reverse_string("PYTHON")) # NOHTYP
A stack elegantly verifies whether parentheses in an expression are balanced. Every opening bracket is pushed; every closing bracket is matched against a pop. If the stack ends empty and no mismatch occurs, the expression is balanced.
def is_balanced(expr):
stack = []
pairs = {")": "(", "}": "{", "]": "["}
for ch in expr:
if ch in "({[":
stack.append(ch)
elif ch in ")}]":
if not stack or stack.pop() != pairs[ch]:
return False
return len(stack) == 0
print(is_balanced("(a+b*(c-d))")) # True
print(is_balanced("((a+b)")) # False
Expressions can be written in three notations. In infix, the operator is between operands, as in A + B. In prefix (Polish) notation, the operator precedes the operands, as in + A B. In postfix (Reverse Polish) notation, the operator follows the operands, as in A B +. Postfix and prefix expressions need no parentheses and are evaluated without knowing operator precedence, which makes them ideal for stack-based computation.
A stack converts infix to postfix. Operators are pushed onto the stack, and operators of equal or higher precedence already on the stack are popped out before the new operator is pushed. The algorithm is a frequent examination topic.
precedence = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
def infix_to_postfix(expr):
result = []
stack = []
for ch in expr:
if ch.isalnum():
result.append(ch)
elif ch == "(":
stack.append(ch)
elif ch == ")":
while stack and stack[-1] != "(":
result.append(stack.pop())
stack.pop()
else:
while stack and stack[-1] != "(" and precedence[ch] <= precedence[stack[-1]]:
result.append(stack.pop())
stack.append(ch)
while stack:
result.append(stack.pop())
return "".join(result)
print(infix_to_postfix("A+B*C")) # ABC*+
Postfix evaluation uses a stack of operands. Each operand is pushed; each operator pops two values, applies the operator and pushes the result. When the expression ends, the stack contains a single value, the answer.
def evaluate_postfix(expr):
stack = []
for ch in expr:
if ch.isdigit():
stack.append(int(ch))
else:
b = stack.pop()
a = stack.pop()
if ch == "+":
stack.append(a + b)
elif ch == "-":
stack.append(a - b)
elif ch == "*":
stack.append(a * b)
elif ch == "/":
stack.append(a / b)
return stack.pop()
print(evaluate_postfix("23*5+")) # 11
When a function calls another function (or itself in recursion), Python maintains a call stack of activation records. Each record stores the function's local variables and the return address. This is the same data structure studied here, showing the stack's central role in language implementation.
Overflow occurs when push is attempted on a stack whose capacity is exhausted; in list-based implementations the list simply grows, but in fixed-capacity implementations this is an error state. Underflow occurs when pop or peek is attempted on an empty stack. Both conditions must be checked to write correct code. The isEmpty() method guards against underflow in all implementations.
| Operation | What It Does | Complexity |
|---|---|---|
| push(item) | Add item to the top | O(1) |
| pop() | Remove and return top item | O(1) |
| peek() / top() | Return top item without removing | O(1) |
| isEmpty() | Check if stack is empty | O(1) |
| size() | Return number of elements | O(1) |
| Notation | Form | Example |
|---|---|---|
| Infix | Operator between operands | A + B |
| Prefix | Operator before operands | + A B |
| Postfix | Operator after operands | A B + |
The stack is a fundamental and elegant data structure built on the simple idea of last in, first out. Its operations push, pop and peek are constant time, making it ideal for a wide range of algorithmic problems. List-based implementation in Python is trivial, yet the structure underlies deeply important machinery: expression conversion and evaluation, parentheses matching, browser history, undo operations, and the function call stack that makes recursion possible. Understanding when to use a stack, and correctly tracing its state, is a core skill for computer science. The next chapter examines the queue, a closely related structure that replaces LIFO with a fair, first-in-first-out discipline.