[자료구조] 덱(Deque)이란?

덱이란?

• 덱은 "double-ended queue"의 줄인말로, 양끝에서 삽입 삭제가 가능한 큐를 의미한다.
• 즉, 덱은 큐와 스택의 특징을 모두 지닌다.

덱의 종류

1. 스크롤(scroll) : 삽입이 한쪽 끝으로만 가능하도록 설정한 데크(입력 제한 데크)
2. 셀프(self) : 삭제가 한쪽 끝으로만 가능하도록 설정한 데크(출력 제한 데크)

덱의 특징

• 덱은 양 방향에서 삽입과 삭제가 동시에 일어날 수 있다.
• 종류에 따라 스크롤 덱과 셀프 덱을 구현할 수도 있다.
• 동적으로 크기를 조절할 수 있다.
• 덱의 연산은 덱의 앞에 원소 추가, 덱의 뒤에 원소 추가, 덱의 앞에 있는 원소 삭제, 덱의 뒤에 있는 원소 삭제, 덱의 앞에 있는 원소 읽기, 덱의 뒤에 있는 원소 읽기, 사이즈 확인, 비어있는지 확인이 있다.

덱의 시간복잡도

1. 덱의 앞에 원소 추가(addFirst)
   • 덱의 앞에 원소를 추가한다.
   • 따라서 시간복잡도는 O(1)이다.
2. 덱의 뒤에 원소 추가(addLast)
   • 덱의 뒤에 원소를 추가한다.
   • 따라서 시간복잡도는 O(1)이다.
3. 덱의 앞에 있는 원소 삭제(removeFirst)
   • 덱의 앞에 있는 원소를 삭제한다.
   • 따라서 시간복잡도는 O(1)이다.
4. 덱의 뒤에 있는 원소 삭제(removeLast)
   • 덱의 뒤에 있는 원소를 삭제한다.
   • 따라서 시간복잡도는 O(1)이다.
5. 덱의 앞에 있는 원소 읽기(peekFirst)
   • 덱의 앞에 있는 원소를 읽어온다.
   • 따라서 시간복잡도는 O(1)이다.
6. 덱의 뒤에 있는 원소 읽기(peekLast)
   • 덱의 뒤에 있는 원소를 읽어온다.
   • 따라서 시간복잡도는 O(1)이다.
7. 덱의 사이즈 확인(size)
   • 덱의 사이즈를 확인한다.
   • 따라서 시간복잡도는 O(1)이다.
8. 덱이 비어있는지 확인(isEmpty)
   • 덱이 비어있는지 확인한다.
   • 따라서 시간복잡도는 O(1)이다.

덱의 장단점

1. 장점
   • 양쪽에서 삽입 삭제가 모두 가능하여 양쪽 끝 연산이 모두 O(1)이 된다.
   • 슬라이싱 윈도우, 양방향 탐색, 최단 경로 알고리즘 등 여러 알고리즘에서 사용할 수 있다.
   • 큐와 스택의 특징을 모두 갖고잇어, 상황에 따라 유연하게 활용할 수 있다.
2. 단점
   • 양쪽의 연산을 모두 효율적으로 지원해야 하기에 구현이 간단하지 않을 수 있다.
   • 덱의 크기를 동적으로 조절하기 때문에 메모리 낭비가 클 수 있다.

예제

import java.util.*;

fun main() {
    var deque = ArrayDeque<Int>()
    deque.addFirst(1)
    deque.addLast(2)
    deque.addFirst(3)
    println(deque.first)
    println(deque.last)
    deque.removeLast()
    deque.removeFirst()
    deque.removeFirst()
}

 

출처 : 덱 - 위키백과