stacks

from collections import deque

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

    def push(self, item):
        """Push an item onto the stack."""
        self.stack.append(item)

    def pop(self):
        """Pop an item from the stack. Returns None if the stack is empty."""
        if not self.is_empty():
            return self.stack.pop()
        return None

    def peek(self):
        """Peek at the top item of the stack without removing it."""
        if not self.is_empty():
            return self.stack[-1]
        return None

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.stack) == 0

    def size(self):
        """Return the size of the stack."""
        return len(self.stack)

    def clear(self):
        """Clear all items in the stack."""
        self.stack.clear()

    def print_stack(self):
        """Print all elements in the stack."""
        print(self.stack)


def reverse_stack(stack):
    """Reverse a stack using recursion."""
    if stack.is_empty():
        return
    top = stack.pop()
    reverse_stack(stack)
    insert_at_bottom(stack, top)

def insert_at_bottom(stack, item):
    """Helper function to insert an item at the bottom of the stack."""
    if stack.is_empty():
        stack.push(item)
    else:
        top = stack.pop()
        insert_at_bottom(stack, item)
        stack.push(top)


def is_balanced(expression):
    """Check if the parentheses in the expression are balanced."""
    stack = Stack()
    for char in expression:
        if char in '([{':
            stack.push(char)
        elif char == ')' and (stack.is_empty() or stack.pop() != '('):
            return False
        elif char == ']' and (stack.is_empty() or stack.pop() != '['):
            return False
        elif char == '}' and (stack.is_empty() or stack.pop() != '{'):
            return False
    return stack.is_empty()


def dfs_stack(graph, start):
    """
    Perform DFS traversal of a graph using a stack.
    :param graph: A dictionary representing the graph (adjacency list).
    :param start: The starting node for DFS traversal.
    :return: A list of nodes in the order they were visited.
    """
    visited = set()
    stack = [start]
    traversal_order = []

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

    return traversal_order


def bfs_queue(graph, start):
    """
    Perform BFS traversal of a graph using a queue.
    :param graph: A dictionary representing the graph (adjacency list).
    :param start: The starting node for BFS traversal.
    :return: A list of nodes in the order they were visited.
    """
    visited = set()
    queue = deque([start])
    traversal_order = []

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            traversal_order.append(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

    return traversal_order


def is_palindrome(s):
    """
    Check if a string is a palindrome using a stack.
    :param s: The string to check.
    :return: True if the string is a palindrome, False otherwise.
    """
    stack = []
    # Push each character onto the stack
    for char in s:
        stack.append(char)

    # Check if the string is a palindrome by comparing characters
    for char in s:
        if char != stack.pop():
            return False
    return True


def sort_stack(stack):
    """
    Sort a stack using only another stack for auxiliary storage.
    :param stack: The stack to be sorted.
    :return: The sorted stack.
    """
    auxiliary_stack = []

    while stack:
        current = stack.pop()

        # Move elements from auxiliary stack back to stack if they are greater than current
        while auxiliary_stack and auxiliary_stack[-1] > current:
            stack.append(auxiliary_stack.pop())

        # Push the current element to the auxiliary stack
        auxiliary_stack.append(current)

    # Move all elements back to the original stack
    while auxiliary_stack:
        stack.append(auxiliary_stack.pop())

    return stack


class MinStack:
    def __init__(self):
        """
        Initialize the stack and the auxiliary stack to keep track of minimum elements.
        """
        self.stack = []
        self.min_stack = []

    def push(self, x):
        """
        Push an element onto the stack.
        :param x: The element to be pushed onto the stack.
        """
        self.stack.append(x)
        # Push the minimum element onto the min_stack
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)

    def pop(self):
        """
        Pop the top element from the stack.
        :return: The popped element.
        """
        if self.stack:
            popped_value = self.stack.pop()
            if popped_value == self.min_stack[-1]:
                self.min_stack.pop()
            return popped_value
        return None

    def top(self):
        """
        Get the top element of the stack.
        :return: The top element of the stack.
        """
        return self.stack[-1] if self.stack else None

    def get_min(self):
        """
        Retrieve the minimum element in constant time.
        :return: The minimum element in the stack.
        """
        return self.min_stack[-1] if self.min_stack else None


# Example Use Cases

# 1. Test the Stack class
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Stack operations:")
print(stack.peek())  # Output: 30
print(stack.pop())   # Output: 30
print(stack.size())  # Output: 2
stack.print_stack()  # Output: [10, 20]

# 2. Test DFS
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print("\nDFS traversal:", dfs_stack(graph, 'A'))  # Output: ['A', 'C', 'F', 'E', 'B', 'D']

# 3. Test BFS
print("\nBFS traversal:", bfs_queue(graph, 'A'))  # Output: ['A', 'B', 'C', 'D', 'E', 'F']

# 4. Test Palindrome Check
print("\nIs 'racecar' a palindrome?", is_palindrome('racecar'))  # Output: True
print("Is 'hello' a palindrome?", is_palindrome('hello'))  # Output: False

# 5. Test Reversing a Stack
print("\nReversing stack:")
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
reverse_stack(stack)
stack.print_stack()  # Output: [3, 2, 1]

# 6. Test Balanced Parentheses
expression = "{[()()]}"
print("\nIs the expression balanced?", is_balanced(expression))  # Output: True
expression = "{[(])}"
print("Is the expression balanced?", is_balanced(expression))  # Output: False

# 7. Test Sorting a Stack
stack = [5, 2, 9, 1, 5, 6]
print("\nSorted stack:", sort_stack(stack))  # Output: [1, 2, 5, 5, 6, 9]

# 8. Test MinStack
min_stack = MinStack()
min_stack.push(3)
min_stack.push(4)
min_stack.push(2)
min_stack.push(5)
print("\nMinStack get_min:", min_stack.get_min())  # Output: 2
min_stack.pop()
print("MinStack get_min after pop:", min_stack.get_min())  # Output: 2
min_stack.pop()
print("MinStack get_min after pop:", min_stack.get_min())  # Output: 3