[Python] deque

이번 포스팅에서는 파이썬의 collections 모듈에서 제공하는 자료형 중 하나인 deque에 대하여 공부를 해보고자 한다.

 

---

deque란

deque는 "double-ended queue"의 약자로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.
파이썬의 collections 모듈에 포함되어 있으며, 리스트와 유사한 기능을 제공하지만 효율적인 작업을 위해 설계되었다.

 

deque 구조

 

deque는 다음과 같이 정의된다.

from collections import deque

# 빈 deque 생성
d = deque()

# 초기값을 가진 deque 생성
d = deque([1, 2, 3])

# 최대 길이를 가진 deque 생성
d = deque(maxlen=10)

 

deque는 다음과 같은 메서드를 포함하고 있다.

• append(item): deque의 오른쪽 끝에 item을 추가한다.
• appendleft(item): deque의 왼쪽 끝에 item을 추가한다.
• pop( ): deque의 오른쪽 끝에서 요소를 제거하고 반환한다.
• popleft( ): deque의 왼쪽 끝에서 요소를 제거하고 반환한다.
• clear( ): deque의 모든 요소를 제거한다.
• count(item): deque에서 item이 나타나는 횟수를 반환한다.
• extend(iterable): iterable의 모든 요소를 오른쪽 끝에 추가한다.
• extendleft(iterable): iterable의 모든 요소를 왼쪽 끝에 추가한다.
• remove(item): deque에서 첫 번째로 일치하는 item을 제거한다.
• reverse( ): deque의 요소들을 역순으로 뒤집는다.
• rotate(n): deque의 모든 요소들을 n만큼 회전시키며, 양수인 경우 오른쪽으로, 음수인 경우 왼쪽으로 회전한다.

deque는 리스트와 비슷한 인터페이스를 제공하면서 효율적인 작업을 가능하게 해주는 자료구조입니다. 큐, 스택, 버퍼 등 다양한 상황에서 유용하게 활용될 수 있습니다.

 

---

deque 특징

 

deque는 다음과 같은 특징을 가지고 있다.

1. 양쪽 끝에서의 삽입과 삭제

# 오른쪽 끝에 요소 추가
d.append(4)
# 결과: deque([1, 2, 3, 4])

# 왼쪽 끝에 요소 추가
d.appendleft(0)
# 결과: deque([0, 1, 2, 3, 4])

# 오른쪽 끝 요소 제거
x = d.pop()
# 결과: x = 4, deque([0, 1, 2, 3])

# 왼쪽 끝 요소 제거
x = d.popleft()
# 결과: x = 0, deque([1, 2, 3])

• deque는 양쪽 끝에서 아이템을 추가하거나 제거할 수 있다.
• 이는 리스트의 append와 pop 메서드와 유사하지만, deque는 왼쪽 끝에서의 추가와 삭제도 지원한다.
• 따라서 큐(Queue)나 스택(Stack)과 같은 다양한 상황에서 유용하게 사용될 수 있다.

 

2. O(1)의 시간 복잡도

• deque의 양쪽 끝에서의 삽입과 삭제는 평균적으로 상수 시간에 이루어진다.
• 이는 리스트의 첫 번째 요소를 삭제하거나 첫 번째에 요소를 추가하는 경우에도 상수 시간에 실행된다.
• 이러한 효율성은 deque가 큰 데이터 집합에서도 효율적으로 작동할 수 있도록 합니다.

 

3. 최대 길이 설정

d = deque(maxlen=3)
d.append(1)
d.append(2)
d.append(3)
d.append(4)
# 결과: deque([2, 3, 4])

• deque는 생성 시 최대 길이를 설정할 수 있다.
• 최대 길이를 설정하면 deque에 저장되는 요소의 개수를 제한할 수 있다.
• 최대 길이에 도달한 deque에 새 요소를 추가하면, 반대쪽 끝에서 하나의 요소가 자동으로 제거된다.
• 이 기능은 제한된 메모리를 다루거나 고정된 크기의 데이터 집합을 유지해야 하는 경우 유용하다.

 

4. 스레드 안전성

• deque는 스레드 안전(thread-safe)하게 구현되어 있다.
• 따라서 여러 스레드에서 동시에 deque에 접근하여 요소를 추가하거나 삭제할 수 있다.

 

---

사용 예시

큐(Queue) 구현

queue = deque()

# 큐에 요소 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐에서 요소 제거
x = queue.popleft()

print(x)  # 결과: 1
print(queue)  # 결과: deque([2, 3])

• deque를 사용하여 큐를 구현할 수 있다.
• append( ) 메서드를 사용하여 큐의 끝에 요소를 추가하고, popleft( ) 메서드를 사용하여 큐의 첫 번째 요소를 제거한다.

 

슬라이딩 윈도우(Sliding Window) 구현

window = deque(maxlen=k)

for i in range(n):
    window.append(nums[i])
    if i >= k - 1:
        print(window)  # 현재 윈도우의 상태를 출력
        # 다음 단계로 윈도우를 이동시키는 작업 수행
        window.popleft()

• 슬라이딩 윈도우는 고정된 크기의 윈도우를 배열 또는 리스트에서 한 번에 하나씩 이동시키는 기법이다.
• deque의 최대 길이를 설정하여 슬라이딩 윈도우를 구현할 수 있다.
• append( ) 메서드를 사용하여 윈도우에 새로운 요소를 추가하고, popleft( ) 메서드를 사용하여 윈도우의 첫 번째 요소를 제거한다.

 

---