데크 (Deque)

han.user();·2023년 3월 15일
DequeSizeaddFirstaddLastgetFirstgetLastisEmpty()linkedlistofferFirstofferLastpalindromepeekFirstpeekLastpollFirstpollLastremoveFirstremoveLast공간데이터데크변형알고리즘예제소스입력제한재정렬팰린드럼팰린드롬??
0

자료구조

목록 보기
6/14
post-thumbnail

Java에서 데크(Deque)는 "Double Ended Queue"의 약자로,
양 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.
즉, 큐(Queue)와 스택(Stack)의 기능을 모두 가지고 있다.

Java에서 데크는 java.util.Deque 인터페이스를 구현한 클래스들로 사용할 수 있다.
예를 들어 LinkedList 클래스는 Deque 인터페이스를 구현하므로,
LinkedList 인스턴스를 Deque로 사용할 수 있다.

데크는 양쪽에서 삽입과 삭제가 가능하기 때문에 큐나 스택으로 사용할 수 있고,
알고리즘 문제를 풀 때 유용하게 사용된다.

데크 관련 메소드

  1. addFirst(E e) : 데크의 앞쪽에 요소를 추가한다.

  2. addLast(E e) : 데크의 뒤쪽에 요소를 추가한다.

  3. offerFirst(E e) : 데크의 앞쪽에 요소를 추가한다.
    추가에 성공하면 true를 반환하고, 데크가 가득 차있다면 false를 반환한다.

  4. offerLast(E e) : 데크의 뒤쪽에 요소를 추가한다.
    추가에 성공하면 true를 반환하고, 데크가 가득 차있다면 false를 반환한다.

  5. removeFirst() : 데크의 첫 번째 요소를 삭제하고 반환한다.
    만약 데크가 비어있다면 NoSuchElementException이 발생한다.

  6. removeLast() : 데크의 마지막 요소를 삭제하고 반환한다.
    만약 데크가 비어있다면 NoSuchElementException이 발생한다.

  7. pollFirst() : 데크의 첫 번째 요소를 삭제하고 반환한다.
    만약 데크가 비어있다면 null을 반환한다.

  8. pollLast() : 데크의 마지막 요소를 삭제하고 반환한다.
    만약 데크가 비어있다면 null을 반환한다.

  9. getFirst() : 데크의 첫 번째 요소를 반환한다.
    만약 데크가 비어있다면 NoSuchElementException이 발생한다.

  10. getLast() : 데크의 마지막 요소를 반환한다.
    만약 데크가 비어있다면 NoSuchElementException이 발생한다.

  11. peekFirst() : 데크의 첫 번째 요소를 반환한다.
    만약 데크가 비어있다면 null을 반환한다.

  12. peekLast() : 데크의 마지막 요소를 반환한다.
    만약 데크가 비어있다면 null을 반환한다.

  13. size() : 데크의 요소 개수를 반환한다.

  14. 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으로 복사한다.

profile
han.user();
I'm still hungry.
이전 포스트

큐(Queue)

다음 포스트

해시 테이블 (Hash Table)

0개의 댓글

관련 채용 정보