🔥 Queue (큐)
1. Queue(큐)란?
'Queue' 는 컴퓨터 과학에서 사용되는 데이터 구조 중 하나이다.
'FIFO'(First-In-First-Out : 선입선출) 원칙에 따라 동작한다.
선입선출 : 첫 번째로 들어간 항목이 첫 번째로 나오게 되는 것을 의미한다.
'매표소에 줄을 서있는 사람들'을 생각하면 쉽다.
2. 큐의 특징
데이터가 추가(Enqueue)되는 위치는 '줄의 가장 뒤(Back)'라고 하고,
데이터가 제거(Dequeue)되는 위치는 '줄의 가장 앞(Front)'이라고 한다.
큐는 작업이 불가능할 때 ⚡️블로킹(Blocking)이 일어날 수 있다.
예를 들어, 비어있는 큐에 제거 연산을 시도하거나 가득 찬 큐에 삽입을 시도하는 경우이다.
또한 큐는 너비 우선 탐색 알고리즘(BFS)에서 사용된다.
BFS :
- 그래프나 트리와 같은 자료구조를 탐색하는 알고리즘 중 하나.
- 시작 노드에서 출발하여 인접한 모든 노드를 먼저 방문하는 방식으로 작동한다.
(* 최단 경로를 찾는 문제에 효과적으로 사용된다.)
3. 메서드
Ⓜ️ 삽입 메서드
offer(E e)
: 큐가 꽉차있으면 'false'를 반환하고 예외는 발생하지 않는다.
add(E e)
: 큐가 꽉차있으면 'IllegalStateException' 을 던진다.
Ⓜ️ 제거 메서드
poll()
: 큐의 맨 앞에 요소를 제거하고 반환한다. 큐가 비어있을 경우 'null'을 반환한다.
remove()
: 큐의 맨 앞에 요소를 제거하고 반환한다. 큐가 비어있을 경우 'NoSuchElementException'을 던진다.
Ⓜ️ 조회 메서드
peek()
: 큐의 맨 앞에 있는 요소를 반환하지만 제거는 하지 않는다. 큐가 비었을 경우 'null'을 반환한다.
element()
: 큐의 맨 앞에 있는 요소를 반환하지만 제거는 하지 않는다. 큐가 비었을 경우 'NoSuchElementException'을 반환한다.
4. 단방향 큐(Queue) / 양방향 큐(Deque)
큐는 단방향 큐(Queue) / 양방향 큐(Deque) 로 구분해볼 수 있다.
단방향 큐(Queue)의 특징
-
FIFO 방식을 따르므로 로직이 간단하고 이해하기 쉽다.
-
데이터가 도착한 순서대로 처리되므로, 요소가 언제 처리될지 예측하기 쉽다.
-
단, 단방향이기 때문에 유연성이 부족할 수 있다.
ex) 큐의 끝에서 요소를 제거하거나, 검색하는 것은 비효율적이다.
양방향 큐(Deque)의 특징
-
유연성 : 양쪽 끝에서 요소를 추가하거나 제거할 수 있으므로 단방향 큐보다 더 다양한 상황에 대응할 수 있다. 이로 인해 양방향 큐는
스택 or 큐로도 사용될 수 있다. -
복잡성 : 데크는 양방향성이므로 로직이 더 복잡하다. 버그가 발생할 가능성이 높으며, 코드를 이해하거나 유지하기가 더 어려울 수 있다.
-
양방향 큐의 대표적인 클래스로는
LinkedList클래스가 있다.
단방향 큐는 순차적인 데이터 처리가 필요하고 단순성이 중요한 경우,
양방향 큐는 복잡한 데이터 조작이 필요하거나 양방향으로 작업을 수행해야 하는 경우에 적합하다.
사실 우리가 말하는 표준 큐(Queue)는 FIFO 원칙을 따르며, Front, Back으로 나뉘어져 있다.
그럼 Deque는 뭘까?
+ Deque 란?
: 큐의 일반적인 FIFO 원칙을 완전히 따르지는 않지만, 그 기능을 확장한 자료구조이다.
이런 특징때문에 상황에 따라 스택 or 큐 로 동작할 수 있다.
자바의 java.util.Queue 인터페이스는 큐의 기본적인 FIFO 동작을 정의하고,
java.util.Deque 인터페이스는 이를 확장하여 양방향 동작을 추가한다.
따라서 Deque는 Queue를 확장한 형태라고 생각하면 된다.
양방향 큐(Deque) 인터페이스를 구현한 클래스들은 양방향에서 삽입하고 제거하고 조회하는 새로운 메서드 들을 사용할 수 있게되는데 최대한 간단히 적어보겠다.
메서드마다 양방향이다 보니 처음과 마지막을 뜻하는 First와 Last가 똑같이 붙는다.
Ⓜ️ 삽입 메서드
addFirst(E e)
: 앞쪽에 요소를 삽입한다. 꽉찼을 경우 IllegalStateException을 던진다.
addLast(E e)
: 뒤쪽에 요소를 삽입한다. 꽉찼을 경우 IllegalStateException을 던진다.
offerFirst(E e)
: 앞쪽에 요소를 삽입한다. 꽉찼을 경우 false를 반환하고 예외는 발생하지 않는다.
offerLast(E e)
: 앞쪽에 요소를 삽입한다. 꽉찼을 경우 false를 반환하고 예외는 발생하지 않는다.
Ⓜ️ 제거 메서드
removeFirst()
: 앞쪽의 첫 번째 요소를 제거하고 반환한다. 비어 있을 경우 'NoSuchElementException'을 던진다.
removeLast()
: 뒤쪽의 첫 번째 요소를 제거하고 반환한다. 비어 있을 경우 'NoSuchElementException'을 던진다.
pollFirst()
: 앞쪽의 첫 번째 요소를 제거하고 반환한다. 비어 있을 경우 'null'을 반환한다.
pollLast()
: 뒤쪽의 첫 번째 요소를 제거하고 반환한다. 비어 있을 경우 'null'을 반환한다.
Ⓜ️ 조회 메서드
getFirst()
: 앞쪽에 있는 요소를 반환하지만 제거하지 않는다. 데크가 비어 있을 경우 NoSuchElementException을 던진다.
getLast()
: 뒤쪽에 있는 요소를 반환하지만 제거하지 않는다. 데크가 비어 있을 경우 NoSuchElementException을 던진다.
peekFirst()
: 앞쪽에 있는 요소를 반환하지만 제거하지 않는다. 데크가 비어 있을 경우 null을 반환한다.
peekLast()
: 뒤쪽에 있는 요소를 반환하지만 제거하지 않는다. 데크가 비어 있을 경우 null을 반환한다.
🎁 사용 예시
아래는 LinkedList 클래스를 사용하여 큐의 기본 메서드들과 양방향 큐에서 사용할 수 있는 메서드들을 사용해보았다.
LinkedList클래스는 'List' 인터페이스와 'Deque' 인터페이스를 모두 구현했고,
'Deque' 인터페이스는 'Queue' 인터페이스를 확장했기 때문에,
LinKedList클래스는 간접적으로 'Queue' 를 구현하게 된다!)
여기서는 잠깐 큐가 가득찬 상황을 만들기 위해 LinkedList대신 다른 클래스를 사용했다.
// offer(), add()메서드의 가득찬 상황을 테스트하기 위해 해당 클래스를 사용했다.
// LinkedList는 크기 제한이 없는 클래스이기 때문에 테스트에 적합하지 않았다.
// offer() 메서드
ArrayBlockingQueue<Integer> offerTest = new ArrayBlockingQueue<>(1);
System.out.println(offerTest.offer(1)); // true
System.out.println(offerTest.offer(1)); // false
// add() 메서드
ArrayBlockingQueue<Integer> addTest = new ArrayBlockingQueue<>(1);
System.out.println(addTest.add(1)); // true
try {
System.out.println(addTest.add(1)); // Queue full!!
} catch (IllegalStateException e) {
e.printStackTrace();![]
}
다음은 기본 메서드들이다. add(), poll(), peek()
LinkedList<Integer> deque = new LinkedList<>();
deque.add(1);
deque.add(2);
deque.add(3);
deque.add(4);
deque.add(5); // 1, 2, 3, 4, 5
System.out.println("poll(제거) : " + deque.poll()); // 1을 출력하고 맨 앞 제거
deque.peek();
deque.peek(); // 몇 번을 해도 똑같다.
System.out.println("peek(조회) : " + deque.peek()); // 2를 출력하고 요소 제거 X
for (int item : deque) {
System.out.print(item + " ");
}
// deque 출력 : 2 3 4 5다음은 양방향 큐(Deque)의 메서드들이다. offerFirst(), pollLast(), peekLast()
// 현재 deque : 2 3 4 5
// 양방향 메서드를 사용해보겠다. addLast()는 사실 그냥 add와 같다.
deque.addFirst((6)); // 6 2 3 4 5
deque.offerFirst(7); // 7 6 2 3 4 5
deque.removeLast(); // 맨 뒤 5를 제거 후 반환 -- 7 6 2 3 4
deque.pollLast(); // 맨 뒤 4를 제거 후 반환 -- 7 6 2 3
deque.getLast(); // 3
deque.peekLast(); // 3
// 양방향 큐(Deque)의 메서드를 같이 사용하면
// 마치 새치기를 하는 듯한 모양을 볼 수 있다.
// 7 6 2 '3'
deque.offerFirst(deque.pollLast()); // 맨 뒤 3을 제거 후 맨 앞으로 추가
for (int item : deque) {
System.out.print(item + " "); // '3' 7 6 2 (웅성웅성)(수근수근)
}
맨 아래 '새치기(?)' 처럼 Deque의 확장된 기능은 Queue로만은 구현하기 힘든 복잡한 로직을 쉽게 구현할 수 있다.
아래는 연결리스트에 대해 적어둔 내용이다. 도움이 되었으면 좋겠다.
[링크] 자료구조 4 - LinkedList에 대해 알아보자!
