정의
덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 스택과 큐의 특성을 모두 가지고 있어 유연하게 사용할 수 있습니다.
핵심 특성
- ✓양쪽 끝에서 O(1) 시간에 삽입/삭제 가능
- ✓스택처럼 사용 가능 (한쪽만 사용)
- ✓큐처럼 사용 가능 (양쪽 다른 연산)
- ✓슬라이딩 윈도우 알고리즘에 자주 활용
활용 사례
이런 상황에서 사용됩니다:
🪟
슬라이딩 윈도우 최대/최소
윈도우 내 최대/최소값을 O(n)에 구할 때 덱을 활용합니다. 양쪽에서 제거가 가능하기 때문입니다.
🔄
회문(Palindrome) 검사
양쪽에서 문자를 꺼내 비교하며 회문인지 효율적으로 검사할 수 있습니다.
📋
작업 스케줄링
우선순위가 높은 작업을 앞에, 낮은 작업을 뒤에 추가하여 유연하게 관리합니다.
🌐
브라우저 히스토리
방문 기록을 양쪽에서 관리하여 앞으로/뒤로 가기 기능을 구현합니다.
주요 연산
주요 연산들:
pushFront
O(1)덱의 앞쪽에 요소를 삽입합니다.
pushBack
O(1)덱의 뒤쪽에 요소를 삽입합니다.
popFront
O(1)덱의 앞쪽에서 요소를 제거하고 반환합니다.
popBack
O(1)덱의 뒤쪽에서 요소를 제거하고 반환합니다.
peekFront / peekBack
O(1)앞/뒤 요소를 제거하지 않고 확인합니다.
복잡도
시간 복잡도
최선
O(1)
평균
O(1)
최악
O(1)
공간 복잡도
O(n)
시각화로 더 깊이 이해하기
단계별 애니메이션과 코드 실행을 통해 알고리즘이 어떻게 동작하는지 직접 확인하세요.
시각화 시작하기