Data Structure - Stack

1. Introduction to Stack

A stack is an ordered collection of elements where insertion and deletion take place at the same end, called the top. The stack is a linear data structure that follows the LIFO (Last In, First Out) principle.

Analogy: A stack of plates in a cafeteria. The last plate placed on top is the first one removed. You cannot remove a plate from the middle without first removing the plates above it.

Characteristics:

• Elements are added and removed only from the top.
• The last element inserted is the first one to be removed.
• Stack has a dynamic size (can grow or shrink).
• Only the top element is accessible at any given time.

2. LIFO Principle

LIFO stands for Last In, First Out. The most recently added element is the one that is removed first.

# Stack visualization (top on the right)
# Empty: []
# Push 10: [10]
# Push 20: [10, 20]
# Push 30: [10, 20, 30]
# Pop:     [10, 20]  (removed 30)
# Pop:     [10]      (removed 20)

3. Basic Stack Operations

4. Stack Implementation using List

In Python, a list can be used to implement a stack efficiently. The end of the list serves as the top of the stack.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return None

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        return None

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)

    def display(self):
        print("Stack (top to bottom):", self.items[::-1])

5. Push Operation

The push operation adds an element to the top of the stack.

def push(self, item):
    self.items.append(item)
    print(f"Pushed {item} to stack.")

Algorithm:

1. Accept the element to be inserted.
2. Append the element to the end of the list.
3. Increment the size of the stack.

6. Pop Operation

The pop operation removes and returns the top element from the stack.

def pop(self):
    if self.is_empty():
        print("Stack is empty. Cannot pop.")
        return None
    item = self.items.pop()
    print(f"Popped {item} from stack.")
    return item

Algorithm:

1. Check if the stack is empty. If empty, return underflow error.
2. Remove and return the last element from the list.
3. Decrement the size of the stack.

7. Peek/Top Operation

The peek operation returns the top element without removing it.

def peek(self):
    if self.is_empty():
        print("Stack is empty.")
        return None
    return self.items[-1]

8. isEmpty Operation

The isEmpty operation checks whether the stack has any elements.

def is_empty(self):
    return len(self.items) == 0

9. Size Operation

def size(self):
    return len(self.items)

10. Menu-Driven Stack Program

def menu():
    stack = Stack()
    while True:
        print("\n--- STACK MENU ---")
        print("1. Push")
        print("2. Pop")
        print("3. Peek")
        print("4. Display")
        print("5. Size")
        print("6. Exit")
        choice = int(input("Enter choice: "))

        if choice == 1:
            item = input("Enter item to push: ")
            stack.push(item)
        elif choice == 2:
            stack.pop()
        elif choice == 3:
            print("Top element:", stack.peek())
        elif choice == 4:
            stack.display()
        elif choice == 5:
            print("Stack size:", stack.size())
        elif choice == 6:
            print("Exiting...")
            break

11. Applications of Stack

• Function calls: Managing function call and return addresses in recursion.
• Expression evaluation: Converting infix to postfix and evaluating postfix expressions.
• Undo operations: In text editors and software applications.
• Browser history: Back and forward navigation.
• Balanced parentheses: Checking if brackets are properly matched.
• Backtracking: In maze solving and puzzle games.
• Syntax parsing: In compilers and interpreters.

12. Checking Balanced Parentheses

def is_balanced(expression):
    stack = []
    pairs = {"(": ")", "{": "}", "[": "]"}
    for char in expression:
        if char in pairs:
            stack.append(char)
        elif char in pairs.values():
            if not stack or pairs[stack.pop()] != char:
                return False
    return len(stack) == 0

print(is_balanced("({[]})"))   # True
print(is_balanced("({[})"))    # False

13. Infix to Postfix Conversion

def infix_to_postfix(expression):
    precedence = {"+": 1, "-": 1, "*": 2, "/": 2, "^": 3}
    stack = []
    result = []
    for char in expression:
        if char.isalnum():
            result.append(char)
        elif char == "(":
            stack.append(char)
        elif char == ")":
            while stack and stack[-1] != "(":
                result.append(stack.pop())
            stack.pop()  # Remove (
        else:
            while stack and stack[-1] != "(" and precedence.get(char, 0) <= precedence.get(stack[-1], 0):
                result.append(stack.pop())
            stack.append(char)
    while stack:
        result.append(stack.pop())
    return "".join(result)

print(infix_to_postfix("A+B*C"))  # ABC*+

14. Postfix Expression Evaluation

def evaluate_postfix(expression):
    stack = []
    for char in expression:
        if char.isdigit():
            stack.append(int(char))
        else:
            b = stack.pop()
            a = stack.pop()
            if char == "+": stack.append(a + b)
            elif char == "-": stack.append(a - b)
            elif char == "*": stack.append(a * b)
            elif char == "/": stack.append(a / b)
    return stack[0]

print(evaluate_postfix("23*5+"))  # (2*3)+5 = 11

15. Stack Limitations

• Limited access: only the top element is accessible.
• Not suitable for searching or accessing middle elements.
• Array-based implementation has a fixed size if using static arrays.
• Recursive function calls can cause stack overflow for deep recursion.