[CS] 자료구조 - Stack <-> Queue

Stack 이용해 Queue 구현

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고 dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있다. 편의상 enqueue()에 사용할 stack을 instack이라고 하고 dequeue()에 사용할 stack을 outstack이라고 할 때 두개의 stack으로 queue를 구현하는 방법은 아래와 같다.

1. enqueue() : instack에 push() 이용해 데이터 저장
2. dequeue()
   • outstack이 비어 있다면 instack.pop() 먼저 하고 outstack.push()하여 instack에서 outstack으로 모든 데이터를 옮겨 넣는다. 그 결과로 가장 먼저 이용된 데이터는 outstack의 top에 위치하게 된다.
   • outstack.pop()을 하면 가장 먼저 온 데이터가 가장 먼저 추출된다.

이때의 시간 복잡도는 아래와 같다

• enqueue() : instack.push() 한번만 하면 되기에 시간복잡도 O(1)
• dequeue()
  • 최악의 경우 : outstack이 비어있을때, instack.pop() 한 이후에 outstack.push 해줘야 하기 때문에 O(n) 시간복잡도 갖는다.
  • outstack이 비어있지 않은 경우 outstack.pop()만 해주면 되기에 O(1) 시간복잡도 갖는다.

 

 

Queue 이용해 Stack 구현

stack의 push(), pop()을 위해 queue를 하나씩 사용해 구현할 수 있다. 편의상 push()에 사용할 큐를 q1, pop()에 사용할 큐를 q2라고 할 때, 두 개의 queue를 이용해 stack을 구현하는 방법은 아래와 같다.

1. push() : q1에 enqueue()를 하여 데이터 저장
2. pop()
   • q1에 저장된 데이터 1개 제외하고 모두 q2로 옮긴다.
   • q1에 남은 1개의 데이터를 dequeue()해서 가장 최근에 저장된 데이터 반환한다.

이때의 시간 복잡도는 아래와 같다

• push() : q1.enqueue() 한번만 하면 되기에 O(1)의 시간복잡도 갖는다.
• pop() : q1에 저장되어 있는 n개의 원소 중 n-1개를 q2로 옮겨야 하므로 O(n) 시간복잡도를 갖는다.

 

 

---

 

* https://kimmeh1.tistory.com/535