Stack Data Structure

# CHAPTER 11

Stack Data Structure #

1. Introduction #

2. Learning Objectives #

• Define the LIFO principle.

• Execute the three core Stack operations: push(), pop(), and peek().

• Implement a Stack using both Arrays and Linked Lists.

• Analyze the Time and Space Complexity of Stack operations.

• Build a real-world "Undo" mechanism.

3. The Core Operations #

1. 1. push(data): Places a new element onto the top of the Stack.

1. 2. pop(): Removes and returns the element currently at the top of the Stack.

1. 3. peek() (or top()): Looks at the top element without actually removing it.

1. 4. isEmpty(): Returns True if the Stack has zero elements.

4. Implementation 1: Array-Based Stack #

// C Example: Building a Stack using a static Array
#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = -1; // -1 means the stack is totally empty!

void push(int data) {
    if (top >= MAX - 1) {
        printf("Stack Overflow! The array is completely full.\n");
        return;
    }
    top++; // Move the pointer up
    stack[top] = data; // Drop the data in
}

int pop() {
    if (top < 0) {
        printf("Stack Underflow! Nothing to pop.\n");
        return -1;
    }
    int popped_data = stack[top];
    top--; // Move the pointer down (the data is overwritten later)
    return popped_data;
}

5. Implementation 2: Linked List-Based Stack #

// Java Example: Building a Stack using a Linked List
class Node {
    int data;
    Node next;
    public Node(int d) { data = d; next = null; }
}

public class CustomStack {
    Node top = null; // The Head of the list

    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top; // New node points to old top
        top = newNode; // New node becomes the absolute top
    }

    public int pop() {
        if (top == null) {
            System.out.println("Stack Underflow!");
            return -1;
        }
        int poppedData = top.data;
        top = top.next; // Top pointer drops down to the next node!
        return poppedData;
    }
}

6. Complexity Analysis #

7. Real-World Applications #

1. 1. The Undo Button: (Ctrl+Z). Every time you type a word in MS Word, it is push()ed to a Stack. When you press Undo, the system pop()s the most recent word and deletes it.

1. 2. Compiler Syntax Checking: How does the compiler know if your { [ ( ) ] } brackets are perfectly balanced? It uses a Stack!

1. 3. The OS Call Stack: As discussed in Chapter 6, computers use Stacks natively in RAM to manage recursive function calls.

8. Mini Project: Balancing Parentheses #

# Python Example: Parentheses Checker using a List as a Stack
def is_balanced(expression):
    stack = [] # Python lists have native O(1) push (append) and pop
    brackets = {')': '(', '}': '{', ']': '['} # Hash map for fast lookup
    
    for char in expression:
        if char in ['(', '{', '[']:
            stack.append(char) # PUSH opening brackets
        elif char in [')', '}', ']']:
            if len(stack) == 0:
                return False # Underflow! More closing than opening.
                
            top_element = stack.pop() # POP the last opened bracket
            
            # Check for a mismatch
            if brackets[char] != top_element:
                return False
                
    # If the stack is empty at the end, it's perfectly balanced!
    return len(stack) == 0

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

9. Common Mistakes #

• Stack Underflow: Calling pop() on an empty stack. If you don't wrap your pop() function in an if (isEmpty()) check, attempting to extract data from a negative array index or a NULL pointer will violently crash your software.

10. Best Practices #

• Use Standard Libraries: In modern programming, never write a Stack from scratch unless you are in an interview. Use java.util.Stack, Python's list, or C++ std::stack. They are heavily optimized by compiler engineers.

11. Exercises #

1. 1. Trace the operations on paper: push(5), push(10), pop(), push(20), peek(). What is the value returned by peek()?

1. 2. Write a function that uses a Stack to reverse a String. *(Hint: Push every character into the stack, then Pop them all out! Because of LIFO, they will come out backward!).*

12. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Implement a MinStack class that supports push(), pop(), top(), and retrieving the minimum element in constant O(1) time." *(Hint: You must maintain TWO stacks simultaneously. One for normal data, and one strictly tracking the current minimum value).*

• *System Design:* "Design a Stack capable of infinite growth utilizing a raw Array structure. Explain the internal resizing logic." *(Answer: It's essentially implementing a Dynamic Array under the hood!).*

Common Pitfalls:

• Calling pop() inside a loop without checking if the stack isEmpty(). If the logic iterates one too many times, the Underflow Exception will result in an immediate whiteboard failure.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #