Deque

Concept

Deque(Double-Ended Queue)는 큐의 확장된 형태로, 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조입니다. 일반적인 큐가 FIFO(First-In-First-Out) 방식으로 동작하는 것과 달리, Deque는 양방향으로 데이터를 추가하거나 제거할 수 있습니다.

Logic

삽입과 삭제

위 그림과 같이, Deque 는,
앞쪽(front)이나,뒤쪽(rear)에 데이터 삽입 삭제가 모두 가능하여,(Front or Rear 에 위치한) 기존 데이터를 앞이나 뒤로 밀어내고 새로운 데이터를 넣거나, 마찬가지로 데이터를 제거하는 경우에는, 나머지 데이터들은 앞이나 뒤로 이동하게 됩니다.

Circular Buffer (원형 버퍼) 그리고 Rotate(회전)

Deque는 메모리 효율적인 구현을 위해 원형 버퍼(Circular Buffer)를 사용하여 구현될 수 있습니다. 이런 경우에는 논리적으로 삽입과 삭제를 사용하여 Rotate(회전) 동작을 사용할 수 있습니다. 현재 그림을 Deque 배열로 표현하면 [1,2,3,4] 으로 되어 있습니다. 이 구조에서 음의 방향으로 1만큼 회전하게 되면,

이와 같은 그림처럼, [2,3,4,1] Deque 배열을 가지는 연산도 진행할 수 있습니다.