큐는 선입 선출(First In First Out : FIFO) 형태의 자료구조이다.
큐는 들어온 순서를 이용하는 기능에서 적절하게 사용할 수 있다.
선착순 대기열 기능이 좋은 예시이다.
어떠한 서비스를 이용하고자 하는 사용자 4명이 있다고 가정해보자.
이 4명은 이용신청을 한 순서대로 1~4번의 번호가 붙어있다.
만약 이 4명을 스택을 이용해서 관리한다면 가장 늦게 도착한 4번이 가장 먼저 처리되는 상황이 발생한다.
큐는 스택과는 반대로 먼저 삽입된 데이터가 먼저 처리(= 삭제) 되기 때문에 위와 같은 불합리한 상황을 발생시키지 않는다.
큐는 대부분의 프로그래밍 언어에서 라이브러리로 지원되고 있다.
C++ / Java의 경우 push(삽입), pop(삭제), front(현재 값)의 메소드를 이용해 조작할 수 있다.
python의 경우 기본 자료형인 list를 이용할 수도 있지만, 아래와 같은 문제로 인해 list 형태는 불필요한 연산을 하게 된다.
위와 같은 불필요한 연산을 줄이기 위해 python에서는 연결 리스트 기반의 deque 클래스를 import 하여 이용하게 되고 append(삽입), popleft(삭제) 메소드를 이용하게 된다.
만약 배열 등을 이용하여 직접 큐의 기능을 구현한다면 투 포인터 기법을 이용하여 아래와 같이 구현할 수 있지만, 결국 한계가 있는 방식이다.
그러므로 일반적으로 큐는 투 포인터를 이용한 환형 큐, 또는 아래의 연결 리스트 방식이 권장된다.
실제로 스택을 이용하여 구현 가능한 기능으로는
- 너비 우선 탐색(BFS)
- 대기열 관련 스케쥴러(ex: 페이지 교체 알고리즘의 FIFO 방식 등)
등이 있다.
우선순위 큐(Priority Queue)의 경우 이름에는 큐가 들어가지만 실제 내부 자료구조는 힙(Heap)을 이용해 구현되어 있다.
즉, 본 포스팅의 큐와 우선순위 큐는 전혀 다른 자료구조이다.
힙에 대해서는 이후 트리, 균형 트리 내용을 포스팅 한 뒤 설명하겠다.
'알고리즘 온라인 저지 > 알고리즘 | 자료구조' 카테고리의 다른 글
| 알고리즘 : 깊이 우선 탐색(DFS) (0) | 2022.08.08 |
|---|---|
| 알고리즘 : 너비 우선 탐색(BFS) (0) | 2022.07.15 |
| 자료구조 트리 (tree) (0) | 2022.06.27 |
| 자료구조 그래프 (graph) (0) | 2022.06.27 |
| 자료구조 스택 (stack) (0) | 2022.06.27 |
