Deque : 양방향 큐의 모든 것

Python의 collections.deque는 양방향 큐(Double-Ended Queue)를 구현한 자료구조입니다. 이 글에서는 deque의 기본 개념부터 실무에서의 활용까지, Python 개발자라면 알아야 할 모든 것을 설명합니다.

---

1. Deque란 무엇인가?

Deque는 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 일반적인 리스트와 달리, 양쪽 끝에서의 연산이 O(1) 시간 복잡도를 가지는 것이 특징입니다.

Deque의 주요 특징

• 양쪽 끝에서의 삽입/삭제가 O(1) 시간 복잡도
• 스레드 안전한 구현
• 크기 제한 설정 가능
• 메모리 효율적인 구현

---

2. Deque의 기본 연산

1. 생성과 기본 연산

from collections import deque

# 기본 생성
d = deque()
print(d)  # deque([])

# 초기 요소와 함께 생성
d = deque([1, 2, 3])
print(d)  # deque([1, 2, 3])

# 최대 크기 설정
d = deque(maxlen=3)
d.extend([1, 2, 3])
d.append(4)
print(d)  # deque([2, 3, 4], maxlen=3)

2. 양쪽 끝 연산

d = deque()

# 오른쪽 끝 연산
d.append(1)      # deque([1])
d.append(2)      # deque([1, 2])
right = d.pop()  # 2, deque([1])

# 왼쪽 끝 연산
d.appendleft(0)  # deque([0, 1])
left = d.popleft()  # 0, deque([1])

3. 확장 연산

d = deque([1, 2, 3])

# 오른쪽 확장
d.extend([4, 5])      # deque([1, 2, 3, 4, 5])

# 왼쪽 확장 (순서가 반대로 들어감)
d.extendleft([0, -1])  # deque([-1, 0, 1, 2, 3, 4, 5])

4. 회전 연산

d = deque([1, 2, 3, 4, 5])

# 오른쪽으로 2칸 회전
d.rotate(2)    # deque([4, 5, 1, 2, 3])

# 왼쪽으로 1칸 회전
d.rotate(-1)   # deque([5, 1, 2, 3, 4])

---

3. Deque의 활용 사례

1. 슬라이딩 윈도우

def sliding_window(nums, k):
    d = deque()
    result = []

    for i, num in enumerate(nums):
        # 윈도우 크기 유지
        while d and d[0] <= i - k:
            d.popleft()

        # 현재 요소보다 작은 요소 제거
        while d and nums[d[-1]] < num:
            d.pop()

        d.append(i)

        if i >= k - 1:
            result.append(nums[d[0]])

    return result

# 사용 예시
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(sliding_window(nums, k))  # [3, 3, 5, 5, 6, 7]

2. 회문 검사

def is_palindrome(s):
    d = deque(s.lower().replace(" ", ""))
    while len(d) > 1:
        if d.popleft() != d.pop():
            return False
    return True

# 사용 예시
print(is_palindrome("A man a plan a canal Panama"))  # True
print(is_palindrome("Hello"))  # False

3. 작업 큐 관리

class TaskQueue:
    def __init__(self):
        self.tasks = deque()

    def add_task(self, task, priority='normal'):
        if priority == 'high':
            self.tasks.appendleft(task)
        else:
            self.tasks.append(task)

    def process_task(self):
        if self.tasks:
            return self.tasks.popleft()
        return None

# 사용 예시
queue = TaskQueue()
queue.add_task("일반 작업")
queue.add_task("긴급 작업", priority='high')
print(queue.process_task())  # "긴급 작업"

---

4. Deque vs 리스트: 언제 무엇을 사용해야 할까?

Deque를 사용해야 할 때

1. 양쪽 끝에서의 삽입/삭제가 빈번한 경우
2. 스레드 안전성이 필요한 경우
3. 크기가 제한된 큐가 필요한 경우
4. 회전 연산이 필요한 경우

리스트를 사용해야 할 때

1. 중간 요소에의 접근이 빈번한 경우
2. 슬라이싱이 필요한 경우
3. 정렬이 필요한 경우

---

5. 실무에서의 활용 팁

1. 성능 최적화

   • 양쪽 끝 연산이 필요한 경우 반드시 deque 사용
   • 중간 삽입/삭제가 필요한 경우 리스트 고려

2. 메모리 관리

   • maxlen 파라미터를 사용하여 메모리 사용량 제한
   • 불필요한 요소는 즉시 제거

3. 스레드 안전성

   • 멀티스레드 환경에서 안전하게 사용 가능
   • 단, 원자적 연산이 필요한 경우 추가적인 동기화 필요

---

6. 결론

Python의 collections.deque는 양방향 큐를 구현한 강력한 자료구조입니다. 특히 양쪽 끝에서의 연산이 필요한 경우 리스트보다 훨씬 효율적이며, 스레드 안전성까지 제공합니다. 실무에서는 상황에 맞게 적절히 활용하면 좋은 성능을 얻을 수 있습니다.

핵심 인사이트

• Deque는 양쪽 끝 연산이 O(1) 시간 복잡도를 가집니다.
• 스레드 안전한 구현을 제공합니다.
• 슬라이딩 윈도우, 회문 검사 등 다양한 문제에 활용할 수 있습니다.

---

참고 자료

• Python collections.deque 공식 문서
• Python Time Complexity 문서