덱이라?
자료구조 덱은 Double Ended QUEue의 축약어로, "deck"으로 발음하게 되어있다. 하지만 데크, 디큐 등의 표기나 발음이 존재할 수 있다.
덱의 풀네임인 double ended queue에서 알 수 있듯 기본적으로 큐의 동작을 양방향으로 지원하는 자료구조이다.
덱의 주요 사용처
양쪽에서의 삽입과 삭제가 필요한 경우
특정 알고리즘이나 문제 해결에서 양쪽 끝에서 삽입과 삭제를 해야 하는 경우 덱을 사용하면 효율적입니다. 예를 들어, BFS(Breadth-First Search) 알고리즘에서 각 레벨의 노드를 추적할 때 덱을 사용할 수 있습니다.
슬라이딩 윈도우 문제
주어진 배열에서 슬라이딩 윈도우의 최대값이나 최소값을 찾는 문제에서 덱을 사용하면 효율적으로 해결할 수 있습니다. 덱을 이용하면 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.
팔린드롬 검사
문자열이 팔린드롬인지 확인할 때 덱을 사용하여 양쪽 끝에서 문자를 비교할 수 있습니다. 이를 통해 효율적으로 문자열의 대칭성을 검사할 수 있습니다.
이중 버퍼링
그래픽스나 멀티미디어 처리에서 이중 버퍼링을 구현할 때 덱을 사용하여 두 버퍼를 관리할 수 있습니다. 이로 인해 부드러운 전환과 효율적인 데이터 처리가 가능합니다.
덱 메서드
-
init : 리스트를 초기화하는 함수
-
enqueue : 데이터 입력
-
enqueueFront : 앞쪽 방향에 데이터 입력
-
dequeue : 첫번째 데이터 삭제
-
dequeueBack : 뒤쪽 방향의 데이터 삭제
-
peekFront : 첫번째 데이터 반환
-
peekBack : 마지막 데이터 반환
-
removeAll : 모든 데이터 삭제
-
count : 현재 리스트의 크기를 반환
-
isEmpty : 현재 리스트의 크기가 비어있는지 체크
덱 구현
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeExample {
public static void main(String[] args) {
// Deque 초기화
Deque<Integer> deque = new ArrayDeque<>();
// 요소 추가
deque.addLast(1); // 오른쪽 끝에 1 추가 (append와 동일)
deque.addFirst(2); // 왼쪽 끝에 2 추가 (appendleft와 동일)
// 요소 제거 및 출력
System.out.println("오른쪽 끝 요소 제거: " + deque.removeLast()); // 오른쪽 끝 요소 제거 후 반환 (pop과 동일)
System.out.println("왼쪽 끝 요소 제거: " + deque.removeFirst()); // 왼쪽 끝 요소 제거 후 반환 (popleft와 동일)
// 덱에 요소 다시 추가
deque.addLast(3);
deque.addLast(4);
deque.addFirst(5);
// 덱의 상태 출력
System.out.println("현재 덱: " + deque);
// 덱의 첫 요소와 마지막 요소 확인
System.out.println("첫 요소: " + deque.peekFirst()); // 첫 요소 확인 (삭제하지 않음)
System.out.println("마지막 요소: " + deque.peekLast()); // 마지막 요소 확인 (삭제하지 않음)
}
}참고 사이트
[자료구조] Dequeue(데크) : Doubly-ended Queue, 스택과 큐의 장점을 모아서 만든 자료구조
