[Algorithm] Deque

치현·2024년 7월 15일

Deque stl 덱 자료구조

Algorithm

목록 보기

1/1

정의

Deque(Double Ended Queue)는 양 쪽에서 삽입/삭제가 가능한 자료구조이다.

성질

원소의 추가 - O(1)
원소의 제거 - O(1)
제일 앞/뒤의 원소 확인 - O(1)
제일 앞/뒤가 아닌 원소는 원칙적으로 확인/변경이 불가능하다.
** STL Deque는 독특하게 인덱스로 중간 원소의 접근이 가능하다.

STL 사용

deque dq : 비어있는 덱 생성
deque dq(2) : Default 값(0) 2개를 지닌 덱 생성
deque dq(2, 1) : 1의 값 2개를 지닌 덱 생성
deque dq(copyDq) : 덱 copyDq를 복사한 dq 생성
dq.assign(2, 1) : 1의 값으로 2개의 원소 할당

dq.at(index) : index에 해당하는 요소 접근
-> 이 경우 dq[index]와 같이 접근하는게 유효 범위를 검사하지 않기 때문에 더 빠르다.
dq.front() : 첫 번째 원소 참조
dq.back() : 마지막 원소 참조
dq.clear() : 모든 원소 제거
dq.push_front(value) : value를 첫 번째에 삽입

dq.pop_front() : 첫 번째 원소 삭제
dq.push_back(value) : value를 마지막에 삽입
dq.pop_back() : 마지막 원소 제거
dq.begin() : 첫 번째 원소의 iterator 반환
dq.end() : 마지막 원소의 다음 iterator 반환

dq.rbegin() : 마지막 원소를 첫 번째 원소로써 iterator 반환
dq.rend() : 첫 번째 원소의 이전 iterator를 반환
dq.resize(n) : 크기를 n으로 변경, 비어있는 공간은 0으로 초기화
dq.size() : 크기를 반환
dq.swap(targetDq) : dq와 targetDq를 바꿔줌

dq.insert(position, count, value) : position에 value 값을 count개 삽입
삽입한 곳의 iterator 반환
dq.erase(iterator) : iterator가 가리키는 곳을 삭제
삭제된 원소 다음의 iterator 반환
dq.empty() : 덱이 비어있다면, true 반환

구현

구현은 가장 쉬운 배열로 한다.
덱은 양 쪽으로 삽입이 가능하기 때문에 배열의 중간부터 시작해 양 쪽으로 뻗어나가는 형식이 되어야 한다.

따라서, N번 삽입할 때 최악의 경우 앞으로 N번 또는 뒤로 N번이 가능하기 때문에 배열의 크기는 2 * N + 1이 되어야 한다.

추가로 구현할 때 원형 큐, 오버플로우 방지를 위한 인덱스 검사 등을 수행하면 좋겠지만, 간단한 구현을 위해 오버플로우가 되는 상황이 아예 없다는 것을 가정한다. (N을 삽입 횟수로 잡음)

초기 값

head는 가장 앞의 원소를 가리키고, tail은 가장 뒤의 원소의 다음을 가리킨다.
즉, 다음과 같이 포인팅을 하고 있다.

중간부터 양 쪽으로 삽입/삭제가 일어나야하기 때문에 head와 tail의 초기 값은 배열의 중간에 위치한다.

앞 쪽 삽입

head의 값을 하나 감소시키고 그 위치에 값을 넣는다.

앞 쪽 삭제

head의 값을 하나 증가시킨다.
삽입 시에 값이 들어있든 들어있지 않든 새로운 값을 삽입하기 때문에, 가장 앞에 있는 원소를 삭제하지 않고 head 포인터만 증가시킨다.

앞 쪽 확인

head 위치에 해당하는 값을 반환한다.

뒤 쪽 삽입

tail 위치에 삽입한 후, 값을 하나 증가시킨다.

뒤 쪽 삭제

tail의 값을 하나 감소시킨다.

뒤 쪽 확인

tail의 값은 가장 뒤 쪽 원소 인덱스의 다음을 가리키고 있기 때문에 그 전 값을 반환한다.

전체 코드

Deque vs Vector

STL의 Deque는 맨 앞/뒤가 아니더라도 인덱스를 이용해 각 원소에 접근이 가능하다. 또한, 인터페이스도 vector와 대부분 유사하다.
둘 사이에 어떤 차이가 있고 어느 상황에서 어떤 것을 사용해야할까?

차이점

메모리
vector는 메모리가 연속적이다. (Cache Hit Rate가 높다.)
deque는 메모리가 불연속적이다. (메모리 관리가 효율적이다.)
연산 속도
vector는 중간에 원소를 삽입하거나 삭제하는 작업이 오래걸린다. (O(N), 배열 기반이기 때문)
deque는 중간에 원소를 삽입하거나 삭제하는 작업이 오래걸리지 않는다. (O(1), 메모리 상 쪼개어 관리되기 때문)