덱 (자료 구조)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
덱(Deque)은 'Double-ended queue'의 약자로, 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조이다. 입력 제한 덱과 출력 제한 덱으로 구분되며, 큐와 스택을 덱을 사용하여 구현할 수 있다. 덱은 동적 배열 또는 이중 연결 리스트를 사용하여 구현할 수 있으며, 다양한 프로그래밍 언어에서 지원된다. 덱은 브라우징 기록 저장, 작업 훔치기 알고리즘 등 다양한 응용 분야에서 활용된다.
더 읽어볼만한 페이지
- 추상 자료형 - 리스트 (컴퓨팅)
리스트는 컴퓨터 과학에서 항목들을 순서대로 저장하고 관리하는 기본적인 자료 구조이며, 다양한 연산을 지원하고 연결 리스트나 동적 배열 등으로 구현되며 큐, 스택 등 다른 자료형의 기반이 된다. - 추상 자료형 - 스택
스택은 후입선출(LIFO) 원칙에 따라 데이터를 관리하는 추상 자료형으로, push 연산으로 데이터를 쌓고 pop 연산으로 가장 최근 데이터를 제거하며, 서브루틴 호출 관리, 수식 평가, 백트래킹 등에 활용된다. - 자료 구조 - 라우팅 테이블
라우팅 테이블은 네트워크에서 데이터 전송 시 최적 경로를 결정하는 핵심 데이터베이스로, 라우터가 목적지 IP 주소를 기반으로 다음 홉을 결정하며 직접 연결 및 원격 네트워크 경로 정보를 저장하고 동적 라우팅 또는 수동 설정으로 관리된다. - 자료 구조 - 스택
스택은 후입선출(LIFO) 원칙에 따라 데이터를 관리하는 추상 자료형으로, push 연산으로 데이터를 쌓고 pop 연산으로 가장 최근 데이터를 제거하며, 서브루틴 호출 관리, 수식 평가, 백트래킹 등에 활용된다.
2. 명칭
덱(deque)은 '디큐(dequeue)'로 표기되기도 하지만, "큐에서 제거하다"라는 동사로도 사용되기 때문에, 일반적으로 기술 문헌이나 기술 문서에서는 이 사용법을 권장하지 않는다.[1] 그럼에도 불구하고, 일부 라이브러리와 아호, 홉크로프트, 울만 등은 저서 ''자료 구조와 알고리즘''에서 '디큐'로 표기한다.[1] 존 미첼은 저서 ''프로그래밍 언어 개념''에서 이 용어를 사용한다.[1]
덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조이다. 덱은 크게 입력 제한 덱과 출력 제한 덱으로 나눌 수 있다.
3. 종류
큐와 스택은 덱의 특수한 경우이며, 덱을 사용하여 구현할 수 있다.[1]
3. 1. 입력 제한 덱 (Scroll)
삭제는 양쪽 끝에서 가능하지만, 삽입은 한쪽 끝에서만 할 수 있는 덱을 입력 제한 덱이라고 한다. 컴퓨팅에서 가장 기본적인 일반적인 리스트 유형인 큐와 스택은 덱의 특수한 경우로 간주될 수 있으며, 덱을 사용하여 구현할 수 있다.[1]
3. 2. 출력 제한 덱 (Shelf)
출력 제한 덱은 삽입은 양쪽 끝에서 가능하지만, 삭제는 한쪽 끝에서만 가능한 덱이다. 요소의 추가는 양쪽 끝에서 가능하지만, 꺼내기는 한쪽에서만 가능하다는 특징을 가진다.[1]
4. 연산
덱의 기본 연산은 양쪽 끝에서의 삽입(push)과 삭제(pop)이다. 엿보기(peek) 연산을 통해 삭제하지 않고 해당 끝의 값을 확인할 수 있다.
다음은 주요 프로그래밍 언어에서의 덱 연산 명칭이다.
5. 구현
덱은 동적 배열을 수정하거나 이중 연결 리스트를 사용하여 효율적으로 구현할 수 있다. 순수 함수형 자료 구조로도 구현할 수 있다.
5. 1. 동적 배열 구현
동적 배열을 수정하여 덱(자료 구조)을 구현할 수 있으며, 이를 '배열 덱'이라고도 한다. 배열 덱은 상수 시간 임의 접근과 우수한 참조 지역성을 가지며, 양쪽 끝에서 분할 상환 상수 시간으로 삽입/삭제가 가능하다. 구현 방법은 다음과 같다.- 링 버퍼에 덱 내용을 저장하고, 버퍼가 가득 찼을 때만 크기를 조정한다. 크기 조정 빈도를 줄일 수 있다.
- 기본 배열의 중앙에서 덱 내용을 할당하고, 양쪽 끝에 도달하면 배열 크기를 조정한다. 한쪽 끝에만 요소가 삽입될 경우 공간 낭비가 발생할 수 있다.
- 여러 개의 작은 배열에 내용을 저장하고, 시작 또는 끝에 추가 배열을 할당한다. 인덱싱은 각 작은 배열을 가리키는 포인터를 포함하는 동적 배열을 통해 구현된다.
5. 2. 순수 함수형 구현
순수 함수형 자료 구조로 덱(Deque)을 구현할 수 있다.[3] 이에는 두 가지 버전이 있다.첫 번째는 '''실시간 덱'''으로, 최악의 시간 내에 연산을 수행하면서 덱이 영구적 자료 구조가 되도록 한다. 하지만 이 구현은 레이지 평가를 사용한 메모이제이션이 있는 지연 리스트를 필요로 한다.
두 번째 버전은 지연 리스트나 메모이제이션을 사용하지 않는다. 이 버전은 영속성을 사용하지 않는 경우 분할 상환 분석 시간이 이지만, 연산의 최악 시간 복잡도는 이다. 여기서 는 덱에 있는 요소의 개수이다.
리스트 l영어에 대해, 은 리스트의 길이를, `NIL`은 빈 리스트를, `CONS(h, t)`는 헤드가 h영어이고 테일이 t영어인 리스트를 나타낸다. 함수 drop(i, l)영어과 take(i, l)영어은 리스트 l영어에서 처음 i영어개의 요소를 제외한 리스트와, l영어의 처음 i영어개의 요소를 각각 반환한다. 만약 < i영어이면, 빈 리스트와 l영어을 각각 반환한다.
덱은 6개의 튜플 `(len_front, front, tail_front, len_rear, rear, tail_rear)`로 표현된다. 여기서 front영어는 큐의 앞부분을 포함하는 연결 리스트이며 길이는 len_front영어이다. rear영어는 큐의 뒷부분의 역순을 나타내는 연결 리스트이며 길이는 len_rear영어이다. ≤ 2+1과 ≤ 2+1이 보장된다. 이는 앞부분과 뒷부분 모두 요소의 3분의 1 마이너스 1에서 3분의 2 플러스 1 사이의 요소를 포함한다는 것을 의미한다. tail_front영어 및 tail_rear영어는 front영어와 rear영어의 꼬리이며, 일부 지연된 연산이 강제되는 시점을 예약할 수 있게 한다. 덱이 앞쪽 리스트에 n영어개의 요소와 뒤쪽 리스트에 n영어개의 요소를 포함하는 경우, i영어번의 삽입과 d영어번의 삭제 후에도 부등식 불변성은 `(i+d) ≤ n/2`일 때 유지된다. 즉, 각 재균형 조정 사이에 최대 n/2영어번의 연산이 발생할 수 있다.
큐의 앞부분에 영향을 미치는 연산(cons, head, tail)의 구현은 다음과 같다. (뒷부분에 영향을 미치는 연산은 대칭적으로 정의된다.)
```sml
empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =
(len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =
(len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty
```
위 구현은 불변성을 반드시 준수하지는 않는다. 앞부분이 비어 있으면 뒷부분에 최대 하나의 요소가 있다는 불변성은 사용한다.
`insert'` 또는 `tail'`이 불변성을 깨뜨린 경우, `balance` 메서드를 사용하여 덱을 재균형 조정할 수 있다. `insert` 및 `tail` 메서드는 먼저 `insert'` 및 `tail'`을 적용한 다음 `balance`를 적용하여 정의한다.
```sml
fun balance(q as (len_front, front, tail_front, len_rear, rear, tail_rear)) =
let floor_half_len = (len_front + len_rear) / 2 in
let ceil_half_len = len_front + len_rear - floor_half_len in
if len_front > 2*len_rear+1 then
let val front' = take(ceil_half_len, front)
val rear' = rotateDrop(rear, floor_half_len, front)
in (ceil_half_len, front', front', floor_half_len, rear', rear')
else if len_front > 2*len_rear+1 then
let val rear' = take(floor_half_len, rear)
val front' = rotateDrop(front, ceil_half_len, rear)
in (ceil_half_len, front', front', floor_half_len, rear', rear')
else q
```
`rotateDrop(front, i, rear))`는 front영어와 drop(i, rear)영어의 연결을 반환한다. front' = rotateDrop(front, ceil_half_len, rear)영어는 front'영어에 front영어의 내용과 rear'영어에 아직 없는 rear영어의 내용을 넣는다. 각 `tail'` 및 각 `insert'` 연산 중에 두 번의 삭제가 수행되도록 지연 평가를 사용하여 요소를 두 개씩 삭제한다.
```sml
fun rotateDrop(front, i, rear) =
if i < 2 then rotateRev(front, drop(i, rear), NIL)
else let CONS(x, front') = front in
CONS(x, rotateDrop(front', j-2, drop(2, rear)))
```
`rotateRev(front, middle, rear)`는 앞부분, 뒤집힌 중간 부분, 뒷부분을 반환하는 함수이다. 이 함수는 각 `insert'` 및 `tail'` 중에 실행되고 상수 시간이 걸리도록 단계별로 계산할 수 있도록 지연 평가를 사용하여 정의된다. 이 함수는 -2가 2 또는 3이라는 불변성을 사용한다.
```sml
fun rotateRev(NIL, rear, a) =
reverse(rear)++a
fun rotateRev(CONS(x, front), rear, a) =
CONS(x, rotateRev(front, drop(2, rear), reverse(take(2, rear))++a))
```
여기서 `++`는 두 개의 리스트를 연결하는 함수이다.
지연 평가를 사용하지 않는 구현은 상각 시간으로 큐의 비영속적인 구현이 된다. 이 경우, 덱의 표현에서 tail_front영어 및 tail_rear영어 리스트를 제거할 수 있다.
6. 언어 지원
에이다는 동적 배열 구현을 위한 제네릭 패키지 `Ada.Containers.Vectors`와 연결 리스트 구현을 위한 `Ada.Containers.Doubly_Linked_Lists`를 제공한다.
C++의 STL는 `std::deque`와 `std::list` 클래스 템플릿을 제공한다. `std::deque`는 일반적으로 여러 개의 고정 크기 배열을 사용하여 구현되며, 양쪽 끝과 임의 접근을 지원한다. 중간 삽입/삭제는 *O*(*n*) 시간이 걸리는 반면, 양쪽 끝 삽입/삭제는 *O*(1)이다.
Java 6부터 Java 컬렉션 프레임워크는 `java.util.Deque` 인터페이스를 제공하며, `java.util.ArrayDeque`와 `java.util.LinkedList` 클래스로 구현된다. `ArrayDeque`는 동적 배열, `LinkedList`는 연결 리스트를 사용한다.
파이썬은 `collections` 모듈의 `collections.deque` 객체를 통해 덱을 지원한다.
PHP는 SPL 확장의 `SplDoublyLinkedList` 클래스를 통해 덱 자료 구조를 구현할 수 있다.
하스켈은 `Data.Sequence` 모듈에서 덱 구조를 구현한다.
Rust는 `std::collections::VecDeque`를 통해 덱을 지원한다.
7. 복잡도
- 이중 연결 리스트로 구현할 경우, 할당/해제 오버헤드가 없다고 가정하면 모든 덱 연산의 시간 복잡도는 O(1)이다. 반복자가 주어졌을 때 중간 삽입 또는 삭제의 시간 복잡도 역시 O(1)이다. 그러나 인덱스를 통한 임의 접근의 시간 복잡도는 O(n)이다.
- 확장 배열로 구현할 경우, 모든 덱 연산의 상각 시간 복잡도는 O(1)이다. 인덱스를 통한 임의 접근의 시간 복잡도 역시 O(1)이다. 그러나 중간 삽입 또는 삭제의 시간 복잡도는 O(n)이다.
8. 응용
덱은 브라우징 기록을 저장하는 데 사용할 수 있다. 새로운 웹사이트는 덱의 끝에 추가되고, 기록이 너무 커지면 가장 오래된 항목이 삭제된다. 사용자가 지난 한 시간 동안의 브라우징 기록을 지우도록 요청하면 가장 최근에 추가된 항목이 제거된다.
덱을 사용할 수 있는 또 다른 예는 작업 훔치기 알고리즘이다.[9] 이 알고리즘은 여러 프로세서에 대한 작업 스케줄링을 구현한다. 각 프로세서마다 실행할 스레드가 있는 별도의 덱이 유지된다. 다음 스레드를 실행하기 위해 프로세서는 덱에서 첫 번째 요소를 가져온다("첫 번째 요소 제거" 덱 연산 사용). 현재 스레드가 분기되면 덱의 맨 앞으로 다시 넣고("앞쪽에 요소 삽입") 새 스레드가 실행된다. 프로세서 중 하나가 자체 스레드 실행을 마치면(즉, 덱이 비어 있으면) 다른 프로세서에서 스레드를 "훔칠" 수 있다. 다른 프로세서의 덱에서 마지막 요소를 가져와("마지막 요소 제거") 실행한다. 작업 훔치기 알고리즘은 인텔의 Threading Building Blocks(TBB) 라이브러리에서 사용된다.
참조
[1]
서적
"C++ in One Hour a Day, Sams Teach Yourself"
Sams Publishing
[2]
서적
The Art of Computer Programming
Addison-Wesley
[3]
학위논문
Purely Functional Data Structures
https://www.cs.cmu.e[...]
Carnegie Mellon University
1996-09
[4]
논문
Confluently persistent deques via data structural bootstrapping
1995-05
[5]
논문
Purely functional representations of catenable sorted lists
1996-05
[6]
간행물
Catenable double-ended queues
https://dl.acm.org/d[...]
1997-08
[7]
간행물
Simple Confluently Persistent Catenable Lists
https://epubs.siam.o[...]
2000
[8]
간행물
Notes on Catenable Deques in Pure Lisp
https://www.cs.princ[...]
Princetown University
2003-08
[9]
학술지
Scheduling multithreaded computations by work stealing
http://supertech.csa[...]
[10]
서적
The Art of Computer Programming
Addison-Wesley
[11]
서적
Effective STL STLを効果的に使いこなす50の鉄則
ピアソン・エデュケーション
[12]
서적
Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006
Springer
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com