#06. 덱(Deque)

덱(Deque)

• front와 end에서 삭제와 삽입이 모두 가능하다.
• 리스트의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 자료구조 (Double Ended Queue)
• 연속적인 메모리를 기반으로 하는 '시퀀스 컨테이너'이다. (임의 접근 반복자 제공)
• 여러 개의 메모리 단위로 데이터를 저장한다.
• 크기가 가변적이다. (선언 후에 변경 가능)
• 중간 요소가 삽입, 삭제될 때, 요소들을 앞/뒤로 밀수 있으므로 vector 보다는 좋은 성능을 가짐

 

• 스크롤(Scroll) : 입력 제한 덱 (입력이 한쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있음)
• 셸프(Shelf) : 출력 제한 덱 (입력은 양쪽에서 일어나고, 출력은 한쪽에서만 일어나도록 제한)

 

장점

• 데이터의 삽입과 삭제가 빠르다
• 크기가 가변적이다.
• 앞/뒤에서 데이터를 삽입/삭제할 수 있다.
• index로 임의 원소 접근이 가능하다.
• 새로운 원소 삽입 시에, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.

단점

• 덱(Deque)의 중간에서의 삽입과 삭제가 어렵다.
• 구현이 어렵다.

 

사용

• 앞과 뒤에서 삽입, 삭제가 자주 일어나는 경우
• 데이터의 개수가 가변적일 경우
• 데이터 검색을 거의 하지 않을 경우 (랜덤 요소에 접근해야 할 때)

---

대표적인 덱의 기능

• push_front : 덱의 앞에 자료를 넣는다.
• push_back : 덱의 뒤에 자료를 넣는다.
• pop_front : 덱의 앞에서 자료를 뺀다.
• pop_back : 덱의 뒤에서 자료를 뺀다.
• front : 덱의 가장 처음에 있는 자료를 본다.
• back : 덱의 가장 마지막에 있는 자료를 본다.

---

• size : 덱에 들어있는 정수의 개수를 출력한다.
• empty : 덱이 비어있으면 1을, 아니면 0을 출력한다.

---

References