Stack in Computer Science: Class 12 NCERT Guide with Python Implementation

What is a Stack? Understanding the Basics

A Stack is a linear data structure that stores elements in a specific order. The key rule is Last In First Out (LIFO), meaning the last element added is the first to be removed.

• Top: The end of the stack where all insertions (push) and deletions (pop) happen.
• Bottom: The opposite end, where no operations occur directly.

Stacks are used in many computer science applications such as function call management, expression evaluation, and undo mechanisms.

Example: Imagine a stack of plates. You add plates on top and remove the top plate first.

Class 12 NCERT Computer Science introduces stacks to help students understand data handling and algorithm design.

Core Operations of a Stack Explained

The main operations on a stack are:

• Push: Add an element to the top of the stack.
• Pop: Remove the top element from the stack.
• Top (Peek): View the top element without removing it.
• isEmpty: Check if the stack has no elements.
• Size: Count the number of elements in the stack.

Each operation must be efficient and maintain the LIFO order.

Example:

If the stack is [10, 20, 30] (30 is top):

• Push(40) → [10, 20, 30, 40]
• Pop() → returns 40, stack becomes [10, 20, 30]
• Top() → returns 30
• isEmpty() → returns False
• Size() → returns 3

Implementing Stack in Python Using Lists

Python lists provide a simple way to implement stacks because they support dynamic resizing and built-in methods:

• Use append() to push elements onto the stack.
• Use pop() to remove the top element.

Here is a sample Python implementation for Class 12 NCERT students:

```python stack = []

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

def opPush(element): stack.append(element)

def opPop(): if isEmpty(): return "Stack Underflow" return stack.pop()

def size(): return len(stack)

def top(): if isEmpty(): return "Stack is empty" return stack[-1]

def display(): print("Stack elements:", stack)

# Example usage opPush('Glass 1') opPush('Glass 2') print(top()) # Output: Glass 2 opPop() display() # Output: ['Glass 1'] ```

This approach prevents stack underflow by checking if the stack is empty before popping. Overflow is not a concern due to Python's dynamic list size.

Stack vs Queue: Key Differences for Class 12 Students

Stacks and queues are both linear data structures but differ in how elements are added and removed.

Understanding these differences helps Class 12 students grasp data structure concepts clearly and prepare for exams.

Common Applications of Stack in Computer Science

Stacks are widely used in various computer science problems and systems:

• Expression Evaluation: Converting and evaluating arithmetic expressions (infix, postfix).
• Function Call Management: Managing recursive function calls using call stack.
• Undo Mechanisms: In text editors and software to reverse actions.
• Syntax Parsing: Compilers use stacks to check for balanced parentheses.
• Backtracking Algorithms: Solving puzzles and pathfinding.

Class 12 NCERT Computer Science highlights these uses to show the practical importance of stacks.

Worked Example: Using Stack to Reverse a String in Python

Reversing a string using a stack demonstrates the LIFO principle:

```python string = "NCERT" stack = []

# Push all characters for char in string: stack.append(char)

reversed_str = ""

# Pop characters to reverse while stack: reversed_str += stack.pop()

print("Reversed String:", reversed_str) # Output: TRECN ```

Explanation: Each character is pushed onto the stack, then popped in reverse order, effectively reversing the string.

This example helps Class 12 students understand stack operations practically.