Class 12 Stack Data Structure: Complete Concepts and Practice

Big picture

A data structure is a way of organising data so it can be used efficiently. A stack is one of the simplest: items are added and removed from one end only, called the top. Think of a pile of plates: you place a plate on top and take the top plate first.

This rule is LIFO: Last In, First Out. Stacks appear everywhere in computing: the undo button, the browser's back button, and the way Python keeps track of function calls. Board questions ask you to write push() and pop() functions using a list, often with a condition (push only even numbers, or only records meeting a test), and to trace stack operations.

Learning goals

• Define a data structure and explain LIFO.

• Explain push, pop, peek and isEmpty, and overflow and underflow.

• Implement a stack using a Python list.

• Write stack functions with conditions, as asked in board papers.

• Trace a sequence of stack operations.

• Apply stacks to reverse a string, check balanced brackets and evaluate postfix expressions.

Core ideas

1. The stack and LIFO

• Top: the end where all insertions and deletions happen.

• LIFO: the element inserted last is the first one removed.

Real-life examples: a pile of books or plates; bangles on a wrist; the undo feature in a text editor (the most recent action is undone first); the back button of a browser (the most recently visited page is reopened first).

2. Stack operations

• Overflow: trying to PUSH onto a stack that is full (when the stack has a fixed size).

• Underflow: trying to POP or PEEK from an empty stack. A Python list grows as needed, so overflow doesn't usually occur, but underflow must be checked before popping.

3. Implementing a stack with a Python list

The end of the list is used as the top: append() pushes and pop() pops, both at the end.

def push(stack, item):
    stack.append(item)

def pop(stack):
    if is_empty(stack):
        print('Underflow')
        return None
    return stack.pop()

def peek(stack):
    if is_empty(stack):
        return None
    return stack[-1]

def is_empty(stack):
    return len(stack) == 0

stack = []
for x in [10, 20, 30]:
    push(stack, x)
print(pop(stack), peek(stack), stack)   # 30 20 [10, 20]

4. Board-style conditional stack programs

Example 1. Push all even numbers from a list onto a stack, then pop and display them.

def push_even(nums, stack):
    for n in nums:
        if n % 2 == 0:
            stack.append(n)

def pop_all(stack):
    while stack:
        print(stack.pop(), end=' ')
    print('Stack empty')

S = []
push_even([12, 7, 18, 5, 20], S)   # S becomes [12, 18, 20]
pop_all(S)                         # 20 18 12 Stack empty

Example 2. A dictionary holds student names and marks. Push the names of students scoring above 75.

def push_toppers(marks, stack):
    for name in marks:
        if marks[name] > 75:
            stack.append(name)

R = {'Asha': 88, 'Ravi': 64, 'Neha': 91}
S = []
push_toppers(R, S)     # S becomes ['Asha', 'Neha']
print(S.pop())         # Neha

Example 3 (records). Each record is a list [roll, name, city]. Push [roll, name] for students from a given city. The same pattern applies: loop, test, append the required part.

5. Tracing stack operations

Start with an empty stack and apply: push(1), push(2), pop(), push(3), push(4), pop().

Final stack: [1, 3].

6. Applications of stacks

Reversing a string: push every character, then pop them all.

def reverse(text):
    s = []
    for ch in text:
        s.append(ch)
    out = ''
    while s:
        out += s.pop()
    return out

print(reverse('STACK'))   # KCATS

Checking balanced brackets: push every opening bracket; for every closing bracket, the top must be the matching opening bracket. At the end, the stack must be empty.

def balanced(expr):
    s = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for c in expr:
        if c in '([{':
            s.append(c)
        elif c in ')]}':
            if not s or s.pop() != pairs[c]:
                return False
    return not s

print(balanced('(a+[b*c])'))   # True
print(balanced('(a+b]'))       # False (mismatch)
print(balanced('((a)'))        # False (an opening bracket is left over)

Evaluating postfix expressions. In postfix notation, the operator comes after its operands: infix (5 + 3) × 2 becomes 5 3 + 2 *. Scan left to right: push numbers; for an operator, pop two operands (the first popped is the right operand), apply the operator, push the result.

5 3 + 2 *
push 5, push 3, '+' → pop 3 and 5 → push 8
push 2, '*' → pop 2 and 8 → push 16
Result: 16

6 2 3 * -
push 6, 2, 3, '*' → pop 3 and 2 → push 6, giving [6, 6]
'-' → pop 6 (right) and 6 (left) → push 6 - 6 = 0
Result: 0

Other uses: keeping track of function calls (the call stack, which also handles recursion), undo/redo in editors, browser history, and converting infix expressions to postfix.

A reliable routine for stack questions

1. Represent the stack as a list with the top at the end.

2. For push, use append(); for pop, check that the list isn't empty, then use pop().

3. For conditional pushes, loop over the data, test the condition, and append only the required part.

4. When tracing, draw the list after every operation.

5. For postfix evaluation, remember that the first value popped is the right-hand operand.

Connections that matter

• Advanced Python revision: lists and their append() and pop() methods implement stacks.

• Functions and recursion: recursive calls are managed by the call stack.

• Exception handling: an unchecked pop() on an empty list raises IndexError.

Common mistakes

• Popping from the front with `pop(0)`. That makes a queue, not a stack.

• Not checking for an empty stack before popping, which raises IndexError.

• Reversing operand order in postfix evaluation for - and /.

• Pushing the whole record when only some fields are asked for.

• Confusing LIFO with FIFO (FIFO is a queue).

Revision checklist

• I can explain LIFO, push, pop, peek, overflow and underflow.

• I can implement a stack with a Python list.

• I can write conditional push and pop functions for lists and dictionaries.

• I can trace a sequence of stack operations.

• I can reverse a string, check balanced brackets and evaluate postfix with a stack.