3️⃣

Stack 두 개를 이용하여 Queue를 구현해 보세요.

[면접 TIP]

어디서도 배운적은 없지만 의외로 가끔 나와서 당황했던 면접 질문입니다. 따로 준비해 가지 않으면 현장에서 바로 떠올리기 힘들 수 있지만, 한 번만 준비했다면 쉽게 답할 수 있습니다. stack 두 개를 사용하여 enqueue와 dequeue를 구현하는 것에 초점을 맞춰서 문제를 해결하면 됩니다. 사실 이런 문제는 답이 다양하고, 답 자체가 중요하기 보단 답을 찾아가는 과정을 더 중요하게 보기 때문에, 풀이를 외우기보단 접근 방식을 주의깊게 보시길 바랍니다.

[핵심 답변]

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있습니다.

편의상 enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 칭하겠습니다. 두 개의 stack으로 queue를 구현하는 방법은 다음과 같습니다.

enqueue() ::  instack에 push()를 하여 데이터를 저장합니다.

dequeue() ::

만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 옮겨 넣습니다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.

outstack.pop()을 하면 가장먼저 왔던 데이터가 가정 먼저 추출된다.(FIFO)

[코드 작성]

class Queue(object):
    def __init__(self):
        self.instack=[]
        self.outstack=[]

    def enqueue(self,element):
        self.instack.append(element)

    def dequeue(self):
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()
Python
복사

[꼬꼬무 문답]

Q. 시간복잡도는 어떻게 되는지 설명해 주세요.