210420 - 2 - queue

스택 두 개 이용해 큐 구현하기(선입선출 알고리즘)

# 스택 두 개를 이용해 큐 구현하기 First In, First Out(선입선출)


#처리 과정

class MyStack(object):
    def __init__(self):
        self.lst = list()

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

    def pop(self):
        return self.lst.pop()

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

class MyQueue(object):
    def __init__(self, max_size):
        self.stack1 = MyStack()
        self.stack2 = MyStack()
        self.max_size = max_size

    def qsize(self):
        return self.stack1.size() + self.stack2.size() # 각 스택 내의 원소 수를 모두 더한다.

    def push(self, item):
        if self.stack1.size() == self.max_size: # 스택1에 이미 최대 갯수가 찬 상태라면 더 이상 넣을 수 없다.
            return False
        else:
            self.stack1.push(item) # 안 찼다면 넣고 완료 메시지를 보내라
            return True

    def pop(self):
        try:
            if self.stack2.size() == 0:  # 빼내는 함수, 스택2에 아무것도 없다면
                while self.stack1.size() != 0: # 스택1 원소수가 0일 때까지
                    self.stack2.push(self.stack1.pop()) # 스택1 원소를 뽑아서 스택2에 넣어라
            return self.stack2.pop() # 스택2에 값이 있으면 pop명령어에 스택2 원소를 뽑아내라. 
        except:
            # print('Empty Exception') # 스택1, 2에 아무것도 없으면 예외처리, false
            return False
 

# 입력 과정

n, max_size = map(int, input().strip().split(' ')) # 맨 처음 입력하는 명령횟수, 큐의 최대 사이즈 

put_in = MyQueue(max_size) # myqueue 클래스를 사용하겠다고 선언, 인스턴스에 저장, 최대 사이즈를 집어 넣고 시작

for i in range(n): # 명령횟수만큼 반복문 실행, 
    order = input() # 명령어를 넣는다
    order_detail = order.split(' ') # push의 경우 명령어와 값을 입력해야 하므로 잘라준다.
    
    if order_detail[0] == 'SIZE': # size 명령어일 때, 인스턴스로 클래스 내 함수 호출해 사이즈 확인
        print(put_in.qsize())
    
    elif order_detail[0] == 'PUSH': # push 명령어일 때, push 함수 호출하고 값도 넣어준다. 
        print(put_in.push(int(order_detail[1])))
        
    elif order_detail[0] == 'POP': # pop명령어일 때, pop함수 호출. 
        print(put_in.pop())