Algorithm Guidecomplexity: O(1) 양끝 삽입/삭제

덱 (Deque)

양쪽 끝에서 모두 삽입·삭제가 가능한 이중 종단 큐입니다. 스택과 큐를 모두 흉내낼 수 있어 슬라이딩 윈도우·회문 검사·양방향 탐색에 활용됩니다.

01덱 (Deque)

알고리즘 작동 원리 탐색

덱(Deque) 시작. 양쪽 끝 모두에서 넣고 뺄 수 있는 이중 종단 큐입니다.

append(10) · 뒤쪽 끝에 10을 추가합니다.

appendleft(5) · 이번엔 앞쪽 끝에 5를 추가합니다.

append(20) · 다시 뒤쪽 끝에 20을 추가합니다.

popleft() · 앞쪽 끝의 5를 꺼낼 대상으로 표시합니다.

앞쪽 5가 빠졌습니다. 남은 것은 10 · 20.

pop() · 이번엔 뒤쪽 끝의 20을 꺼낼 대상으로 표시합니다.

뒤쪽 20이 빠졌습니다. 양끝 모두에서 자유롭게 넣고 빼는 것이 덱의 특징입니다.

empty

Live Python

1from collections import deque

3dq = deque()

4dq.append(x) # 뒤에 추가

5dq.appendleft(x) # 앞에 추가

6dq.pop() # 뒤에서 제거

7dq.popleft() # 앞에서 제거

8dq[0], dq[-1] # 양끝 조회

1 / 8

02 쉽게 이해하기

For Everyone

🔑핵심 동작

양쪽 끝에서 모두 넣고 뺄 수 있어, 스택으로도 큐로도 쓸 수 있습니다.

💡쉽게 말하면

큐와 스택을 합친 형태로, 양쪽 끝 모두에서 넣고 뺄 수 있어 더 유연합니다.

📍어디에 쓰나

–최근 사용 목록(오래된 건 앞에서 버리고 새 건 뒤에 추가)
–회문 검사
–슬라이딩 윈도우

03 파이썬 구현 코드

덱 (Deque)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

from collections import deque

dq = deque()
dq.append(x)        # 뒤에 추가
dq.appendleft(x)    # 앞에 추가
dq.pop()            # 뒤에서 제거
dq.popleft()        # 앞에서 제거
dq[0], dq[-1]       # 양끝 조회

04 자주 묻는 질문

FAQ

덱 (Deque)란 무엇인가요?+

양쪽 끝에서 모두 삽입·삭제가 가능한 이중 종단 큐입니다. 스택과 큐를 모두 흉내낼 수 있어 슬라이딩 윈도우·회문 검사·양방향 탐색에 활용됩니다.

덱 (Deque)의 시간복잡도는 어떻게 되나요?+

덱 (Deque)의 시간복잡도는 O(1) 양끝 삽입/삭제 입니다. 시각화의 단계별 진행을 따라가며 왜 이런 복잡도가 나오는지 직접 확인할 수 있습니다.

덱 (Deque)은(는) 어디에 사용하나요?+

최근 사용 목록(오래된 건 앞에서 버리고 새 건 뒤에 추가), 회문 검사, 슬라이딩 윈도우.

덱 (Deque)를 쉽게 비유하면?+

양쪽 끝에서 모두 넣고 뺄 수 있어, 스택으로도 큐로도 쓸 수 있습니다.

📦연결 리스트 (Linked List)