[자료구조] std::deque

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

std::deque

개요

　앞서 살펴본 자료구조들은 연속된 자료구조 거나, 연결된 자료구조였다. 하지만 std::deque(Double-ended queue)는 두 가지 방식이 섞여있는 형태며, 양방향 삽입/삭제가 모두 가능한 자료구조다. 따라서 deque는 배열과 리스트의 장점을 모두 가지고 있어, 둘의 단점을 보완할 수 있는 자료구조다. 여기서 queue는 추후에 다룰 자료구조이니, 이런 것이 있구나 정도만 짚고 넘어가자.

---

구조

　앞서 <개요> 부분에서 deque의 구조가 조금 특이하다는 것을 알았다. 이를 가시적으로 확인하기 위해 다음 그림을 보자.

 

 

　위 그림은 deqeue의 전체 덱 자료구조를 나타내고 있다. Chunk는 여러 개의 메모리 청크 중 하나를 나타낸다. 각각의 청크는 연속된 메모리 블록으로 구성되어 있으며, 첫 번째 청크부터 마지막 청크까지 연결되어 이중 연결 리스트를 형성한다. 이렇게 함으로써, 덱은 큰 데이터를 블록으로 나누어 관리할 수 있으며, 블록 단위로 메모리를 할당하므로 메모리 관리가 효율적이다. 또한 덱의 양쪽 끝에 원소를 추가하거나 제거할 때, 첫 번째나 마지막 청크에도 추가/제거가 가능하므로 덱을 구현하는 데 있어서 유용하다. 만약 청크의 개념이 잘 이해되지 않는다면, [자료구조] 메모리 청크 게시글을 간략하게 읽고 오자.

 

　C++ 표준에 나와있는 deque 관련된 글을 읽어보면, cppreference 사이트만 가도 알 수 있듯이 어떤 기능에 대한 동작만 정의할 뿐, 어떻게 구현해야 하는지 정의하지 않는다.

 

출처: https://en.cppreference.com/w/cpp/container/deque

 

　따라서 deque를 구현하고자 한다면, 덱의 동작에 있어 다음 조건을 만족하게 해야 한다.

• 양쪽 끝에서의 삽입과 삭제가 가능해야 한다 ( O(1) )
• 임의 접근 반복자를 제공해야 한다 ( O(1) )
• 블록(block)으로 이루어진 메모리 구조를 사용해야 한다
• 멤버 함수는 예외 안전성을 보장해야 한다

---

특징

　위의 구조에 대한 글을 읽었다면, 덱의 전반적인 그림이 그려질 것이다. 앞선 요구 사항을 보면, 양쪽 끝의 포인터만 조작하면 삽입과 삭제가 이루어지므로 속도가 빠를 것이고(연결된 자료구조의 장점), 메모리 구조가 블록이기 때문에 임의 접근이 가능할 것이다(연속된 자료구조의 장점). 또한 원소 삽입/삭제 시 n/2 단계로 동작하는데, 이 연산이 모든 원소를 이동시키는 동작을 수행해야 한다는 것을 의미한다. 

#include <iostream>
#include <deque>

int main()
{
	std::deque<int> dq;

	for (int i = 5; i <= 10; i++)
		dq.push_back(i); // 5 6 7 8 9 10

	for (int i = 4; i >= 1; i--)
		dq.push_front(i); // 1 2 3 4 5 6 7 8 9 10

	dq.pop_back(); // 1 2 3 4 5 6 7 8 9
	dq.pop_front(); // 2 3 4 5 6 7 8 9
}

 

 

---

요약

std::deque
1. 정의: 양방향 큐 자료구조.
2. 특징
　a. 포인터를 이용해 역방향/순방향 이동 가능
　b. 임의 접근 가능
　c. 메모리 블록을 사용