최종 수정 : 24.12.29
덱(Deque)
덱(Deque : double-ended queue의 약어)은 큐의 특수한 형태로, 디큐, 데크, 덱이라는 이름으로 불린다. 덱은 리스트의 양쪽 끝에서 삽입과 삭제가 모두 이루어지는 자료구조 형태이다. 덱은 스택과 큐를 혼합한 구조로 하나의 배열을 선언한 후 2개의 포인터로 양쪽 끝을 가리킴으로써 양쪽에서 삽입 및 삭제 연산이 이루어지는 구조이다.
덱을 표현하는 방법에는 1차원 배열 형태인 스택을 이용하는 방법과 단순 연결 리스트나 이중 연결 리스트를 사용하여 표현하는 방법이 있다. 연결 구조를 위한 포인터 기억공간을 더 요구하게 되는 문제점을 갖는다. 덱은 리스트의 양쪽 끝에서 삽입과 삭제가 발생하여 항상 2개의 포인터가 필요하다.
덱은 양쪽 끝에서 원소들의 삽입과 삭제에 제한을 두어 리스트의 어느 한쪽 끝에서 삽입과 삭제만 가능하도록 할 수 있다.
- 입력 제한 덱
☞ 스크롤(Scroll)이라고도 하며, 삽입이 한쪽 끝에서만 일어날 수 있도록 제한하는 경우 - 출력 제한 덱
☞ 셀프(shelf)라고도 하며, 출력이 한쪽 끝에서만 일어날 수 있도록 제한하는 경우
스택울 이용하는 방법은 2개의 스택을 연결하여 사용하고, 2개의 스택은 경계를 두어 삽입 및 삭제 연산을 실행한다. 또한, 기억공간이 아직 남아 있는 상태인데도 불구하고, 기억공간 overflow가 발생하여 원소들의 이동이 필요할 때가 있다. 이러한 오버헤드를 줄이기 위해서 덱을 연결 리스트로 표현하기도 한다.
참고
독학사 교재
댓글