[CS / Queue & Stack] ep07. Stack 두 개를 이용하여 Queue를 구현해 보세요

🤔 면접 질문

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

 

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

 

편의상 enqueue()에 사용할 스택을 instack이라 부르고, dequeue에 사용할 stack을 outstack이라 명명하겠습니다. 이 두 개의 stack으로 queue를 구현하는 방법을 설명드리겠습니다.

 

1. enqueeue() 

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

 

2. dequeue()

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

 

  b. outstack.pop을 하면 가장 먼저 왔던 데이터가 가장 먼저 추출됩니다. (=FIFO)

 

  c. python을 통해 구현한 코드는 다음과 같습니다.

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()

 

 

 

💡 면접🐕🍯 tip

:  따로 준비해가지 않는다면 현장에서 머리 위에 404 error가 뜰만한 질문이지만, 많이 할 필요는 없고 한 번만 준비해 간다면 쉽게 답할 수 있는 문제이다. stack 두 개를 이용하여 enqueue와 dequeue를 구현하는 것에 초점을 맞추고 문제를 해결하면 된다. 사실 이런 문제는 답 자체가 중요하기 보단 답을 찾아가는 과정을 더 중요하게 보기 때문에, 풀이를 외우기 보단 접근 방식을 주의 깊게 볼 필요가 있다.

 

 

 

🚀 심화 면접 질문

 

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

 

A1. 구현한 queue의 시간 복잡도는 다음과 같습니다.

• enqueue() : instack.push()를 한번만 하면 되기 때문에 시간복잡도 O(1)입니다.
• dequeue() : 두 가지 경우를 따져봐야 합니다. worst case는 outstack이 비어있는 경우입니다. 이 때는 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 해줘야 합니다. 따라서 총 2*n 번의 operation이 실행되어야 하므로 O(n)의 시간복잡도를 갖습니다.
• 하지만 outstack이 비어있지 않는 경우에는 outstack.pop()만 해주면 됩니다. 이는 O(1)의 시간복잡도를 갖습니다. 이를 종합했을 때, amortized O(1)의 시간복잡도를 갖는다고 할 수 있습니다.
• enqueue() 👉 O(1)
• dequeue() 👉 O(1)