precedence = {'(': 0, '+': 1, '-': 1, '*': 2, '/': 2}


def infix2postfix(infix: str) -> str:
    ops = []
    postfix = []

    for c in infix:
        if c.isdigit():
            postfix.append(c)
        elif c == '(':
            ops.append(c)
        elif c == ')':
            while ops and ops[-1] != '(':
                postfix.append(ops.pop())
            ops.pop()
        else:
            while ops and precedence[ops[-1]] >= precedence[c]:
                postfix.append(ops.pop())
            ops.append(c)

    while ops:
        postfix.append(ops.pop())

    return ''.join(postfix)

def cal_postfix(postfix: str) -> int:
    stack = []

    for c in postfix:
        if c.isdigit():
            stack.append(int(c))
        else:
            b = stack.pop()
            a = stack.pop()
            stack.append(cal_op(c, a, b))  # 根据c属于什么op(+-/*)计算

    return stack.pop()

def infix2prefix(infix: str) -> str:
    infix = [{"(": ")", ")": "("}.get(c, c) for c in infix[::-1]]

    ops = []
    prefix = []

    for c in infix:
        if c.isdigit():
            prefix.append(c)
        elif c == '(':
            ops.append(c)
        elif c == ')':
            while ops and ops[-1] != '(':
                prefix.append(ops.pop())
            ops.pop()
        else:
            # 注意反转后是右结合，因此是>而不是>=
            while ops and precedence[ops[-1]] > precedence[c]:
                prefix.append(ops.pop())
            ops.append(c)

    while ops:
        prefix.append(ops.pop())

    return ''.join(reversed(prefix))

def cal_prefix(prefix: str) -> int:
    stack = []

    for c in reversed(postfix):
        if c.isdigit():
            stack.append(int(c))
        else:
            a = stack.pop()
            b = stack.pop()
            stack.append(cal_op(c, a, b))

    return stack.pop()

class CircularQueue:
    def __init__(self, size: int):
        self.size = size
        self.queue = [None] * size
        self.front = 0
        self.rear = 0

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        return self.front == self._next(self.rear)

    def enqueue(self, item: Any):
        self.queue[self.rear] = item
        self.rear = self._next(self.rear)

    def dequeue(self) -> Any:
        item = self.peek()
        self.front = self._next(self.front)
        return item

    def peek(self) -> Any:
        return self.queue(self.front)

    def _next(self, x):
        return (x + 1) % self.size