[자료구조] 큐 (Queue)
큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조입니다.
실제 예로 매표소 대기열에서 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황과 비슷합니다.
나중에 집어넣은 데이터가 먼저 나오는 스택(Stack)과는 반대되는 개념입니다.
큐 표현
큐는 FIFO(First In First Out) / LILO(Last In Last Out) 순서를 따릅니다.
- FIFO : 처음 들어온 값이 처음에 나가는 것
- LILO : 마지막에 들어온 값이 마지막에 나가는 것
큐에 끝(Rear)에서 요소를 추가하는 작업을 enqueue라고 하며 큐에 맨 앞(Front)에서 요소를 제거하는 작업을 dequeue라고 합니다.
가득 찬 큐에 요소를 추가하려고 할 때 Overflow가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 Underflow가 발생합니다.
기본 동작
- enqueue() - 큐에 끝(rear)에 항목을 추가
- dequeue() - 큐에 맨 앞(front)에 항목을 제거
- peek() - 큐에 맨 앞(front)에 있는 항목을 반환
- isfull() - 큐가 가득 찼는지 확인
- isempty() - 큐가 비어 있는지 확인.
시간 복잡도 (Time complexity)
| Operation | Average | Worst |
| Access | Θ(n) | O(n) |
| Search | Θ(n) | O(n) |
| Insert (enqueue) | Θ(1) | O(1) |
| Delete (dequeue) | Θ(1) | O(1) |
구현
큐를 구현하는 방법에는 두 가지가 있습니다.
- 배열 사용
- 장점 : 구현하기 쉬움.
- 단점 : 크기가 동적이 아님. 런타임 시 필요에 따라 늘어나거나 줄어들지 않음.
- 연결 리스트 사용
- 장점 : 크기가 동적임. 런타임시 필요에 따라 크기가 확장 및 축소될 수 있음.
- 단점 : 포인터를 위한 추가 메모리 공간이 필요함.
종류
큐에는 선형과 환형이 있습니다.
선형 큐 (Linear Queue)
기본적인 큐의 형태로써 막대 모양으로 된 큐입니다.
배열로 구현 시 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있고 많은 수의 enqueue 및 dequeue 작업이 있는 경우 어느 시점에서 큐가 비어있어도 자료를 삽입하지 못하는 경우가 발생합니다.
환형 큐 (Circular Queue)
선형 큐의 문제점을 보완한 것이 환형 큐입니다.
환형 큐는 1차원 배열 형태의 큐를 원형(Circular)으로 구성하여 배열의 처음과 끝을 연결하여 만듭니다.
원형 큐라고도 합니다.
사용 사례
- 어떠한 작업/데이터를 순서대로 실행/사용하기 위해
대기시킬 때 사용합니다.
ex) CPU 스케줄링, 디스크 스케줄링 - 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 많이 사용합니다. (비동기 전송)
ex) IO 버퍼, 파이프, 파일 IO
참고: www.geeksforgeeks.org/queue-data-structure/
