덱 (Deque, Double-Ended queue)

개념

덱은 양쪽 끝(앞과 뒤) 모두에서 데이터의 삽입과 삭제가 가능한 선형 자료구조이다. 배열과 연결 리스트가 섞여 있는 형태로, 각각의 장점과 단점을 어느 정도 공유하고 있다.

특징

• 양방향 삽입/삭제 양쪽 끝(앞과 뒤)에서 삽입과 삭제가 모두 가능하다.
• 유연한 동작 방식 FIFO(큐), LIFO(스택) 방식 모두를 지원할 수 있어 다양한 상황에서 활용이 가능하다.
• 동적 크기 크기가 가변적이며 필요에 따라 자동으로 확장/축소되므로, 데이터의 개수가 동적으로 변하는 상황에 적합하다.
• 구현 방식 주로 배열이나 이중 연결 리스트로 구현된다.

장점

• 양쪽 끝에서의 빠른 연산 앞과 뒤 모두에서 O(1)로 삽입과 삭제가 가능하여, 큐와 스택의 단점을 보완할 수 있다.
• 인덱스 접근 가능 (배열 기반) 배열 기반 덱은 인덱스를 통해 임의 접근이 가능하다.

단점

• 중간 삽입/삭제의 비효율성 양 끝이 아닌 중간에서의 삽입과 삭제는 O(n)의 시간 복잡도를 가지므로 비효율적이다.
• 메모리 오버헤드 구현 방식에 따라, 특히 연결 리스트 기반 덱은 포인터를 사용하므로 메모리 사용량이 늘어날 수 있다.
• 구현 복잡성 스택과 큐에 비해 구현이 더 복잡하며 여러 예외 처리가 필요하다.
• 최소 메모리 공간 데이터가 적더라도 구조상 꼭 필요한 메모리 공간이 클 수 있다.

std::deque