2024. 6. 19. 10:39ㆍHigh Level Programming Language/Collections
The Queue Interface
Queue는 엘리먼트를 처리하기 전에 보관하는 컬렉션입니다. 기본적인 Collection 연산 외에도 큐는 추가적인 삽입, 제거 및 검사 연산을 제공합니다. Queue 인터페이스는 다음과 같습니다.
public interface Queue<E> extends Collection<E> {
E element();
boolean offer(E e);
E peek();
E poll();
E remove();
}
각 Queue 메서드는 두 가지 형태로 존재합니다:
(1) 연산이 실패하면 예외를 던지는 형태.
(2) 연산이 실패하면 특별한 값을 반환하는 형태(null 또는 false, 연산에 따라 다름).
인터페이스의 일반적인 구조는 다음 표에 나와 있습니다.
Queue Interface Structure
| Type of Operation | Throws exception | Returns special value |
| Insert | add(e) | offer(e) |
| Remove | remove() | poll() |
| Examine | element() | peek() |
큐는 일반적으로 FIFO(선입선출) 방식으로 엘리먼트들을 정렬하지만, 반드시 그렇지는 않습니다. 예외 중 하나는 우선순위 큐로, 엘리먼트의 우선순위 값에 따라 엘리먼트를 정렬합니다(자세한 내용은 객체 정렬(Object Ordering) 섹션을 참조하세요). 어떤 정렬 방법을 사용하든지 간에, 큐의 head는 remove나 poll 호출에 의해 제거될 엘리먼트입니다. FIFO 큐에서는 모든 새로운 엘리먼트가 큐의 tail에 삽입됩니다. 다른 종류의 큐는 다른 배치 규칙을 사용할 수 있습니다. 모든 큐 구현은 정렬 속성을 명시해야 합니다.
큐 구현은 보유하는 엘리먼트의 수를 제한할 수 있습니다. 이러한 큐를 유한 큐(bounded queue)라고 합니다. java.util.concurrent의 일부 큐 구현은 유한 큐이지만, java.util의 구현은 그렇지 않습니다.
다음은 java.util.concurrent 패키지에서 제공하는 유한 큐(bounded queue)의 예시로, ArrayBlockingQueue를 사용하는 샘플 코드입니다. 이 코드는 큐의 용량을 제한하고, 큐가 가득 찼을 때 offer 메서드를 사용하여 엘리먼트를 추가하려 할 때 실패하는 모습을 보여줍니다.
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
public class BoundedQueueExample {
public static void main(String[] args) {
// 용량이 5인 유한 큐 생성
BlockingQueue<Integer> boundedQueue = new ArrayBlockingQueue<>(5);
try {
// 큐에 요소 추가
for (int i = 1; i <= 5; i++) {
boundedQueue.add(i);
System.out.println("Added element: " + i);
}
// 큐가 가득 찼으므로 다음 추가 시도는 실패함
boolean wasAdded = boundedQueue.offer(6);
if (!wasAdded) {
System.out.println("Failed to add element: 6 (Queue is full)");
}
// 큐에서 요소 제거
while (!boundedQueue.isEmpty()) {
int element = boundedQueue.poll();
System.out.println("Removed element: " + element);
}
} catch (IllegalStateException e) {
System.err.println("Error adding element to the queue: " + e.getMessage());
}
}
}
이 예제에서는 다음과 같은 작업을 수행합니다:
1. 용량이 5인 ArrayBlockingQueue를 생성합니다.
2. 큐에 5개의 엘리먼트를 추가합니다.
3. 큐가 가득 찬 상태에서 offer 메서드를 사용하여 엘리먼트를 추가하려고 시도하고, 실패 시 메시지를 출력합니다.
4. 큐에서 엘리먼트를 하나씩 제거하고 출력합니다.
ArrayBlockingQueue는 java.util.concurrent 패키지에 포함된 유한 큐의 대표적인 예입니다. 반면, java.util 패키지에 있는 큐 구현체(LinkedList 등)는 기본적으로 무한 큐입니다.
컬렉션(Collection)에서 큐(Queue)가 상속하는 add 메서드는 큐의 용량 제한을 위반하지 않는 한, 엘리먼트를 삽입합니다. 제한을 위반하면 IllegalStateException을 던집니다. offer 메서드는 유한 큐에서만 사용하기 위한 것이며, 엘리먼트 삽입 실패를 알리기 위해 false를 반환하는 점만 add 메서드와 다릅니다.
Queue 인터페이스에서 offer와 add 메서드는 모두 큐에 엘리먼트를 추가하는 데 사용되지만, 두 메서드의 동작 방식에는 중요한 차이점이 있습니다.
1. offer(E e):
▪ offer 메서드는 엘리먼트를 큐에 추가하려고 시도합니다.
▪ 큐의 용량 제한에 걸리면 offer 메서드는 false를 반환하여 추가가 실패했음을 알립니다.
▪ 예외를 던지지 않기 때문에 안전하게 큐의 상태를 확인하고 적절하게 처리할 수 있습니다.
2. add(E e):
▪ add 메서드는 엘리먼트를 큐에 추가합니다.
▪ 큐의 용량 제한에 걸리면 add 메서드는 IllegalStateException을 던집니다.
▪ add 메서드는 성공적으로 추가되면 true를 반환합니다.
이 두 메서드는 유한 큐(bounded queue)에서 주로 사용되는 방식에 따라 선택됩니다. offer 메서드는 큐가 가득 찬 경우 예외를 피하고 실패를 나타내기 위해 false를 반환하는 반면, add 메서드는 큐가 가득 찬 경우 예외를 던져서 더 강력한 오류 처리를 할 수 있도록 합니다.
다음은 offer와 add 메서드의 차이를 보여주는 예제 코드입니다:
import java.util.concurrent.ArrayBlockingQueue;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
// 용량이 3인 유한 큐 생성
Queue<Integer> queue = new ArrayBlockingQueue<>(3);
// offer 메서드를 사용하여 엘리먼트 추가
System.out.println("Offer 1: " + queue.offer(1)); // true
System.out.println("Offer 2: " + queue.offer(2)); // true
System.out.println("Offer 3: " + queue.offer(3)); // true
System.out.println("Offer 4: " + queue.offer(4)); // false (큐가 가득 참)
// add 메서드를 사용하여 엘리먼트 추가
try {
System.out.println("Add 5: " + queue.add(5)); // IllegalStateException 발생
} catch (IllegalStateException e) {
System.out.println("Failed to add 5: " + e.getMessage());
}
}
}
이 예제에서는:
▪ ArrayBlockingQueue를 생성하고 용량을 3으로 설정합니다.
▪ offer 메서드를 사용하여 4개의 엘리먼트들을 추가하려고 시도하며, 네 번째 시도는 실패하여 false를 반환합니다.
▪ add 메서드를 사용하여 네 번째 엘리먼를 추가하려고 시도하면, 큐가 가득 찼기 때문에 IllegalStateException이 발생합니다.
remove와 poll 메서드는 모두, 큐의 head 엘리먼트를 제거하고 리턴합니다. 정확히 어떤 엘리먼트가 제거되는지는 큐의 정렬 정책에 따라 다릅니다. remove와 poll 메서드는 큐가 비어 있을 때만 동작이 다릅니다. 이 경우 remove는 NoSuchElementException을 던지고, poll은 null을 반환합니다.
다음은 remove와 poll 메서드의 동작 차이를 보여주는 샘플 코드입니다. 이 코드에서는 두 메서드가 큐의 head 엘리먼트를 제거하고 리턴하는 방식과, 큐가 비어 있을 때의 동작을 확인할 수 있습니다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.NoSuchElementException;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 큐에 엘리먼트 추가
queue.add(1);
queue.add(2);
queue.add(3);
// 큐에서 엘리먼트 제거 및 출력
System.out.println("Removed with remove(): " + queue.remove()); // 1
System.out.println("Removed with poll(): " + queue.poll()); // 2
System.out.println("Removed with remove(): " + queue.remove()); // 3
// 큐가 비어 있는 경우 remove() 메서드 사용 시 예외 발생
try {
System.out.println("Attempt to remove with remove(): " + queue.remove());
} catch (NoSuchElementException e) {
System.out.println("Exception caught: " + e.getMessage());
}
// 큐가 비어 있는 경우 poll() 메서드 사용 시 null 반환
System.out.println("Attempt to remove with poll(): " + queue.poll()); // null
}
}
이 예제에서는 다음과 같은 작업을 수행합니다:
1. LinkedList를 사용하여 Queue를 생성합니다.
2. 큐에 3개의 엘리먼트를 추가합니다.
3. remove와 poll 메서드를 사용하여 엘리먼트를 제거하고 출력합니다.
4. 큐가 비어 있는 상태에서 remove 메서드를 호출하여 NoSuchElementException 예외가 발생하는 것을 확인합니다.
5. 큐가 비어 있는 상태에서 poll 메서드를 호출하여 null이 반환되는 것을 확인합니다.
이 코드로 remove와 poll 메서드의 동작 차이를 명확히 이해할 수 있습니다.
element와 peek 메서드는 큐의 head 엘리먼트를 반환하지만 제거하지는 않습니다. 이 메서드들도 큐가 비어 있을 때의 동작이 remove와 poll 메서드와 정확히 동일합니다: element는 NoSuchElementException을 던지고, peek은 null을 반환합니다.
다음은 element와 peek 메서드의 동작 차이를 보여주는 샘플 코드입니다. 이 코드는 두 메서드가 큐의 head 엘리먼트를 반환하지만 제거하지 않는 방식과, 큐가 비어 있을 때의 동작을 확인할 수 있습니다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.NoSuchElementException;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 큐에 엘리먼트 추가
queue.add(1);
queue.add(2);
queue.add(3);
// 큐의 head 엘리먼트를 반환 (제거하지 않음)
System.out.println("Head element with element(): " + queue.element()); // 1
System.out.println("Head element with peek(): " + queue.peek()); // 1
// 큐의 상태 출력
System.out.println("Queue after element() and peek(): " + queue); // [1, 2, 3]
// 큐에서 엘리먼트 제거
queue.remove();
queue.remove();
queue.remove();
// 큐가 비어 있는 경우 element() 메서드 사용 시 예외 발생
try {
System.out.println("Attempt to get head with element(): " + queue.element());
} catch (NoSuchElementException e) {
System.out.println("Exception caught: " + e.getMessage());
}
// 큐가 비어 있는 경우 peek() 메서드 사용 시 null 반환
System.out.println("Attempt to get head with peek(): " + queue.peek()); // null
}
}
이 예제에서는 다음과 같은 작업을 수행합니다:
1. LinkedList를 사용하여 Queue를 생성합니다.
2. 큐에 3개의 엘리먼트들을 추가합니다.
3. element와 peek 메서드를 사용하여 head 엘리먼트를 반환하고, 이를 출력합니다. 이때 엘리먼트는 제거되지 않습니다.
4. 큐의 상태를 출력하여 엘리먼트가 제거되지 않았음을 확인합니다.
5. 큐에서 모든 엘리먼트를 제거합니다.
6. 큐가 비어 있는 상태에서 element 메서드를 호출하여 NoSuchElementException 예외가 발생하는 것을 확인합니다.
7. 큐가 비어 있는 상태에서 peek 메서드를 호출하여 null이 반환되는 것을 확인합니다.
이 코드로 element와 peek 메서드의 동작 차이를 명확히 이해할 수 있습니다.
Queue 구현은 일반적으로 null 엘리먼트의 삽입을 허용하지 않습니다. Queue를 구현하기 위해 수정된 LinkedList 구현은 예외입니다. 역사적인 이유로 null 엘리먼트를 허용하지만, poll과 peek 메서드가 null을 특별한 리턴 값으로 사용하기 때문에 이를 이용하지 않는 것이 좋습니다.
다음은 LinkedList가 Queue 인터페이스를 구현할 때 null 엘리먼트를 허용하는 예외적인 경우를 보여주는 샘플 코드입니다. 이 코드는 poll과 peek 메서드가 null을 특별한 리턴 값으로 사용하는 이유로 null 엘리먼트의 사용을 피해야 하는 이유를 설명합니다.
import java.util.LinkedList;
import java.util.Queue;
public class QueueNullElementExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
// null 엘리먼트 추가 (LinkedList는 허용)
queue.add(null);
queue.add("A");
queue.add("B");
// 큐의 상태 출력
System.out.println("Queue after adding elements (including null): " + queue);
// poll 메서드로 엘리먼트 제거 및 출력
// 첫 번째 호출은 null 반환
System.out.println("Polled element: " + queue.poll()); // null
// 큐의 상태 출력
System.out.println("Queue after polling once: " + queue);
// 두 번째 호출은 "A" 반환
System.out.println("Polled element: " + queue.poll()); // "A"
// peek 메서드로 엘리먼트 확인 (제거하지 않음)
// 현재 head 요소인 "B" 반환
System.out.println("Peeked element: " + queue.peek()); // "B"
// 모든 엘리먼트 제거
queue.clear();
// 큐가 비어 있는 상태에서 peek 메서드 호출 (null 반환)
System.out.println("Peeked element when queue is empty: " + queue.peek()); // null
// 큐가 비어 있는 상태에서 poll 메서드 호출 (null 반환)
System.out.println("Polled element when queue is empty: " + queue.poll()); // null
}
}
이 코드로 null 엘리먼트의 삽입이 왜 피해야 하는지, 그리고 poll과 peek 메서드가 null을 특별한 리턴 값으로 사용하기 때문에 주의해야 하는 이유를 명확히 이해할 수 있습니다.
(큐가 비어 있는 상태에서 peek 또는 poll 메서드 호출에 대한 리턴값도 null이기 때문에, null 엘리먼트를 큐에 삽입하지 말라고 언급하고 있습니다)
큐 구현은 일반적으로 엘리먼트 기반의 equals 및 hashCode 메서드를 정의하지 않고 Object로부터 상속받은 아이덴티티(identity) 기반의 메서드를 상속받습니다.
다음은 큐 구현에서 엘리먼트 기반의 equals 및 hashCode 메서드를 정의하지 않고, Object로부터 상속받은 아이덴티티(identity) 기반의 메서드를 사용하는 예제를 보여주는 샘플 코드입니다. 이 코드에서는 두 개의 큐를 생성하고 동일한 엘리먼트를 추가한 후, equals 메서드와 hashCode 메서드를 호출하여 비교합니다.
import java.util.LinkedList;
import java.util.Queue;
public class QueueIdentityEqualsHashCodeExample {
public static void main(String[] args) {
// 두 개의 큐 생성
Queue<Integer> queue1 = new LinkedList<>();
Queue<Integer> queue2 = new LinkedList<>();
// 동일한 엘리먼트 추가
queue1.add(1);
queue1.add(2);
queue1.add(3);
queue2.add(1);
queue2.add(2);
queue2.add(3);
// 큐의 상태 출력
System.out.println("Queue 1: " + queue1);
System.out.println("Queue 2: " + queue2);
// equals 메서드 비교
boolean areEqual = queue1.equals(queue2);
System.out.println("Are the two queues equal? " + areEqual);
// hashCode 메서드 비교
int hashCode1 = queue1.hashCode();
int hashCode2 = queue2.hashCode();
System.out.println("Hash code of Queue 1: " + hashCode1);
System.out.println("Hash code of Queue 2: " + hashCode2);
}
}
이 예제에서는 다음과 같은 작업을 수행합니다:
1. LinkedList를 사용하여 두 개의 큐 (queue1과 queue2)를 생성합니다.
2. 두 큐에 동일한 엘리먼트들 1, 2, 3을 추가합니다.
3. 두 큐의 상태를 출력하여 동일한 엘리먼트를 가지고 있는지 확인합니다.
4. equals 메서드를 사용하여 두 큐를 비교합니다. 큐 구현에서는 엘리먼트 기반의 equals 메서드를 정의하지 않으므로, 두 큐가 동일한 엘리먼트를 가지고 있어도 equals 메서드는 false를 반환합니다.
5. 각 큐의 hashCode 값을 출력합니다. 마찬가지로 엘리먼트 기반의 hashCode 메서드를 정의하지 않으므로, 두 큐가 동일한 엘리먼트를 가지고 있어도 hashCode 값은 다를 수 있습니다.
이 코드로 큐 구현이 왜 아이덴티티 기반의 equals 및 hashCode 메서드를 사용하는지 명확히 이해할 수 있습니다. Queue 인터페이스를 구현하는 클래스는 기본적으로 Object 클래스의 equals 및 hashCode 메서드를 상속받으며, 이는 객체의 참조를 기반으로 비교합니다.
큐 인터페이스는 엘리먼트가 나타나기를 기다리거나 공간이 생기기를 기다리는 블로킹 큐 메서드를 정의하지 않습니다. 이러한 메서드는 java.util.concurrent.BlockingQueue 인터페이스에 정의되어 있으며, 이 인터페이스는 큐를 확장합니다.
다음 예제 프로그램에서는 큐를 사용하여 카운트다운 타이머를 구현합니다. 큐는 커맨드라인에서 지정한 숫자부터 0까지의 모든 정수 값을 내림차순으로 미리 로드합니다. 그런 다음 큐에서 값을 제거하고 1초 간격으로 값을 출력합니다. 이 프로그램은 큐를 사용하지 않고 동일한 작업을 수행하는 것이 더 자연스러울 것이지만, 큐를 사용하여 요소를 저장한 후 처리하는 방법을 보여줍니다.
import java.util.*;
public class Countdown {
public static void main(String[] args) throws InterruptedException {
int time = Integer.parseInt(args[0]);
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = time; i >= 0; i--)
queue.add(i);
while (!queue.isEmpty()) {
System.out.println(queue.remove());
Thread.sleep(1000);
}
}
}
다음 예제에서는 우선순위 큐를 사용하여 엘리먼트 컬렉션을 정렬합니다. 이 프로그램도 마찬가지로 Collections에서 제공하는 sort 메서드를 사용하는 것이 더 자연스러워, 실제로 사용할 이유는 없지만, 우선순위 큐의 동작을 설명합니다.
static <E> List<E> heapSort(Collection<E> c) {
Queue<E> queue = new PriorityQueue<E>(c);
List<E> result = new ArrayList<E>();
while (!queue.isEmpty())
result.add(queue.remove());
return result;
}
ArrayList vs LinkedList
ArrayList와 LinkedList의 성능 평가를 위해 각 자료구조에서 자주 사용되는 몇 가지 연산(삽입, 삭제, 접근 등)에 대한 시간 복잡도를 비교해보겠습니다.
ArrayList
1. 랜덤 접근 (Random Access):
⦁ 시간 복잡도: O(1)
⦁ 설명: 배열을 기반으로 하기 때문에 인덱스를 통해 빠르게 접근할 수 있습니다.
2. 삽입 (Insert):
⦁ 끝에 삽입: O(1) (평균적으로, 배열이 가득 찬 경우 재할당 필요)
⦁ 중간에 삽입: O(n)
⦁ 설명: 끝에 삽입할 때는 평균적으로 O(1)이지만, 중간에 삽입할 때는 요소들을 이동시켜야 하므로 O(n)의 시간이 걸립니다.
3. 삭제 (Remove):
⦁ 끝에서 삭제: O(1)
⦁ 중간에서 삭제: O(n)
⦁ 설명: 끝에서 삭제하는 경우는 O(1)이지만, 중간에서 삭제할 경우 요소들을 이동시켜야 하므로 O(n)의 시간이 걸립니다.
4. 탐색 (Search):
⦁ 시간 복잡도: O(n)
⦁ 설명: 특정 요소를 찾기 위해서는 순차적으로 탐색해야 하므로 O(n)의 시간이 걸립니다.
LinkedList
1. 랜덤 접근 (Random Access):
⦁ 시간 복잡도: O(n)
⦁ 설명: 노드들을 순차적으로 탐색해야 하므로 랜덤 접근 시간이 느립니다.
2. 삽입 (Insert):
⦁ 시작 또는 끝에 삽입: O(1)
⦁ 중간에 삽입: O(1) (특정 위치를 찾는 시간 제외)
⦁ 설명: 특정 노드를 찾아 삽입하는 경우는 O(n) 시간이 걸리지만, 찾은 후 삽입 자체는 O(1)입니다.
3. 삭제 (Remove):
⦁ 시작 또는 끝에서 삭제: O(1)
⦁ 중간에서 삭제: O(1) (특정 위치를 찾는 시간 제외)
⦁ 설명: 특정 노드를 찾아 삭제하는 경우는 O(n) 시간이 걸리지만, 찾은 후 삭제 자체는 O(1)입니다.
4. 탐색 (Search):
⦁ 시간 복잡도: O(n)
⦁ 설명: 특정 요소를 찾기 위해서는 순차적으로 탐색해야 하므로 O(n)의 시간이 걸립니다.
성능 평가 요약
⦁ 랜덤 접근:
⦁ ArrayList: O(1) (우수)
⦁ LinkedList: O(n) (비효율적)
⦁ 삽입:
⦁ 끝에 삽입: ArrayList가 평균적으로 O(1)
⦁ 중간에 삽입: LinkedList가 O(1) (특정 위치를 찾는 시간 제외, 전체는 O(n))
⦁ 삭제:
⦁ 끝에서 삭제: ArrayList가 O(1)
⦁ 중간에서 삭제: LinkedList가 O(1) (특정 위치를 찾는 시간 제외, 전체는 O(n))
⦁ 탐색:
⦁ 둘 다 O(n) : 둘 다 특정 값을 찾기 위해 순차적으로 탐색
결론
⦁ ArrayList: 랜덤 접근이 빠르고, 끝에 요소를 추가/삭제하는 경우 효율적입니다. 하지만 중간에 삽입/삭제하는 경우는 비효율적입니다.
⦁ LinkedList: 삽입과 삭제가 빈번히 발생하는 경우 특히 리스트의 앞뒤에서의 삽입/삭제가 효율적입니다. 그러나 랜덤 접근이나 탐색 성능은 떨어집니다.
따라서, 상황에 따라 적절한 자료구조를 선택하는 것이 중요합니다. 랜덤 접근이 많고 중간 삽입/삭제가 적은 경우 ArrayList가 적합하고, 삽입/삭제가 빈번히 발생하는 경우 LinkedList가 더 적합합니다.
The Deque Interface
일반적으로 "덱[deck]"이라고 발음되는 deque는 double-ended-queue입니다. double-ended-queue는 양쪽 끝점에서 element를 삽입하고 제거할 수 있는 선형 엘리먼트 컬렉션입니다. Deque 인터페이스는 Stack과 Queue보다 더 풍부한 추상 데이터 타입으로, 스택과 큐를 동시에 구현합니다. Deque 인터페이스는 Deque 인스턴스의 양쪽 끝에서 엘리먼트에 접근하는 메서드를 정의합니다. 엘리먼트를 삽입하고 제거하며 살펴보는 메서드가 제공됩니다. ArrayDeque와 LinkedList와 같은 미리 정의된 클래스들은 Deque 인터페이스를 구현합니다.
대부분의 Deque 구현은 포함할 수 있는 엘리먼트 개수에 고정된 제한을 두지 않지만, 이 인터페이스는 용량이 제한된 deque와 고정된 크기 제한이 없는 deque를 모두 지원합니다.
이 인터페이스는 deque의 양 끝에서 element에 접근할 수 있는 메서드를 정의합니다. 엘리먼트를 삽입, 제거 및 검사하기 위한 메서드가 제공됩니다. 이러한 메서드는 각각 두 가지 형태로 존재합니다:
- 하나는 작업이 실패할 경우 예외를 던지며,
- 다른 하나는 작업이 실패할 경우 특별한 값(작업에 따라 null 또는 false)을 반환합니다.
후자의 삽입 작업 형태는 용량이 제한된 Deque 구현에서 사용하도록 설계되었습니다; 대부분의 Deque 구현에서는 삽입 작업이 실패할 수 없습니다.
위에서 설명한 12가지 메서드는 다음 표에 요약되어 있습니다:
Summary of Deque methods
이 인터페이스는 Queue 인터페이스를 확장합니다. deque가 큐로 사용될 때, FIFO(First-In-First-Out) 방식으로 동작합니다. 엘리먼트는 deque의 끝에 추가되고 처음에서 제거됩니다. Queue 인터페이스에서 상속된 메서드는 다음 표에 나타낸 바와 같이 Deque 메서드와 정확히 동일합니다:
Queue 메서드와 동일한 Deque 메서드
| Queue 메서드 | 동일한 Deque 메서드 |
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
Deque는 LIFO(Last-In-First-Out) 스택으로도 사용될 수 있습니다. 이 인터페이스는 레거시 Stack 클래스보다 우선적으로 사용되어야 합니다. Deque가 스택으로 사용될 때, 엘리먼트는 Deque의 처음에서 푸시(push)되고 팝(pop)됩니다. 스택 메서드는 아래 표에 나타낸 바와 같이 Deque 메서드와 동일합니다:
Stack과 Deque 메서드 비교
| Stack Method | Equivalent Deque Method |
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | getFirst() |
peek 메서드는 deque가 큐로 사용될 때나 스택으로 사용될 때 모두 잘 작동합니다. 두 경우 모두 요소는 deque의 시작 부분에서 가져옵니다.
이 인터페이스는 내부 요소를 제거하기 위한 두 가지 메서드, removeFirstOccurrence와 removeLastOccurrence를 제공합니다.
List 인터페이스와 달리, 이 인터페이스는 엘리먼트에 대한 인덱스 접근을 지원하지 않습니다.
Deque 구현은 null 엘리먼트 삽입을 금지하도록 엄격하게 요구되지는 않지만, 이를 강력히 권장합니다. null 요소를 허용하는 Deque 구현의 사용자도 null을 삽입하지 않도록 강력히 권장합니다. 이는 null이 다양한 메서드에서 deque가 비어 있음을 나타내는 특별한 반환 값으로 사용되기 때문입니다.
Deque 구현은 일반적으로 엘리먼트 기반의 equals와 hashCode 메서드를 정의하지 않고, 대신 Object 클래스에서 상속된 식별 기반 버전을 사용합니다.
Deque 인터페이스는 후입선출(LIFO) 스택과 선입선출(FIFO) 큐로 모두 사용할 수 있습니다.
Deque 인터페이스에 제공되는 메서드는 세 부분으로 나눌 수 있습니다:
Insert
addFirst와 offerFirst 메서드는 엘리먼트를 Deque 인스턴스의 시작 부분에 삽입합니다. addLast와 offerLast 메서드는 엘리먼트를 Deque 인스턴스의 끝 부분에 삽입합니다. Deque 인스턴스의 용량이 제한된 경우, addFirst는 가득 찬 경우 예외를 던지지 않을 수 있기 때문에 offerFirst와 offerLast 메서드를 사용하는 것이 좋습니다.
Deque 클래스와 Modulus 개념
Deque 인터페이스를 구현하는 ArrayDeque 클래스는 내부적으로 원형 버퍼를 사용하여 요소를 관리합니다. 원형 버퍼의 특성상, 엘리먼트를 추가하거나 제거할 때 인덱스를 관리하기 위해 modulus 연산이 사용될 수 있습니다. 이는 배열의 시작과 끝이 연결된 것처럼 동작하게 하여 효율적인 메모리 사용과 빠른 접근을 가능하게 합니다.
원형 버퍼와 Modulus 연산
원형 버퍼는 배열의 시작과 끝이 연결되어 있는 구조입니다. 이 구조를 사용할 때, modulus 연산을 통해 배열의 경계를 넘어서지 않고 인덱스를 순환시킬 수 있습니다.
/**
* Circularly decrements i, mod modulus.
* Precondition and postcondition: 0 <= i < modulus.
*/
// 첫번째 파라미터의 아규먼트로 Head[Front] 값을 전달함
// 두번째 파라미터의 아규먼트로 엘리먼트 개수를 전달함static final int dec(int i, int modulus) {
if (--i < 0) i = modulus - 1;
return i;
}
최초 엘리먼트 삽입은 원형 큐의 끝에 삽입합니다.
Remove
removeFirst와 pollFirst 메서드는 Deque 인스턴스의 시작 부분에서 엘리먼트를 제거합니다. removeLast와 pollLast 메서드는 끝 부분에서 엘리먼트를 제거합니다. pollFirst와 pollLast 메서드는 Deque가 비어 있을 경우 null을 반환하는 반면, removeFirst와 removeLast 메서드는 Deque 인스턴스가 비어 있을 경우 예외를 던집니다.
Retrieve
getFirst와 peekFirst 메서드는 Deque 인스턴스의 첫 번째 엘리먼트를 가져옵니다. 이 메서드들은 Deque 인스턴스에서 값을 제거하지 않습니다. 비슷하게, getLast와 peekLast 메서드는 마지막 엘리먼트를 가져옵니다. getFirst와 getLast 메서드는 Deque 인스턴스가 비어 있을 경우 예외를 던지는 반면, peekFirst와 peekLast 메서드는 null을 반환합니다.
예제:
아래는 Deque 인터페이스의 주요 메서드들을 사용하는 샘플 코드입니다. 이 코드는 ArrayDeque를 사용하여 Deque 인스턴스를 생성하고, 엘리먼트를 삽입하고 제거하며 조회하는 방법을 보여줍니다.
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.NoSuchElementException;
public class DequeExample {
public static void main(String[] args) {
// Deque 인스턴스 생성
Deque<String> deque = new ArrayDeque<>();
// Insert
deque.addFirst("A"); // Deque: A
deque.addLast("B"); // Deque: A, B
deque.offerFirst("C"); // Deque: C, A, B
deque.offerLast("D"); // Deque: C, A, B, D
System.out.println("Deque after insertions: " + deque);
// Remove
System.out.println("Removed with removeFirst(): " + deque.removeFirst()); // C
System.out.println("Removed with removeLast(): " + deque.removeLast()); // D
System.out.println("Removed with pollFirst(): " + deque.pollFirst()); // A
System.out.println("Removed with pollLast(): " + deque.pollLast()); // B
// Deque is now empty
System.out.println("Deque after removals: " + deque);
// Retrieve
try {
System.out.println("Retrieved with getFirst(): " + deque.getFirst());
} catch (NoSuchElementException e) {
System.out.println("Exception caught: " + e.getMessage());
}
try {
System.out.println("Retrieved with getLast(): " + deque.getLast());
} catch (NoSuchElementException e) {
System.out.println("Exception caught: " + e.getMessage());
}
System.out.println("Retrieved with peekFirst(): " + deque.peekFirst()); // null
System.out.println("Retrieved with peekLast(): " + deque.peekLast()); // null
// 다시 엘리먼트 추가
deque.offerFirst("E"); // Deque: E
deque.offerLast("F"); // Deque: E, F
System.out.println("Deque after re-adding elements: " + deque);
// 엘리먼트 조회
System.out.println("Retrieved with getFirst(): " + deque.getFirst()); // E
System.out.println("Retrieved with getLast(): " + deque.getLast()); // F
System.out.println("Retrieved with peekFirst(): " + deque.peekFirst()); // E
System.out.println("Retrieved with peekLast(): " + deque.peekLast()); // F
}
}
이 예제에서는 다음과 같은 작업을 수행합니다:
1. ArrayDeque를 사용하여 Deque 인스턴스를 생성합니다.
2. addFirst, addLast, offerFirst, offerLast 메서드를 사용하여 엘리먼트를 삽입합니다.
3. removeFirst, removeLast, pollFirst, pollLast 메서드를 사용하여 엘리먼트를 제거합니다.
4. getFirst, getLast, peekFirst, peekLast 메서드를 사용하여 엘리먼트를 조회합니다.
5. Deque가 비어 있을 때 getFirst와 getLast는 예외를 던지며, peekFirst와 peekLast는 null을 반환하는 것을 확인합니다.
6. 다시 엘리먼를 추가하고 조회하여 정상 동작을 확인합니다.
이 샘플 코드는 Deque 인터페이스의 다양한 메서드들이 어떻게 동작하는지 명확히 보여줍니다.
Deque 엘리먼트의 삽입, 제거 및 조회를 위한 12개의 메서드는 다음 테이블과 같이 요약됩니다:
Deque Methods
| Type of Operation | First Element(Beginning of the Deque instance) | Last Element(End of the Deque Instance) |
| Insert | addFirst(e) offerFirtst(e) |
addLast(e) offerLast(e) |
| Remove | removeFirst() pollFirst() |
removeLast() pollLast() |
| Examine | getFirst() peekFirst() |
getLast() peekLast() |
이러한 기본적인 삽입, 제거 및 조회 메서드 외에도, Deque 인터페이스에는 몇 가지 미리 정의된 메서드가 더 있습니다. 그 중 하나는 removeFirstOccurrence 메서드로, 지정된 엘리먼트의 첫 번째 발생을 제거합니다. Deque 인스턴스에 해당 엘리먼트가 존재하지 않으면, Deque 인스턴스는 변경되지 않습니다. 이와 비슷한 메서드로 removeLastOccurrence가 있으며, 이는 Deque 인스턴스에서 지정된 엘리먼트의 마지막 발생을 제거합니다. 이러한 메서드의 리턴 타입은 boolean이며, Deque 인스턴스에 엘리먼트가 존재하는 경우 true를 리턴합니다.
다음은 removeFirstOccurrence와 removeLastOccurrence 메서드를 사용하는 샘플 코드입니다. 이 코드는 Deque 인스턴스에서 지정된 엘리먼트의 첫 번째 및 마지막 발생을 제거하는 방법을 보여줍니다.
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeRemoveOccurrenceExample {
public static void main(String[] args) {
// Deque 인스턴스 생성
Deque<String> deque = new ArrayDeque<>();
// 요소 추가
deque.add("A");
deque.add("B");
deque.add("A");
deque.add("C");
deque.add("A");
deque.add("D");
// 초기 Deque 상태 출력
System.out.println("Initial Deque: " + deque);
// removeFirstOccurrence 메서드로 첫 번째 "A" 제거
boolean removedFirst = deque.removeFirstOccurrence("A");
System.out.println("After removeFirstOccurrence(\"A\"): " + deque + " (removed: " + removedFirst + ")");
// removeLastOccurrence 메서드로 마지막 "A" 제거
boolean removedLast = deque.removeLastOccurrence("A");
System.out.println("After removeLastOccurrence(\"A\"): " + deque + " (removed: " + removedLast + ")");
// 존재하지 않는 엘리먼트 제거 시도
boolean removedNonExistent = deque.removeFirstOccurrence("Z");
System.out.println("After removeFirstOccurrence(\"Z\"): " + deque + " (removed: " + removedNonExistent + ")");
// 최종 Deque 상태 출력
System.out.println("Final Deque: " + deque);
}
}
이 예제에서는 다음과 같은 작업을 수행합니다:
1. ArrayDeque를 사용하여 Deque 인스턴스를 생성합니다.
2. 몇 개의 엘리먼트를 추가합니다. 엘리먼트 "A"는 여러 번 추가됩니다.
3. 초기 Deque의 상태를 출력합니다.
4. removeFirstOccurrence 메서드를 사용하여 첫 번째 "A"를 제거합니다.
5. removeLastOccurrence 메서드를 사용하여 마지막 "A"를 제거합니다.
6. 존재하지 않는 요소 "Z"를 제거하려고 시도합니다.
7. 최종 Deque의 상태를 출력합니다.
이 샘플 코드는 removeFirstOccurrence와 removeLastOccurrence 메서드가 어떻게 동작하는지 명확히 보여줍니다. 각 메서드는 지정된 엘리먼트가 Deque에 존재하는 경우 해당 엘리먼트를 제거하고, 존재하지 않는 경우 아무 것도 제거하지 않습니다. 메서드의 리턴 값은 제거가 성공했는지 여부를 나타냅니다.
'High Level Programming Language > Collections' 카테고리의 다른 글
| Lesson: Introduction to Collections 4 (0) | 2024.06.21 |
|---|---|
| Lesson: Introduction to Collections 2 (0) | 2024.06.16 |
| Lesson: Introduction to Collections 1 (0) | 2024.06.10 |
| Java Collection Framework-Hash, Hash Table, Map, Set (0) | 2023.06.14 |
| Java Collection Framework-List, ArrayList, LinkedList, (0) | 2023.06.14 |