덱 (Deque, Double-Ended Queue)

덱 (Deque, Double-Ended Queue)

양쪽 끝(front와 rear)에서 삽입과 삭제가 모두 가능한 선형 자료구조로, 스택과 큐의 기능을 모두 제공하는 유연한 자료구조

목적: 양방향 삽입·삭제, 스택+큐 통합, 슬라이딩 윈도우, 유연한 순서 관리

특징: 양방향 연산, 스택+큐 일반화, 동적 크기, 양쪽 O(1) 연산

연산

• •addFirst(item)/pushFront(): front에 삽입, O(1)
• •addLast(item)/pushBack(): rear에 삽입, O(1)
• •removeFirst()/popFront(): front 제거, O(1)
• •removeLast()/popBack(): rear 제거, O(1)
• •peekFirst(), peekLast(): 조회, O(1)

구현: 이중 연결 리스트 또는 원형 배열(동적 배열)

시간 복잡도: 양쪽 삽입·삭제 모두 O(1)

공간 복잡도: O(n)

장점: 유연성(스택+큐), 양방향 O(1) 연산, 다양한 응용

단점: 중간 접근 비효율, 일반 큐보다 복잡, 추가 메모리(이중연결)

적용사례

• •슬라이딩 윈도우 최대/최소
• •LRU 캐시
• •팰린드롬 검사
• •작업 스케줄러(양방향)
• •Undo/Redo
• •브라우저 히스토리

비교: 덱(양방향/유연) vs 큐(FIFO/한방향) vs 스택(LIFO/한쪽)

연관: 큐, 스택, 이중 연결 리스트, 슬라이딩 윈도우