박종훈 알고리즘 블로그

(알고리즘 문제) 스택 두 개로 큐 만들기

스택 두 개로 큐 만들기 코딩인터뷰 완전분석 - 게일 라크만 맥도웰


스택으로 큐: 스택 두 개로 큐 하나를 구현한 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

categories: 스터디-알고리즘

tags: 파이썬 , 알고리즘 , , Queue , 스택 , Stack