[자료구조] Queue, Stack, Deque

 자료구조 3가지를 다뤄볼 것이다. 코테 때도 자주 사용하니 알아두는 게 좋다. 

 

1 Queue

 먼저 queue이다. 큐라고 쓰기도 한다. 큐는 선입선출이라고 해서 먼저 들어온 것이 먼저 나오는 구조를 가지고 있다. 예를 들어서 열차가 터널을 지날 때 앞부분이 먼저 들어가고 앞부분이 먼저 나온다. 또 내가 먼저 동물원에 들어가기 위해 줄을 먼저 섰다면 먼저 들어가게 될 것이다.

그림 1 선형큐

 

 

그림 2 원형큐

 

연결리스트와 배열을 이용한 구현방식이 있다. 그리고 큐는 종류가 선형큐와 원형큐로 나뉘는데 원형큐는 배열로 구현했을 때의 단점을 해소하기 위해 만들어졌다.

 

 이 단점에 대해 간단히 설명하겠다. 보통 큐에서 앞쪽의 자료를 뺄 때 뒤에 있는 모든 원소를 한 칸씩 앞으로 움직이는 방법대신 front를 뒤로 한 칸 당긴다. 만약 자료가 1억 개가 넘어가고 한다면 원소를 옮기는데 꽤 많은 시간이 걸리는데 front만 한 칸 당기면 1번의 연산으로 끝낼 수 있다. 그런데 문제는 이러면 언젠가는 뒤에 새로운 원소를 넣을 공간이 없어질 것이다. 하지만 원형큐라면 그냥 한 바퀴 돌아서 앞에 남아있던 공간을 재사용하면 되기 때문에 이러한 문제가 해결된다.

 

 큐가 실제로 사용되는 곳을 생각해 보면 bfs(너비 우선 탐색) 사용되고, cpu의 스케줄러가 프로세서를 순서대로 실행하기 위해 사용한다. 그 외에도 다양한 곳에 사용한다.

 

2 Stack 

 다음은 Stack이다. 스택이라고도 한다. 스택은 큐와는 다르게 선입후출이다. 먼저 들어온 게 먼저 나오는 형태로 단순히 생각해서 동전을 하나씩 쌓은 상태에서 한 개씩 빼봐라고 한다면 위에 제일 마지막에 놓은 것부터 빼고 제일 처음 놓은 것을 제일 마지막에 뺄 것이다. 스택 또한 연결리스트와 배열로 구현이 가능하다. 

그림 3 스택

 

 스택이 실제로 사용되는 곳을 생각해 보면 프로세서를 메모리에 저장하고 쓸 때 함수를 스택처럼 쌓아서 쓰고, 다익스트라같은 최단거리를 찾는 알고리즘같은 곳에서도 사용한다.

 

3 Deque

 마지막으로 Deque를 보자. 덱이라고도 한다. 덱은 양방향 큐라고도 한다. 어떻게 보면 스택과 큐가 합쳐진 모양이기도 하다. 기존의 큐는 한 방향에서는 들어가는 것만 되고 다른 방향에서는 나오는 것만 가능했지만 덱은 두 방향 다 삽입과 삭제가 가능하다.

 

 덱은 이중연결리스트나 배열로 구현되고, 원형큐를 조금 바꾸면 덱으로 바꿀 수도 있다.

 

 덱이 실제로 사용되는 곳은 [1] work-steal이라는 걸 할 때 사용한다. 자신이 처리할 것이 없는 cpu 코어가 다른 cpu코어가 처리해야 할 일을 가져와서 처리하는 것이 work-steal이다.

 

 

---

 이러한 자료구조는 언어에 따라 이미 구현되어 있는 경우도 존재한다. 그러나 간단한 만큼 직접 구현해 보는 것도 좋을 것 같다. 그리고 이런 자료구조를 사용할 때 시간복잡도를 생각하면서 하는 게 좋다. 큐를 설명할 때 말한 것처럼 어떻게 구현하냐에 따라 시간복잡도가 꽤 많이 달라진다.

Reference

그림 1, 2 https://yoongrammer.tistory.com/46 [자료구조] 큐 (Queue) / yoongrammer / 2021

그림 3 https://velog.io/@sbinha/%EC%8A%A4%ED%83%9D-%ED%81%90 스택, 큐 (Stack, Queue) / Subin / 2020

[1] https://howudong.tistory.com/88  [자료구조] 덱 응용 : Work-Steal(A-steal) 알고리즘 구현  / 호우동 / 2022