[자료구조] 스택으로 큐, 큐로 스택 구현하기

스택과 큐의 원리를 이용하면 스택으로 큐를, 큐로 스택을 구현할 수 있다. 그 원리를 알아보고 코드로 구현해보자.

---

스택으로 큐 구현하기

큐는 선입선출의 구조로 데이터가 들어온 순서대로 나가게된다. 이를 스택 2개를 활용하여 구현할 수 있다. 아래의 그림을 보자.

스택 A와 B가 존재한다. 만약 큐에 PUSH하는 과정이 일어나면 스택 A에 PUSH를 한다. 이후 큐에 POP연산을 하게되면 스택 A의 모든 데이터를 스택 B로 옮긴다. 그렇게되면 스택 A의 역순으로 데이터가 저장될 것이고 스택 B를 POP하면 큐에 저장된 데이터 순서대로 출력될 것이다.

 

즉 스택 A는 인큐의 역할을 하게되고 스택 B는 디큐의 역할을 하게된다. PUSH를 하면 스택에는 가장 늦게 들어온 데이터가 맨 위에 쌓일 것이며 이를 다시 디큐의 역할을 하는 스택 B로 옮기면 큐의 구조(선입선출)로 저장된다.

 

큐로 스택 구현하기

스택은 후입선출의 구조로 가장 마지막에 들어온 데이터가 가장 먼저 나온다. 이를 큐의 특징을 활용하여 구현해보자.

위의 그림에는 한 개의 큐가 두 가지의 상태를 나타내고 있다. 위에있는 큐는 데이터를 PUSH한 상태이다. 이때 스택이라면 POP했을 때 3이 나와야하지만 큐는 1이 나오게된다. 따라서 아래의 큐를 보면 맨 첫 번째로 3이 나올때까지 POP하여 다시 큐에 PUSH한다. 이 과정을 통해 큐를 활용하여 스택의 순서에 맞게 데이터를 POP할 수 있다.

---

정리

스택과 큐라는 자료구조는 쉽다고 생각하였다. 하지만 스택과 큐에 대해 정확히 이해하고 있다면 위와 같은 문제들로 생각을 발전시킬 수도 있었을 것이다.