(알고리즘 문제) 스택 두 개로 큐 만들기
스택 두 개로 큐 만들기 코딩인터뷰 완전분석 - 게일 라크만 맥도웰
스택으로 큐: 스택 두 개로 큐 하나를 구현한 MyQueue 클래스를 구현하라
스택 두 개를 이용해서 엘리먼트들을 옮기면서 마지막 엘리먼트를 넘겨주나?
기본적인 Queue는 FIFO 이기 때문에
Queue 에서 필요한 기능은
- push() : 뒤에 넣음
- pop() : 앞에서 꺼내감
일 것 같다.
이 때 stack 이라고 자료구조를 명시해주었기 때문에 array에 직접 접근 하는 것이 아닌 stack의 함수만 이용해야 한다고 가정하고 문제를 풀어나가 보았다.
class Stack:
def __init__(self):
self.stack = []
def push(self, value):
return self.stack.append(value)
def pop(self):
if not self.stack:
return None
return self.stack.pop()
def is_empty(self):
return len(self.stack) == 0
class MyQueue:
def __init__(self):
self.main_stack = Stack()
self.temp_stack = Stack()
def push(self, value):
self.main_stack.push(value)
def pop(self):
self.transfer(self.main_stack, self.temp_stack)
if self.temp_stack:
return self.temp_stack.pop()
else:
return None
self.transfer(self.temp_stack, self.main_stack)
def transfer(self, src, dest):
if dest.is_empty():
while not src.is_empty():
dest.push(src.pop())
queue = MyQueue()
queue.push(1)
queue.push(2)
queue.push(3)
print(queue.pop()) # 출력: 1
print(queue.pop()) # 출력: 2
queue.push(4)
print(queue.pop()) # 출력: 3
print(queue.pop()) # 출력: 4
print(queue.pop()) # 출력: None