파이썬 collections deque 사용법과 응용

 

그냥 예뻐서 넣은 사진

✏️ deque

Stack이나 queue처럼 한 방향에서 삽입과 삭제가 일어나는게 아니라 양방향에서 삽입과 삭제가 일어나는 자료구조이다.

 

파이썬에서 list를 사용하는 것과 유사하지만 deque를 사용하는 이유는 시간복잡도 때문이다.

리스트에서 0번 인덱스를 삭제한다고 생각해보자. 이때 리스트 내부에서는 0번 인덱스를 제거하고 끝이 아니라 뒤에있는 원소들을 앞으로 하나씩 당겨주는 연산을 더 수행하게된다. 따라서 list의 삭제연산은 O(n)이 걸리는데 반면 deque의 삭제연산은 O(1)이다. 따라서 push, pop이 빈번한 알고리즘의 경우 list보다 deque를 사용하는 것이 효율적이다.

 

✏️ collections.deque

 

1. collections.deque.append(x)

: deque의 맨뒤(오른쪽)에 삽입

from collections import deque 
dq = deque([1,2,3,4]) 
dq.append('a') 
print(dq)

#output
#deque([1, 2, 3, 4, 'a'])

 

2. collections.deque.appendleft(x)

: deque의 왼쪽에 삽입

from collections import deque 
dq = deque([1,2,3,4]) 
dq.appendleft('a') 
print(dq)

#output
#deque(['a', 1, 2, 3, 4])

 

3. collections.deque.clear()

: deque안의 모든 요소를 제거

from collections import deque 
dq = deque([1,2,3,4]) 
dq.clear()
print(dq)

#output
#deque([])

 

 

4. collections.deque.insert(i,x)

: i번째 인덱스에 x를 삽입

from collections import deque 
dq = deque([1,2,3,4]) 
dq.insert(3, 'a')
print(dq)

#output
#deque([1, 2, 3, 'a', 4])

 

5. collections.deque.pop()

: 맨 오른값을 제거하고 제거한 값을 리턴한다.

from collections import deque 
dq = deque([1,2,3,4]) 
pop_x = dq.pop()
print(dq)
print(pop_x)

#output
#deque([1, 2, 3])
#4

 

6. collections.deque.popleft()

: 맨 왼값을 제거하고 제거한 값을 리턴한다.

from collections import deque 
dq = deque([1,2,3,4]) 
pop_x = dq.popleft()
print(dq)
print(pop_x)

#output
#deque([2, 3, 4])
#1