덱 (Deque)
쉽게 풀면
양쪽에 문이 달린 복도를 상상해봅시다. 한쪽 문으로만 들어가고 나가야 하는 큐(줄서기)나, 한쪽에서만 넣고 빼야 하는 스택(접시 쌓기)과 달리, 덱(Deque, Double-Ended Queue)은 앞문과 뒷문 어디로든 자유롭게 물건을 넣거나 뺄 수 있습니다. 그래서 덱 하나로 스택처럼 쓸 수도 있고 큐처럼 쓸 수도 있으며, 양 끝을 동시에 활용해야 하는 문제에서 특히 유용합니다.
왜 중요한가
덱은 스택과 큐의 기능을 하나로 통합한 자료구조이기 때문에, 알고리즘 설계 논문에서 양 끝을 모두 활용해야 하는 문제의 효율성을 크게 개선하는 도구로 자주 등장합니다. 슬라이딩 윈도우 최적화, 작업 스케줄링, 캐시 교체 정책(예: 최근 사용 빈도를 관리하는 구조) 등 실무적인 시스템 설계에서도 기반 자료구조로 활용되어, 자료구조 및 알고리즘 효율성을 다루는 연구에서 폭넓게 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 "창(윈도우)이 한 칸씩 움직일 때마다 필요 없어진 값은 앞에서 빼고 새 값은 뒤에서 비교해 넣는 방식으로, 덱의 양쪽 끝 연산을 활용해 계산을 빠르게 만들었다"는 뜻입니다.
병렬 컴퓨팅 연구에서는 여러 스레드가 서로 다른 끝에서 작업을 넣고 빼는 방식으로 자료구조를 공유하면, 스레드 간 충돌을 줄이면서도 유휴 스레드가 남은 작업을 효율적으로 나눠 가질 수 있다는 뜻입니다.
운영체제·캐시 설계 연구에서는 자주 쓰는 데이터를 앞쪽에 두고 오랫동안 안 쓰인 데이터를 뒤쪽에서 밀어내는 방식으로, 덱의 양 끝 연산이 캐시 관리 정책을 구현하는 데 쓰인다는 뜻입니다.
조금 더 깊게 보면
덱은 배열 기반 원형 버퍼(circular buffer)로 구현하면 앞뒤 삽입·삭제를 평균적으로 상수 시간(O(1))에 처리할 수 있고, 이중 연결 리스트로 구현하면 메모리 재할당 없이도 유연하게 확장할 수 있습니다. 다만 배열 기반 구현은 중간 위치에서 특정 인덱스에 접근할 때 빠른 반면 크기 조정 시 재할당 비용이 들 수 있고, 연결 리스트 기반 구현은 임의 위치 접근이 느린 대신 삽입·삭제가 유연하다는 특성이 있습니다. 논문에서 덱을 활용한 알고리즘을 볼 때는 어떤 내부 구현을 전제로 시간복잡도를 계산했는지 확인하는 것이 중요합니다.
주의할 점
덱은 스택과 큐의 기능을 모두 포함하는 일반화된 자료구조이지만, 실제 구현 방식(배열 기반 원형 버퍼인지, 연결 리스트 기반인지)에 따라 특정 위치 접근이나 메모리 재할당 비용이 달라질 수 있으므로, 사용하는 언어나 라이브러리의 덱 구현 방식을 확인하고 쓰는 것이 좋습니다.