[모두가 기술 면접에 합격하는 그날까지]
https://github.com/Lee-Jin-Hyeok/technical-interview-question
목차
- 큐(Queue)란?
- 큐의 용어
- 큐의 종류
3-1. 선형 큐 (Linear Queue)
3-2. 원형 큐 (Circular Queue)
3-3. 우선순위 큐 (Priority Queue)
3-4. 데큐 (Double-Ended Queue) - 큐의 구현
- 큐의 사용
5-1. 실생활에서의 큐
5-2. 프로그래밍에서의 큐 - 마무리
1. 큐(Queue)란?
큐는 선입선출 구조의 자료구조입니다.
선입선출이란 먼저 들어간 자료가 마지막에 나온다는 뜻으로,
영어로는 FIFO(First In First Out)라고 하며 흔히 '피포' 자료구조라고 읽습니다.
자료 A -> 자료 B -> 자료 C 순서대로 삽입 연산이 이루어지면,
자료 A -> 자료 B -> 자료 C 순서대로 삭제 연산이 이루어집니다.
FIFO 대신 LILO를 쓸 수도 있으나 보통 FIFO를 선호합니다.
2. 큐의 용어
- Enqueue
큐에서 삽인 연산을 할때 사용되는 명령으로,
'인큐', '엔큐'라고 많이 읽습니다.
- Dequeue
큐에서 삭제 연산을 할때 사용되는 명령으로,
'디큐'라고 많이 읽습니다.
- Rear
큐의 뒤쪽이라는 뜻으로 큐에서 삽입이 되는 위치를 말한다.큐를 뱀이라고 봤을 때 뱀의 꼬리에 삽입한다고 생각하면 쉽습니다.
- Front
큐의 앞쪽이라는 뜻으로 큐에서 삭제가 되는 위치를 말한다.
- Queue Overflow
Stack Overflow와 마찬가지로 큐가 가득찬 상태에서 Enqueue 연산을 실행하면 발생합니다.
- Queue Underflow
Stack Underflow와 마찬가지로 큐가 빈 상태에서 Dequeue 연산을 실행하면 발생합니다.
3. 큐의 종류
3-1. 선형 큐 (Linear Queue)
선형 큐가 일반적으로 생각할 수 있는 큐입니다.
이름을 선형 큐라고 한 이유는 원형(환형) 큐가 존재하기 때문입니다.
따라서 그냥 일반적인 큐라고 생각하시면 될 것 같습니다.
3-2. 원형 큐 (Circular Queue)
원형 큐가 만들어진 계기는 다음과 같습니다.
선형 큐의 경우에는 Enqueue 연산을 계속 진행하면 Queue Overflow가 발생하게 됩니다.
그런데 선형 큐를 배열로 구현하고 Dequeue 연산시 발생하는 배열의 빈 공간을 대체하지 않는다면
큐에 빈 공간이 남아 있음에도 불구하고 Queue Overflow가 발생하게 됩니다.
이러한 현상 때문에 배열의 마지막 인덱스까지 요소가 차게 되면
배열의 첫 인덱스로 Rear 위치를 옮기는 방식을 사용하게 되었습니다.
원형 큐는 선형 큐와는 다르게 Queue Overflow가 발생하지 않는다는 점을 가지고 있습니다.
원형 큐의 동작 방식은 다음과 같습니다.
- Enqueue 연산시 Rear의 다음 위치에 자료를 삽입한다.
- Dequeue 연산시 Front의 다음 위치에 있는 자료를 삭제한다.
- Rear + 1 = Front 일 경우 큐가 가득찬 걸로 인지한다.
따라서 원형 큐의 경우에는 공간이 4이면 총 3개의 자료를 삽입할 수 있습니다. - Rear = Front 일 경우 큐가 빈 것으로 인지한다.
3-3. 우선순위 큐 (Priority Queue)
일반적인 큐의 경우에는 무조건 선입선출의 원칙을 따릅니다.
하지만 우선순위 큐는 무조건 선입선출이 아니라 자료의 우선순위에 따라서
자료를 정렬하고 우선순위가 가장 높은 자료를 내보냅니다.
우선순위 큐는 Dequeue 명령은 선형 큐와 동일하지만,
Enqueue 명령은 큐의 자료들과 비교하여 자신의 위치를 정렬하는 과정을 거칩니다.
3-4. 데큐 (Double-Ended Queue)
Deque는 Double-Ended Queue의 약자로 양쪽의 끝을 가지고 있어서 Deque라고 부릅니다.
스택과 큐의 장점만을 합친 형태로 양쪽에서 삽입, 삭제가 가능한 자료구조입니다.
따라서 LEnqueue, REnqueue, LDequeue, RDequeue 등의 명령들이 존재합니다.
Double-Ended Stack이 아니라 Double-Ended Queue인 이유는 딱히 없습니다.
4. 큐의 구현
큐를 구현하는 방법은 크게 배열로 구현하는 방법과 리스트로 구현하는 방법이 존재합니다.
큐를 배열로 구현할 경우 Queue Overflow가 발생할 가능성이 있지만,
리스트에 비해서 메모리를 덜 낭비한다는 장점을 가지고 있다.
하지만 선형 큐를 구현하여 배열의 자료를 미는 알고리즘을 사용할 경우,
자료의 갯수에 따른 과부하가 걸릴 가능성이 존재합니다.
큐를 리스트로 구현할 경우 Queue Overflow가 발생하지 않는다는 장점을 가지고 있지만,
배열로 구현한 것에 비해서 메모리의 낭비가 심하다는 단점을 가지고 있습니다.
5. 큐의 사용
5-1. 실생활에서의 큐
- 화장실 줄을 서는 사람들은 먼저 줄을 선 사람이 먼저 화장실에 들어간다.
- 에스컬레이터에 타는 사람들은 먼저 탄 사람이 먼저 도착한다.
5-2. 프로그래밍에서의 큐
먼저 들어간 자료가 먼저 나오는 자료구조는 생각보다 많은 곳에서 사용됩니다.
- 프린터기의 출력 프로세스에서 사용된다.
- CPU 스케줄링 알고리즘 중 FCFS를 구현하는데 사용된다.
- BFS (너비 우선 탐색)을 구현하는데 사용된다.
6. 마무리
스택과 큐는 자료구조를 처음 배울때 보통 배우게 되는 자료구조입니다.
그만큼 기본기라는 뜻이기 때문에 꼭 알아야 하는 자료구조입니다.
특히 큐의 경우에는 선입선출이라는 특징이 명확하기 때문에
생각보다 많은 곳에서 사용되는듯 합니다.
제 글을 읽어주신 분들께 정말 감사드립니다!!
성장하는 개발자가 되도록 노력하겠습니다.
