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):
        self._data.append(x)
        if not self._mins or x <= self._mins[-1]:
            self._mins.append(x)
        else:
            self._mins.append(self._mins[-1])

    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):
        if not self._mins:
            return None
        return self._mins[-1]


def next_greater(nums):
    """Return a list where each entry is the next greater element to the right, or -1."""
    # TODO: use a monotonic stack of indices; pop while current value is greater
    pass