개념
Rear와 Front 모두에서 데이터를 넣고 뺄 수 있는 자료구조다. 스택과 큐의 장점을 모두 갖고 있다.
특징
멤버
덱도 큐와 마찬가지로 배열이라 연결리스트를 이용해서 구현할 수 있다. 메모리적인 측면에서 봤을 때 원형큐처럼 배열을 활용해서 구현하는 것이 좋다.
두개의 포인터로 원소들을 관리한다.
- front
- rear
front는 덱의 앞을 가리키고 순서상 가장 앞의 원소의 인덱스보다 -1 값을 가진다.
rear는 덱의 뒤를 가리키고 순서상 가장 마지막 원소의 인덱스와 같다.
연산
덱은 스택과 큐의 장점을 붙인 자료구조다. 덱의 연산은 다음과 같다.
- pushFront()
- pushBack()
- popFront()
- popBack()
원소들이 어느 방향으로 들어오냐에 따라 포인터의 움직임이 다르다.
pushFront()의 경우 덱의 front를 통해 원소가 들어오게 된다. 원소가 들어올 경우 front의 위치에 원소를 넣고 front의 값을 -1만큼 내려서 갱신한다.
pushBack()의 경우 덱의 rear를 통해 원소가 들어오게 된다. 원소가 들어올 경우 rear의 위치에 원소를 넣고 rear의 값을 +1만큼 올려서 갱신한다.
덱을 원형큐를 활용해서 구현했기 때문에 배열의 인덱스보다 작거나 클 수 있다. 따라서 나머지 연산을 통해 front와 rear를 갱신한다.
rear = (rear + 1) % capacity;
front = (front - 1) % capacity;