5. 큐의 개념
큐 : '줄을 서다'라는 뜻을 가지고 있다.
큐는 먼저 들어간 데이터가 먼저 나오는 자료 구조이다.
실생활에서 예를 들자면 줄을 선 순서대로 식당에 입장할 때를 생각해 보면 된다. 이런 큐의 특징을 FIFO(First In First Out)이라고 한다.
Enqueue : 큐에서 삽입하는 연산
Dequeue : 큐에서 꺼내는 연산
큐의 특성을 활용하는 분야
대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용된다.
- 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리하는데, 이때 큐를 활용할 수 있다.
- 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용할 수 있다.
큐의 ADT
| 구분 | 정의 | 설명 |
| 연산 | boolean isFull() | 큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환한다. |
| boolean isEmpty() | 큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환한다. | |
| void add(ItemType item) | 큐에 데이터를 add한다. | |
| ItemType poll() | 큐에서 처음에 add한 데이터를 poll하고, 그 데이터를 반환한다. | |
| 상태 | int front | 큐에서 가장 마지막에 poll한 위치를 기록한다. |
| int rear | 큐에서 최근에 add한 데이터의 위치를 기록한다. | |
| ItemType data[maxsize] | 큐의 데이터를 관리하는 배열이고, 최대 maxsize개의 데이터를 관리한다. |
큐는 데이터를 앞에서 빼고(poll) 뒤에서 데이터를 넣는다.(add)
초기에는 아무런 데이터도 넣은 상태가 아니므로 front와 rear 모두 -1이다.
큐의 세부 동작에 대해서 알아보기
isFull() 연산으로 현재 큐가 가득 찼는지 확인하고 큐가 가득 차지 않았으므로 (isFull이 false) rear를 +1 한 다음 rear가 가리키는 위치에 3을 add하는 모습이다.
※ 반대로 isFull 연사이 true이면 데이터를 add하지 않는다.
이 상태에서 poll()을 하면 isEmpty() 연산을 통해 큐가 비어있는지 확인하고 isEmpty() 연산은 front와 rear가 값이 같은지 확인해서 큐에 원소가 없을 때 poll하는 동작을 방지한다. 만약 비어 있지 않다면(isEmpty()가 false) front를 + 1한다.
만일 이 상태에서 계속 add해서 배열이 꽉 찼을 때 isFull()이 true가 되어 더 이상 add를 할 수 없게 된다.
선형 큐는 front와 rear가 한 방향으로 이동하는데 이를 개선한 큐가 바로 원형 큐이다. 낭비하는 공간을 없애기 위해 원형으로 front와 rear가 돈다. 원형 큐는 선형 큐보다 구현하기 조금 복잡하지만 메모리 공간을 절약할 수 있다는 장점이 있다.
코딩 테스트에서 자바에 컬렉션에서 제공하는 Queue 인터페이스를 사용해도 충분하다. 왜냐하면 Queue는 배열 길이를 자동으로 관리하기 때문이다.
큐 규현하기
큐를 간단하게 구현하는 방식은 크게 2가지 방식이 있다.
1) Queue 인터페이스를 사용하는 방식
2) 덱(ArrayDeque) 클래스를 활용하는 방식
Queue 인터페이스 사용하기
add 메서드와 poll 메서드를 활용해 Enqueue, Dequeue를 하면 된다.
※ add()와 offer() 메서드는 내부적으로 같은 로직을 수행하지만 내부에서 메서드 호출 횟수가 offer()이 1회 더 많기 때문에 근소한 차이로 add()가 빠를 수 있다. 근데 거의 차이가 없다고 봐도 된다.
Queue는 인터페이스로 구현되어 있다고 말했는데, 큐의 구현체로 주로 사용하는 클래스는 ArrayDeque와 LinkedList가 있다.
일반적인 코딩 테스트에선 LinkedList보다 ArrayDeque를 더 많이 사용한다.
따라서 예시에 나오는 큐의 구현체로 ArrayDeque을 사용하겠다.
Queue<Integer> queue = new ArrayDeque<>();
// 큐에 데이터 추가
queue.add(1);
queue.add(2);
queue.add(3);
// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.poll();
System.out.println(first); // 1
// 큐에 데이터 추가
queue.add(4);
queue.add(5);
//큐의 맨 앞 데이터를 제거하면서 반환
first = queue.poll();
System.out.println(first); // 2
덱을 큐처럼 활용하기
덱은 Double Ended Queue를 줄인 말로, 말 그대로 양 끝에서 삽입이나 삭제를 할 수 있는 큐를 구현한 것이다.
ArrayDeque<Integer> queue = new ArrayDeque<>();
// 큐에 데이터 추가
queue.addList(1);
queue.addList(2);
queue.addList(3);
// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.pollFirst();
System.out.println(first); // 1
queue.addList(4);
queue.addList(5);
int first = queue.pollFirst();
System.out.println(first); // 2
ArrayDeque은 addFirst(), addLast(), pollFirst(), pollLast()메서드가 존재한다. 추가로 데이터를 addFirst()로만 넣고, pollFirst()로만 꺼내면 동작은 push(), pop()과 동일하므로 ArrayDeque 하나면 큐, 스택 그리고 덱을 전부 구현할 수 있다는 장점이 있다.
몸풀기 문제
N명의 사람이 원 형태로 서 있습니다. 각 사람은 1부터 N까지 번호표를 갖고 있습니다. 그리고 임의의 숫자 k가 주어졌을 때 다음과 같이 사람을 없앱니다.
- 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다.
- 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.
N과 K가 주어질 때 마지막에 살아있는 사람의 번호를 반환하는 solution() 함수를 구현해라.
제약 조건
- N과 K는 1이상 1000이하의 자연수입니다.
입출력의 예
| N | K | return |
| 5 | 2 | 3 |
public class Solution {
public static void main(String[] args) {
System.out.println(solution(5, 2));
}
// 이 부분을 변경해서 실행해보세요.
private static int solution(int N, int K) {
}
}
N과 K에 실제 값을 넣고 문제를 풀어보자. N = 5, K = 2, 기준이 1인 경우를 예로 설명해보겠다. N = 5이므로 이름표를 1~5로 붙이고 사람을 원형으로 배치한다. 기준은 1이므로 K번째 사람은 2번 번호표를 가진 사람이다. 이 사람을 제거하고 다음 위치를 3으로 한다.
위와 같은 방식으로 3이 기준이 되고 4번 번호표를 가진 사람을 제거하고 다음 위치를 5로, 1번 번호표를 가진 사람을 제거하고 다음 위치를 3으로 하고 다시 5를 제거하면 3만 남는다. 이후 마지막으로 3을 제거하면 이 문제를 해결할 수 있다.
문제 분석하고 풀기
1) 첫 번째 데이터부터 마지막 데이터까지 큐에 add한다.
2) 큐에서 k - 1번째까지의 데이터를 각각 front에서 poll하고 rear에 add한다.
3) k번째 데이터를 poll하고 출력한다.
4) 큐에 더는 원소가 없을 때까지 과정 2~3을 반복합니다.
알고리즘 코드
import java.util.ArrayDeque;
public class Solution {
public static void main(String[] args) {
System.out.println(solution(5, 2));
}
// 이 부분을 변경해서 실행해보세요.
private static int solution(int N, int K) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
for(int i = 1; i <= N; i++) {
deque.addLast(i);
}
while(deque.size() > 1) {
for(int i = 0; i < K - 1; i++) {
deque.addLast(deque.pollFirst());
}
deque.pollFirst();
}
return deque.pollFirst();
}
}
조금만 생각하면 쉽게 풀 수 있는 문제라고 생각이 든다.
시간 복잡도 분석하기
전체 사람 수 K는 제거된 사람의 번호이다. K - 1번 poll하고 1번 add하는 동작을 N번 반복하므로 최종 시간 복잡도는 O(N * K)이다.