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

    def push(self, x):
        self._data.append(x)

    def pop(self):
        if not self._data:
            return None
        return self._data.pop()

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

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

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


def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    openers = set(pairs.values())
    stack = Stack()
    for ch in s:
        if ch in openers:
            stack.push(ch)
        elif ch in pairs:
            if stack.pop() != pairs[ch]:
                return False
    return stack.is_empty()


class Queue:
    def __init__(self):
        self._in = []
        self._out = []

    def enqueue(self, x):
        self._in.append(x)

    def dequeue(self):
        if not self._out:
            while self._in:
                self._out.append(self._in.pop())
        if not self._out:
            return None
        return self._out.pop()

    def is_empty(self):
        return not self._in and not self._out

    def size(self):
        return len(self._in) + len(self._out)


class MinStack:
    def __init__(self):
        self._data = []
        self._mins = []

    def push(self, x):
        """Push x, keeping an auxiliary min stack so get_min stays O(1)."""
        # TODO: append x to _data and push the running minimum onto _mins
        pass

    def pop(self):
        if not self._data:
            return None
        self._mins.pop()
        return self._data.pop()

    def top(self):
        if not self._data:
            return None
        return self._data[-1]

    def get_min(self):
        """Return the current minimum in O(1), or None if empty."""
        # TODO: return the top of the auxiliary _mins stack, or None if empty
        pass