def quick_sort(arr):
    def sort(low, high):
        if low >= high:
            return
        mid = partition(low, high)
        sort(low, mid-1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high)//2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low += 1
                high -= 1
        return low
    return sort(0,len(arr)-1)

def merge_sort(arr):
    # 길이가 1일때 재귀 탈출
    if len(arr)<2:
        return arr

    # devide
    mid = len(arr)//2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    # conquer
    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1

    # low_arr 혹은 high_arr이 비었을 떄 뒤에다 털어준다.
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]

    return merged_arr

# 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 swap
# 한번 루프를 돌때마다 최대값이 맨 앞에 오게 된다.
# 정렬때마다 제외되는 데이터가 많아진다.
def bubble_sort(arr):
    for i in range(len(arr)-1, 0, -1):
        for j in range(i):
         if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

def insertion_sort(my_list):
    for i in range(1,len(my_list)):
        key = my_list[i]
        j = i-1
        while j>=0 and my_list[j] > key:
            my_list[j+1] = my_list[j] # 앞의 값의 인덱스를 올려준다.
            j -= 1
        my_list[j+1] = key
    return my_list

class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x:int) -> None:
        self.stack1.append(x)

    def pop(self) -> int:
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()


    def peek(self) -> int:
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())

        return self.stack2[-1]

    def empty(self):
        return (not self.stack1) and (not self.stack2)

queue = MyQueue()
queue.push(1)
queue.push(2)
queue.push(3)

queue.pop() # 1

queue.push(4)
queue.push(5)
queue.push(6)

queue.pop() # 2
queue.pop() # 3
queue.pop() # 4

from collections import deque

class MyStack:

    def __init__(self):
        self.q = deque()


    def push(self, x: int) -> None:
        self.q.append(x)
        for i in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0