데크 (Deque)
자료구조
Java에서 데크(Deque)는 "Double Ended Queue"의 약자로,
양 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.
즉, 큐(Queue)와 스택(Stack)의 기능을 모두 가지고 있다.
Java에서 데크는 java.util.Deque 인터페이스를 구현한 클래스들로 사용할 수 있다.
예를 들어 LinkedList 클래스는 Deque 인터페이스를 구현하므로,
LinkedList 인스턴스를 Deque로 사용할 수 있다.
데크는 양쪽에서 삽입과 삭제가 가능하기 때문에 큐나 스택으로 사용할 수 있고,
알고리즘 문제를 풀 때 유용하게 사용된다.
데크 관련 메소드
-
addFirst(E e) : 데크의 앞쪽에 요소를 추가한다.
-
addLast(E e) : 데크의 뒤쪽에 요소를 추가한다.
-
offerFirst(E e) : 데크의 앞쪽에 요소를 추가한다.
추가에 성공하면true를 반환하고, 데크가 가득 차있다면false를 반환한다. -
offerLast(E e) : 데크의 뒤쪽에 요소를 추가한다.
추가에 성공하면true를 반환하고, 데크가 가득 차있다면false를 반환한다. -
removeFirst() : 데크의 첫 번째 요소를 삭제하고 반환한다.
만약 데크가 비어있다면NoSuchElementException이 발생한다. -
removeLast() : 데크의 마지막 요소를 삭제하고 반환한다.
만약 데크가 비어있다면NoSuchElementException이 발생한다. -
pollFirst() : 데크의 첫 번째 요소를 삭제하고 반환한다.
만약 데크가 비어있다면null을 반환한다. -
pollLast() : 데크의 마지막 요소를 삭제하고 반환한다.
만약 데크가 비어있다면null을 반환한다. -
getFirst() : 데크의 첫 번째 요소를 반환한다.
만약 데크가 비어있다면NoSuchElementException이 발생한다. -
getLast() : 데크의 마지막 요소를 반환한다.
만약 데크가 비어있다면NoSuchElementException이 발생한다. -
peekFirst() : 데크의 첫 번째 요소를 반환한다.
만약 데크가 비어있다면null을 반환한다. -
peekLast() : 데크의 마지막 요소를 반환한다.
만약 데크가 비어있다면null을 반환한다. -
size() : 데크의 요소
개수를 반환한다. -
isEmpty() : 데크가 비어있는지
여부를 반환한다.
🌏 Chat-GPT 예제소스들
1. Deque 기본 예제소스
import java.util.ArrayDeque;
import java.util.Deque;
public class ArrayDequeExample {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1); // 데크의 앞쪽에 1을 삽입
deque.addLast(2); // 데크의 뒤쪽에 2를 삽입
deque.offerFirst(3); // 데크의 앞쪽에 3을 삽입
deque.offerLast(4); // 데크의 뒤쪽에 4를 삽입
System.out.println(deque); // [3, 1, 2, 4]
System.out.println(deque.getFirst()); // 3
System.out.println(deque.getLast()); // 4
System.out.println(deque.pollFirst()); // 3
System.out.println(deque.pollLast()); // 4
System.out.println(deque); // [1, 2]
}
}2. 입력제한 데크
Deque 인터페이스를 구현한 LinkedList 클래스를 사용하여 입력 제한을 구현할 수 있다.
이를 위해, add() 메소드를 오버라이딩하여 입력 제한을 설정한다.
😀 입력 제한이 '5'인 Deque를 만들어보자.
import java.util.Deque;
import java.util.LinkedList;
public class LimitedDeque<E> extends LinkedList<E> implements Deque<E> {
private final int limit;
public LimitedDeque(int limit) {
this.limit = limit;
}
@Override
public boolean add(E e) {
if (size() >= limit) {
throw new IllegalStateException("Deque is full");
}
return super.add(e);
}
// 기타 Deque 인터페이스의 메소드들을 구현해야 합니다.
public static void main(String[] args) {
// LimitedDeque클래스의 객체를 만들어 입력제한 Deque를 만들 수 있다.
deque.add(1);
deque.add(2);
deque.add(3);
deque.add(4);
deque.add(5);
// 다음 라인에서 예외 발생
deque.add(6);
}
}
위 코드에서, 입력 제한이 5인 Deque를 생성한 후, 1부터 5까지의 정수를 추가한다.
마지막으로, Deque가 가득 찬 상태에서 6을 추가하려고 하면 예외가 발생한다.
3. 데이터 재정렬
{1, 2, 3, 4, 5}를 Deque를 이용하여 {1, 2, 5, 3, 4}로 재정렬하기
import java.util.*;
public class DequeReorderingExample {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
Deque<Integer> deque = new LinkedList<>();
// 배열을 Deque에 추가
for (int i : arr) {
deque.add(i);
}
// 재정렬된 데이터를 담을 배열
int[] reorderedArr = new int[arr.length];
// Deque에서 앞쪽 두 데이터를 꺼내서 배열에 추가
reorderedArr[0] = deque.removeFirst();
reorderedArr[1] = deque.removeFirst();
// Deque에서 뒤쪽 데이터를 꺼내서 배열 끝에 추가
reorderedArr[arr.length-1] = deque.removeLast();
// Deque에서 남은 데이터를 앞쪽부터 배열에 추가
int index = 2;
while (!deque.isEmpty()) {
reorderedArr[index++] = deque.removeFirst();
}
// 재정렬된 배열 출력
System.out.println(Arrays.toString(reorderedArr));
} [1, 2, 5, 3, 4]
}위 코드에서, 먼저 Deque에 입력된 배열을 추가한다.
그 다음, Deque에서 앞쪽 두 데이터를 꺼내서 배열의 첫 두 칸에 추가하고, Deque에서 뒤쪽 데이터를 꺼내서 배열의 마지막 칸에 추가한다. 마지막으로, Deque에서 남은 데이터를 앞쪽부터 배열에 추가하여 {1, 2, 5, 3, 4}로 재정렬한다.
4. 팰린드롬(Palindrome) 판별
Palindrome(팰린드롬)은 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 단어, 구절, 문장, 수 등을 의미합니다. 예를 들면, "level", "racecar", "A man, a plan, a canal, Panama!" 등이 팰린드롬의 예시이다. (기러기,토마토)
import java.util.Scanner;
public class PalindromeExample {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("문자열을 입력하세요: ");
String str = scanner.nextLine();
// 대소문자를 구분하지 않고, 공백을 제거하여 문자열을 정제합니다.
String refinedStr = str.toLowerCase().replaceAll("\\s", "");
boolean isPalindrome = true;
// 문자열의 가운데를 중심으로 좌우 대칭인지 확인합니다.
int len = refinedStr.length();
for (int i = 0; i < len / 2; i++) {
if (refinedStr.charAt(i) != refinedStr.charAt(len - i - 1)) {
isPalindrome = false;
break;
}
}
// 결과 출력
if (isPalindrome) {
System.out.println("입력한 문자열은 팰린드롬입니다.");
} else {
System.out.println("입력한 문자열은 팰린드롬이 아닙니다.");
}
}
}위 코드에서, 사용자로부터 입력받은 문자열에서 대소문자를 구분하지 않고, 공백을 제거하여 문자열을 정제한다. 그 다음, 문자열의 가운데를 중심으로 좌우 대칭인지 확인하여 팰린드롬인지 판별한다.
위 코드의 가장 핵심은 팰린드롬 판별 알고리즘 부분이다.
boolean isPalindrome = true;
// 문자열의 가운데를 중심으로 좌우 대칭인지 확인합니다.
int len = refinedStr.length();
for (int i = 0; i < len / 2; i++) {
if (refinedStr.charAt(i) != refinedStr.charAt(len - i - 1)) {
isPalindrome = false;
break;
}
}위 코드에서, 문자열의 길이를 len 변수에 저장한 후, 문자열의 가운데를 중심으로 좌우 대칭인지 확인한다. for문에서 변수 i는 문자열의 첫 번째 문자부터 가운데까지 순차적으로 접근한다. 이 때, 문자열의 길이가 홀수인 경우 가운데 문자는 대칭이 아니기 때문에 len / 2까지만 순회한다. 문자열의 첫 번째 문자와 마지막 문자부터 순서대로 비교하며, 하나라도 다른 문자가 나오면 팰린드롬이 아니므로 isPalindrome 변수를 false로 설정하고 반복문을 빠져나간다. 팰린드롬인지 아닌지에 따라 결과를 출력한다.
5. 데크 변형 (중간 데이터 추가)
주어진 배열 {2, 4, 8, 10}에서 가운데에 6을 추가하여 {2, 4, 6, 8, 10}으로 변형하는 예제 소스코드다. 이 문제에서는 입력 제한이 필요하지 않기 때문에, 일반적인 Deque을 사용하여 구현할 수 있다.
import java.util.*;
public class DequeExample {
public static void main(String[] args) {
int[] arr = {2, 4, 8, 10};
Deque<Integer> deque = new LinkedList<>();
// 배열의 중앙에 해당하는 위치에 6을 추가하기 위해,
// 배열의 가운데 위치를 구합니다.
int middle = arr.length / 2;
// 배열의 데이터를 Deque에 추가합니다.
for (int i : arr) {
deque.add(i);
}
// Deque에서 중앙 위치 이전의 데이터를 모두 제거합니다.
// 그리고 중앙 위치에 6을 추가합니다.
for (int i = 0; i < middle; i++) {
deque.removeFirst();
}
deque.addFirst(6);
// Deque에서 데이터를 꺼내 배열에 저장합니다.
int[] newArr = new int[arr.length + 1];
for (int i = 0; i < newArr.length; i++) {
newArr[i] = deque.removeFirst();
}
// 결과 출력
System.out.println(Arrays.toString(newArr));
} // [2, 4, 6, 8, 10]
}위 코드에서는 먼저 '6'을 넣을 가운데 위치를 구하고, Deque에 배열의 데이터를 추가한다. 그리고, 배열의 중앙 위치 이전의 데이터를 모두 제거하고 중앙 위치에 6을 추가한다. 이 과정을 통해, Deque에서는 {2, 4, 6, 8, 10}이 남게 된다. 마지막으로, Deque에서 데이터를 꺼내어 새로운 배열에 저장하여 {2, 4, 6, 8, 10}을 출력한다.
6. 데크 공간 2배로 늘리기
Deque에서 공간이 부족할 때, 일반적인 방법은 Deque의 크기를 동적으로 늘려주는 것이다. 이때 Deque의 크기를 2배씩 늘려주는 방법은 대표적인 방법 중 하나입니다. 다음은 공간이 부족할 때 Deque의 크기를 2배씩 늘려주는 예제 코드다.
import java.util.*;
public class DequeExpansionExample {
public static void main(String[] args) {
Deque<Integer> deque = new ArrayDeque<>(2);
int[] arr = {1, 2, 3, 4, 5};
// 배열의 데이터를 Deque에 추가합니다.
for (int i : arr) {
deque.add(i);
}
// Deque의 공간이 부족할 경우, 크기를 2배씩 늘려줍니다.
for (int i = 6; i <= 10; i++) {
deque.add(i);
if (deque.size() == deque.toArray().length) {
deque = expandDeque(deque);
}
}
// 결과 출력 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
System.out.println(Arrays.toString(deque.toArray()));
}
// Deque의 크기를 2배로 늘려주는 메서드
private static Deque<Integer> expandDeque(Deque<Integer> deque) {
Deque<Integer> newDeque = new ArrayDeque<>(deque.toArray().length * 2);
newDeque.addAll(deque);
return newDeque;
}
}위 코드에서, Deque에 데이터를 추가하면서 Deque의 크기가 부족해질 경우 크기를 2배씩 늘려준다. 이 때 Deque의 크기를 늘리기 위해 expandDeque 메소드를 호출한다. 이 메서드는 Deque의 크기를 2배로 늘린 후, 기존의 Deque에 있는 데이터를 새로운 Deque으로 복사한다.
