챕터2-3. 자료구조 | 덱(Deque)

덱의 개념

# 덱이란

- Deque, Double-ended queue의 약자이다.

- 양 끝에서만 자료를 넣고 양 끝에서 뺄 수 있는 자료구조

- 큐는 push, pop을 할 수 있는 위치가 한 방향으로 고정되어 있지만, 덱은 앞에서도 push, pop, 뒤에서도 push, pop이 모두 가능하다.

- 중요한 자료구조는 맞지만, 덱의 특징을 이용해서 문제를 푸는 경우는 많지 않음.

 

# 직접 구현하기 위해 필요한 요소

- 앞, 뒤에서 삭제 추가 연산이 일어나기 때문에 보통 이중 연결리스트로 구현한다고 함

 

# 덱의 연산

- push_front() : 덱의 앞에 자료를 넣는 연산

- pop_front() : 덱의 앞에서 자료를 빼는 연산

- push_back() : 덱의 뒤에 자료를 넣는 연산 

- pop_back() : 덱의 뒤에서 자료를 빼는 연산

- front() : 덱의 가장 앞에 있는 자료를 보는 연산

- back() : 덱의 가장 뒤에 있는 자료를 보는 연산

덱을 적용한 문제풀이

# 덱을 구현하는 문제

- https://www.acmicpc.net/problem/10866