ABOUT
home
무료 콘텐츠
home
3️⃣

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

[면접  TIP]
어디서도 배운적은 없지만 의외로 가끔 나와서 당황했던 면접 질문입니다. 따로 준비해 가지 않으면 현장에서 바로 떠올리기 힘들 수 있지만, 한 번만 준비했다면 쉽게 답할 수 있습니다. stack 두 개를 사용하여 enqueue와 dequeue를 구현하는 것에 초점을 맞춰서 문제를 해결하면 됩니다. 사실 이런 문제는 답이 다양하고, 답 자체가 중요하기 보단 답을 찾아가는 과정을 더 중요하게 보기 때문에, 풀이를 외우기보단 접근 방식을 주의깊게 보시길 바랍니다.
[핵심 답변]
queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고, dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있습니다.
편의상 enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 칭하겠습니다. 두 개의 stack으로 queue를 구현하는 방법은 다음과 같습니다.
1.
enqueue() :: instack에 push()를 하여 데이터를 저장합니다.
2.
dequeue() ::
a.
만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를 하여 instack에서 outstack으로 모든 데이터를 옮겨 넣습니다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.
b.
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. 시간복잡도는 어떻게 되는지 설명해 주세요.

 뒤로 가기