3. 덱(deque)

deque의 자료구조

---

deque의 자료구조는 이름과 같이 Deque(Dooble Ended Queue)자료구조다. 덱 자료구조는 큐(Queue)자료구조와 비슷하므로, 먼저 큐 자료구조를 설명한다. 큐는 선형 리스트로 선입선출(FIFO) 방식을 사용한다. 다음 그림처럼 시작과 끝을 가리키느 ㄴ포인터로 삽입과 삭제를 한다.

 

큐는 앞으로는 삭제, 뒤로는 삽입을 할 때 사용한다. 덱이 큐와 다른 점은 삽입과 삭제를 한쪽이 아닌 앞, 뒤 양쪽에서 할 수 있다는 것이다.

 

 

 

 

 

 

Deque의 특징

---

1. 크기가 가변적이다.

2. 앞과 뒤에서 사입과 삭제가 좋다.

3. 중간에 데이터 삽입, 삭제가 용이하지 않다.

- 데이터를 중간에 삽입하거나 삭제하는 것은 피해야한다. 사입과 삭제를 중간에 한다면 삽입하거나 삭제한 위치 앞뒤 데이터를 모두 이동해야 하낟.

4. 구현이 쉽지 않다.

- 덱은 스텍과 큐가 결합된 자료구조로 연결 리스트보다 구현하기가 더 어렵다.

5. 랜덤 접근이 가능하다.

- 연결리스트 처럼 리스트를 탐색하지 않고 원하는 요소에 바로 접근할 수 있다.

 

 

 

 

Deque을 사용하는 경우

---

1. 앞과 뒤에서 삽입, 삭제를 한다.

- 대부분 작업이 데이터를 앞이나 뒤에 삽입, 삭제를 한다면 STL 컨테이너 라이브러리 중에서 deque을 사용할떄 성능이 가장 좋다.

2. 저장할 데이터 개수가 가변적이다.

3. 검색을 거의 하지 않는다.

- 많은 데이터를 저장한다면 앞에서 여러 번 언급했듯이 map, set, hash_map중 하나를 선택해서 사용하는 편이 좋다.

4. 데이터 접근을 랜덤하게 하고 싶다.

- vector와 같이 랜덤 접근이 가능하다. 사용하는 방법도 같다.

 

 

 

 

 

deque VS. vector

---

deque은 전체적으로 멤버 함수의 기능이나 사용방법이 vector와 거의 같다. vector는 삽입과 삭제를 뒤에서만 해야 성능이 좋지만, deque은 삽입과 삭제를 앞과 뒤에서 해도 좋으며 앞뒤 삽입, 삭제 성능도 vector보다 좋다. 하지만, deque은 앞뒤에서 삽입, 삭제하는 것을 제외한 다른 위치에서의 삽입과 삭제는 vector보다 성능이 좋지 않다.

 

 

 

 

deque 사용방법

---

deque을 사용하려면 deque 헤더파일을 포함한다.

#include <deque>

 

deque 형식은 아래와 같다.

deque<자료형> 변수이름

예) deque<int> deque1;

 

deque도 동적 할당을 할 수 있다.

deque<int>* deque1 = new deque<int>;

 

 

 

1. deque의 주요 멤버들

---

 

 

 

 

2. 기본 사용 멤버

---

 

 

 

 

 

가. 추가

---

앞과 뒤에서 추가를 할 수 있다. 보통 덱을 사용할 때는 뒤에 추가를하고 앞에서는 삭제를 한다.

 

앞쪽 추가는 push_front()를 사용

deque<int> deque1;

deque1.push_front(100);

 

뒤쪽 추가는 push_back()을 사용

deque<int> deque1;

deque1.push_back(200);

 

 

나. 삭제

---

앞과 뒤에서 삭제 할 수 있다.

 

앞에서 삭제는 pop_front()를 사용

deque1.pop_front();

 

뒤에서 삭제는 pop_back()를 사용

deque1.pop_back();

 

 

다. 접근

---

 

라. 모두 삭제

---

clear()를 사용하면 저장한 모든 데이터를 삭제한다.

deque1.clear();

 

 

마. 데이터 저장 여부

---

저장한 데이터가 있는지 없는지 empty()로 조사한다. 있으면 false, 없으면 true를 리턴한다.

bool bEmpty = deque1.empty();

 

 

바. 저장된 원소 개수 조사

---

size()로 덱에 저장된 데이터 개수를 조사한다.

deque<int>::size_type TotalCount = deque1.size();

 

 

사. 가장 자주 사용하는 멤버들을 사용하는 예제 코드

---

 

 

아. insert 멤버

---

 

자. erase 멤버

---

 

 

 

차. assign

---

지정 데이터를 지정 개수만큼 채웁니다. 숫자 7를 7개 채운다.

deque1.assign(7, 7);

 

다른 deque의 반복자로 지정한 영역으로 채운다.

deque1.assign( deque2.begin(), deque2.end() );

 

 

카. swap

---

deque1과 deque2가 있을 때 두 deque에 저장한 데이터를 서로 맞바꿀 때 사용한다.

 

다음은 deque1과 deque2를 swap하는 방법을 두 가지로 나타낸 코드다.

deque1.swqp( deque2 );

swqp( deque1, deque2 );

 

 

출처 : Thinking About C++ STL 프로그래밍 (최홍배 지음)