우선순위 스택은 왜 없을까?

서론

턴제 게임을 개발하다, 우선순위 스택이 필요한 순간이 생겼었다.

우리 게임은 스택을 기반으로 플레이어와 적의 스킬을 관리했는데, 상태이상을 스킬화하면서 우선순위를 만들 필요가 생긴 것.

 

당연히 처음엔 스택 4개(당시 상태이상이 3가지였다.)를 동시에 운용하는 방식을 생각했는데, 문득 우선순위 큐도 있는데, 우선순위 스택은 없나?하는 생각이 들었다.

 

오늘은 그에 관한 간단한 고찰이다. 

---

큐, 스택, 우선순위 큐

거창하게 큐와 스택의 차이부터 설명할 수도 있지만, 이는 그리 중요하진 않으니 간단히 넘어가고 바로 본론으로 들어가보겠다.

 

스택은 마지막에 들어간 게 먼저 나오고 (LIFO), 큐는 먼저 들어간 게 먼저 나온다 (FIFO).

 

큐와 스택의 차이는 위처럼, 먼저 넣은 게 먼저 나오냐, 나중에 나오냐의 차이다.

 

그럼 우선순위 큐는 무엇일까?

 

 

우선순위 큐는 개념적으로, 위처럼 값을 넣은 순서가 아닌 가중치에 따라 정렬하는 큐다.

위의 사진에선 8부터 2까지 차례로 넣었지만, 정렬 기준(작은 수가 먼저)에 따라 1이 맨 앞에, 8이 맨 뒤에 온 예시다.

 

구현 방식이 어떻고는 너무 내용이 빠지니, 개념적으로 이정도만 알고 가자.

---

우선순위 큐 vs 우선순위 스택

관념적으로 내가 이 부분이 헷갈렸던 건, 우선순위 큐는 우선순위가 같다면 FIFO를 보장한다고 착각했기 때문이다.

 

Microsoft Learn, PriorityQueue<TElement,TPriority> 클래스 중 발췌. 왜 보장하지 않는지는 힙에 대해 알아보자.

 

우선순위 큐는, 우선순위가 같은 요소에 대해 선입선출을 보장하지 않는다. 애초에, 큐조차 아니다. 우선순위 큐는 주로 힙을 기반으로 구현되니까.

삽입 순서를 별도로 표기하여 FIFO를 보장하는 우선순위 큐를 만들 수도 있겠지만, 이는 어디까지나 응용일 뿐, 본질은 아니다.

 

당연히, 우선순위 스택이란 건 존재하지 않는다. 하지만 LIFO를 보장하는 우선순위 큐를 만들 수는 있다.

---

그럼 왜 우선순위 큐라는 이름이 붙었을까?

그럼 왜 큐와 전혀 다른 자료구조에 큐라는 이름이 붙었을까? 이는, Queue라는 단어가 대기열을 뜻하기 때문이다.

 

풀어쓰자면 이건 대기열인데, VIP가 먼저 이동하는 대기열이야.라는 뜻에서 Queue라는 단어가 사용되었을 뿐, 우선순위가 같다는 전제 하에 깔리는 선입선출은 해당하지 않았던 것이다. 즉, 엄밀한 정의와 구조적 유사함에서 나온 큐라는 단어가 아니라, 관념적으로, 그러한 것들을 퉁쳐서 부르는 큐에서 나온 것이다.

 

그러니, 애초에 우선순위 큐는 큐가 아니니 우선순위 스택 또한 존재하지 않는다는 것. 꽤나 허무한 결말이었다.

---

마무리

우선순위 스택이 없는 이유를 찾은 동기는 단순한데, 우선순위 큐는 클래스로 지원해주는데 우선순위 스택은 없으니까 만들기 귀찮아서였다. 만들려면 금방 만들 수야 있었겠지만, 그냥 '아 왜 안 만들어놨냐'하고 불평만 하는 것보단, 이유를 알아보는 게 더 도움되지 않겠나?

 

물론, 우선순위에 따르되 같은 경우 LIFO인 자료구조를 따로 만들고 사용할 순 있을 것이다. 다만, 그럼에도 사람들이 잘 쓰지 않는, 복잡한 자료구조가 필요한 상황이 왔다면, 정말 그것 외엔 해결법이 없는지 돌아볼 필요는 있을 것이다. 나 역시 게임 개발 도중 이러한 문제를 맞닥뜨려 공부한 거지만, 결국 구조를 정리해서 구현하지 않고 문제를 해결했으니까.

 

어찌보면 개발에 도움되지 않는 지식일 수도 있지만, 단순히 생각하지 않는 것과 왜 없는지 아는 것은 천지차이가 아니겠는가? 이러한 것들이 쌓여 실력이 되니까, 아까운 시간은 아니었다. 솔직히 말하자면, 꽤 재밌어서 오히려 좋았다.

---

참고 자료

• Microsoft, "PriorityQueue<TElement,TPriority> 클래스", Microsoft Learn, https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.priorityqueue-2?view=net-8.0
• Duong Phan, "Priority stack in C++", stackoverflow, 2019. 3. 17., https://stackoverflow.com/questions/55207148/priority-stack-in-c