특징
큐는 먼저 들어온 것이 먼저 나가는 FIFO(First In First Out) 방식의 자료구조이다.
큐의 한 쪽 끝(Rear)에서는 데이터 삽입만 가능하며, 다른 한 쪽 끝(Front)에서는 데이터 삭제만 가능하다.
큐에서 데이터가 추가되는 것을 Enqueue, 데이터가 삭제되는 것을 Dequeue라고 한다.
큐에는 종류가 총 3가지가 존재한다.
1. 선형 큐(Linear Queue)
2. 원형 큐(Circular Queue)
3. 우선순위 큐(Priority Queue)
원형 큐와 우선순위 큐는 다음 글에서 정리할 예정이다.
연산
큐의 연산은 삽입(add), 삭제(remove), 첫 번째 데이터(가장 오래전에 삽입된 데이터) 확인(peek), 큐가 비었는지 확인(isEmpty) 이렇게 4가지의 연산이 있다.
1. add()
add() 연산은 큐에 데이터를 추가하는 연산이다.
큐에 데이터를 추가하면 Rear의 값이 1이 증가된다.
만일 큐가 꽉 차게 된다면 더 이상 삽입할 수 없다.
2. remove()
remove() 연산은 큐에서 데이터를 제거하는 연산이다.
큐에서 front가 가리키는 데이터를 삭제한 뒤, front의 값을 1 증가시킨다.
만일 rear와 front의 위치가 동일하다면, 이는 큐에 남은 데이터가 없음을 의미하고 더이상 삭제할 수 없다.
3. peek()
peek() 연산은 큐에서 가장 앞에 있는 데이터(가장 오래전에 삽입 된 데이터)를 확인하는 연산이다.
peek() 연산과 remove() 연산의 차이점은 remove() 연산은 데이터를 삭제한 후 읽는다면, peek() 연산은 데이터를 삭제하지 않고 확인할 수 있다.
4. isEmpty()
isEmpty() 연산은 큐가 비어있는지 확인해주는 연산이다.
반환 타입은 boolean으로 큐가 비어있다면 true, 비어있지 않다면 false를 반환한다.
시간복잡도
| 연산 | 복잡도 |
|---|---|
| Insertion | O(1) |
| Deletion | O(1) |
| Selection | O(n) |
삽입 연산의 경우, 데이터를 넣으면 데이터의 개수에 상관없이 삽입할 수 있으므로 O(1)이다.
삭제 연산은 삽입 연산과 마찬가지로 데이터를 삭제할 때 데이터의 개수에 상관없이 삭제할 수 있으므로 O(1)이다.
검색 연산의 경우, 현재 큐에 들어있는 데이터를 모두 찾는 것이므로 데이터의 개수에 따라 복잡도가 달라지므로 O(n)이다.
장단점
장점
- 데이터의 삽입 삭제가 빠르다.
- 순차적으로 되어 있어서 입력 순서에 따라 처리할 때 유용하다.
단점
- 중간에 위치한 데이터에 접근하기 어렵다.
- 배열로 구현하면 삽입, 삭제에 한계가 존재한다.
- 이 문제를 해결하고자 나온 것이 바로 원형 큐이다.
사용사례
- 프린터와 같은 우선순위 작업 예약
- 은행 업무
- 콜센터 고객 대기시간
- 프로세스 관리
- 너비 우선 탐색(BFS, Breadth-First Search) 구현
- 캐시(Cache) 구현
예제코드
Java
Queue
자바에서는 기본적으로 Queue 객체를 지원해준다.
import java.util.LinkedList;
import java.util.Queue;
public class QueueEx {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(4);
queue.add(3);
while(!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}배열
Queue 객체를 사용하지 않고 배열로 구현한다면 다음과 같이 구현할 수 있다.
public class Queue {
private int[] array = new int[100];
int lastIdx = 0;
public void add(int input) {
array[lastIdx] = input;
lastIdx++;
}
public int peek() {
return array[0];
}
public int poll() {
int rs = array[0];
for(int i=1; i<=lastIdx; i++) {
array[i-1] = array[i];
}
lastIdx--;
return rs;
}
public boolean isEmpty() {
return lastIdx==0?true:false;
}
}Kotlin
코틀린에서는 따로 Queue 객체를 구현해놓지 않았다.
그래서 ArrayList를 사용하여 Queue를 구현할 수 있다.
fun main() {
var queue = arrayListOf<Int>()
queue.add(1)
queue.add(2)
queue.add(3)
queue.removeAt(0)
print(queue[0])
}