Queue 계층 구조에서 길 찾기
Java SE 5에서는 컬렉션 프레임워크에 새로운 인터페이스인 Queue 인터페이스가 추가되었으며, Java SE 6에서는 Deque 인터페이스로 더욱 확장되었습니다. Queue 인터페이스는 Collection 인터페이스의 확장입니다.
Queue 인터페이스 계층 구조
Pushing, Popping and Peeking
Stack과 Queue 구조는 컴퓨팅의 고전적인 데이터 구조입니다. Stack은 LIFO Stack이라고도 하며, 여기서 LIFO는 Last In, First Out의 약자입니다. Queue는 FIFO라고도 합니다: 선입선출이라고도 합니다.
이러한 구조는 매우 간단하며 세 가지 주요 작업을 제공합니다.
- push(element): 요소를 Queue 또는 Stack에 추가합니다.
- pop(): Stack에서 요소, 즉 추가된 가장 최근 요소를 제거합니다.
- poll(): Queue에서 요소, 즉 추가된 가장 오래된 요소를 제거합니다.
- peek(): 를 사용하면 pop() 또는 poll() 을 통해 얻을 요소를 제거하지 않고도 확인할 수 있습니다.
컴퓨팅에서 이러한 구조의 성공을 설명하는 데는 두 가지 이유가 있습니다. 첫 번째는 단순성입니다. 컴퓨팅의 초창기에도 이러한 구조를 구현하는 것은 간단했습니다. 두 번째는 그 유용성입니다. 많은 알고리즘이 Stack을 구현에 사용합니다.
Queues 와 Stacks 모델링
컬렉션 프레임워크는 Queue와 Stack을 모델링하는 두 가지 인터페이스를 제공합니다:
Queue인터페이스는 큐를 모델링합니다;Deque인터페이스는 양쪽 끝이 있는 Queue(따라서 이름)를 모델링합니다.Deque의 꼬리 부분과 머리 부분 모두에서 요소를 Pushing, Popping, Polling, Peeking할 수 있어 Queue이자 Stack이 될 수 있습니다.
Stack과 Queue는 동시 프로그래밍에서도 널리 사용됩니다. 이러한 인터페이스는 더 많은 인터페이스로 확장되어 이 분야에서 유용한 메서드를 추가합니다. 이러한 인터페이스인 BlockingQueue, BlockingDeque 및 TransferQueue는 컬렉션 프레임워크와 Java의 동시 프로그래밍의 교차점에 있으며, 이 튜토리얼의 범위를 벗어납니다.
Queue와 Deque 인터페이스는 이 세 가지 기본 연산에 동작을 추가하여 두 가지 코너 케이스를 처리합니다.
- Queue가 꽉 차서 더 이상 요소를 받을 수 없는 경우
- Queue가 비어 있어 pop, poll 또는 peek 연산으로 요소를 반환할 수 없는 경우.
실제로 이 두 가지 경우에 구현이 어떻게 작동해야 하는지에 대한 질문에 답해야 합니다.
Queue를 사용하여 FIFO 큐 모델링하기
Queue 인터페이스는 이러한 코너 케이스를 처리하는 두 가지 방법을 제공합니다. 예외를 던지거나 특수 값을 반환할 수 있습니다.
다음은 Queue가 제공하는 메서드 표입니다.
| Operation | Method | Behavior when the queue is full or empty |
|---|---|---|
| push | add(element) | throws an IllegalStateException |
offer(element) | returns false | |
| poll | remove() | throws a NoSuchElementException |
poll() | returns false | |
| peek | element() | throws a NoSuchElementException |
peek() | returns null |
Deque로 LIFO Stack 및 FIFO Queue 모델링하기
Java SE 6에서는 Deque 인터페이스가 Queue 인터페이스의 확장으로 추가되었습니다. 물론 Queue에 정의된 메서드는 여전히 Deque에서 사용할 수 있지만, Deque는 새로운 명명 규칙을 가져왔습니다. 따라서 이러한 메서드는 새로운 명명 규칙에 따라 Deque에 중복되었습니다.
다음은 Deque에 정의된 FIFO 연산에 대한 메서드 표입니다.
| FIFO Operation | Method | Behavior when the queue is full or empty |
|---|---|---|
| push | addLast(element) | throws an IllegalStateException |
offerLast(element) | returns false | |
| poll | removeFirst() | throws a NoSuchElementException |
pollFirst() | returns null | |
| peek | getFirst() | throws a NoSuchElementException |
peekFirst() | returns null |
다음은 Deque에 정의된 LIFO 연산에 대한 메서드 표입니다.
| LIFO Operation | Method | Behavior when the queue is full or empty |
|---|---|---|
| push | addFirst(element) | throws an IllegalStateException |
offerFirst(element) | returns false | |
| pop | removeFirst() | throws a NoSuchElementException |
pollFirst() | returns null | |
| peek | getFirst() | throws a NoSuchElementException |
peekFirst() | returns null |
Deque의 명명 규칙은 간단하며, Queue 인터페이스에서 따르는 것과 동일합니다. 한 가지 차이점이 있다면, Deque에서는 getFirst()와 getLast()의 이름이, Queue에서는 element()]의 이름이 붙여진다는 점입니다.
또한, Deque는 모든 Queue 또는 Stack 클래스에서 기대할 수 있는 메서드도 정의합니다:
push(element): 주어진요소를 양쪽 끝 Queue의 헤드에 추가합니다.pop(): 양쪽 끝 Queue의 헤드에 있는 요소를 제거하고 반환합니다.poll(): 양쪽 끝 Queue의 꼬리에서 동일한 작업을 수행합니다.peek(): 양쪽 끝 Queue의 끝에 있는 요소를 표시합니다.
pop, poll 또는 peek 에 요소가 없는 경우 이러한 메서드에서는 null 값이 반환됩니다.
Queue 및 Deque 구현하기
컬렉션 프레임워크는 동시 프로그래밍 공간 외부에서 Queue 및 Deque의 세 가지 구현을 제공합니다:
ArrayDeque: 두 가지를 모두 구현합니다. 이 구현은 배열로 뒷받침됩니다. 이 클래스의 용량은 요소가 추가됨에 따라 자동으로 증가합니다. 따라서 이 구현은 항상 새로운 요소를 받아들입니다.LinkedList: 이 역시 두 가지를 모두 구현합니다. 이 구현은 링크된 목록으로 지원되므로 첫 번째와 마지막 요소에 대한 액세스가 매우 효율적입니다. 링크된 리스트](https://docs.oracle.com/en/java/javase/22/docs/api/java.base/java/util/LinkedList.html)는 항상 새로운 요소를 받아들입니다.PriorityQueue:Queue만 구현합니다. 이 Queue는 요소를 자연 순서 또는Comparator에 의해 지정된 순서로 정렬된 배열로 뒷받침됩니다. 이 큐의 헤드는 항상 지정된 Ordering과 관련하여 큐의 최하위 요소입니다. 이 클래스의 용량은 요소가 추가됨에 따라 자동으로 증가합니다.
Stack 클래스에서 벗어나기
JDK에서 제공하는 Stack 클래스를 사용하고 싶을 수 있습니다. 이 클래스는 사용과 이해가 간단합니다. 이 클래스에는 예상되는 세 가지 메서드 push(element), pop() 및 peek()가 있으며, 코드에서 이 클래스를 참조하는 것을 보면 완벽하게 가독성이 있습니다.
이 클래스는 Vector 클래스의 확장이라는 것이 밝혀졌습니다. 컬렉션 프레임워크가 도입되기 전에는 Vector가 List 작업을 위한 최선의 선택이었습니다. Vector는 더 이상 사용되지 않지만, 그 사용은 권장되지 않습니다. Stack 클래스의 사용도 마찬가지입니다.
Vector 클래스는 스레드 안전하며, Stack도 마찬가지입니다. 스레드 안전성이 필요하지 않은 경우, Deque 및 ArrayDeque로 안전하게 대체할 수 있습니다. 스레드 안전 Stack이 필요한 경우, BlockingQueue 인터페이스의 구현을 살펴봐야 합니다.