deque(double-ended-que)

deque는 리스트 처럼 원소들을 담아둘 수 있는 자료구조이며 리스트와는 다르게 큐의 양 옆에서 원소를 삽입하거나, 지울 수 있습니다. 기존의 리스트를 이용할 때는 원소들을 순환(rotate) 시키거나 리스트 가장 앞에 원소를 추가시키려면 직접 코드로 구현해야 하지만 deque 를 이용하면 deque 원소들을 순환(rotate)시키거나 deque 가장 앞에 원소를 추가시키는 등 기존 리스트에서는 하기 어려웠던 다양한 기능들을 활용할 수 있습니다. 이번 포스트에서는 deque 메소드의 여러가지 사용법을 정리하겠습니다.

deque 의 용도

deque 자료구조는 리스트로는 활용하기 어려운 기능들을 이용할 때 쓰입니다.

deque 사용법

deque를 사용하기 위해서는 collections에서 deque를 import 해주어야 합니다.

from collections import deque

deque 선언하기

빈 deque 선언하기

빈 deque를 선언할 때는 변수 = deque() 로 선언합니다.

from collections import deque

deq = deque()

원소들을 포함한 deque

원소들을 포함한 deque는 변수 = deque([1,2,3,4]) 형식으로 deque() 안에 리스트[]가 들어간 모양으로 표현합니다.

from collections import deque

deq = deque([1,0,0,4])

deque 의 maxlen

deque는 리스트와 다르게 deque의 최대 길이(maxlen)를 지정할 수 있습니다. 지정한 최대 길이(maxlen) 이상으로 deque에 원소가 추가되면 처음 원소는 사라지고 새로 입력한 원소가 추가됩니다.

from collections import deque

deq1 = deque([1,0,0,4],maxlen=4)
deq2 = deque([1,0,0,4],maxlen=4)

deq1.append("sky")
deq2.appendleft("sky")

print("deq1 =",deq1)
print("deq2 =",deq2)

실행 결과

deq1 = deque([0, 0, 4, 'sky'], maxlen=4)
deq2 = deque(['sky', 1, 0, 0], maxlen=4)

실행 결과를 보면 deque의 최대 길이가 지정되어있을 때 append 를 사용하면 가장 왼쪽의 원소가 삭제되며 appendleft를 사용하면 가장 오른쪽의 원소가 삭제되는 것을 알 수 있습니다.

  1. deque 의 slice

deque에서는 리스트의 slice 기능을 사용할 수 없습니다.

from collections import deque
number=deque([1,2,3,4,5])
print(number[0])
print(number[2:4])

실행 결과

1
TypeError: sequence index must be integer, not 'slice'

number[0] 을 입력하면 1이 출력되지만(가능) number[2:4]을 하게 되면 Type Error가 발생합니다.(slice 불가능)

deque 메소드 정리

deq = deque([1,0,0,4])를 예시로 deque의 여러가지 메소드를 정리하겠습니다.

1. deq.append() , deq.appendleft()

deq.append(“원소”): deque의 가장 오른쪽 끝에 새로운 원소 추가 deq.appendleft(“원소”): deque의 가장 왼쪽 끝에 새로운 원소 추가

append,appendleft 예시

from collections import deque

deq1 = deque([1,0,0,4])
deq2 = deque([1,0,0,4])

deq1.append("sky")
deq2.appendleft("sky")

print("deq1 =",deq1)
print("deq2 =",deq2)

실행결과

deq1 = deque([1, 0, 0, 4, 'sky'])
deq2 = deque(['sky', 1, 0, 0, 4])

2. deq.extend(), deq.extendleft()

deq.extend(“원소”): deque의 가장 오른쪽 끝에 새로운 원소 리스트 연장 deq.extendleft(“원소”): deque의 가장 왼쪽 끝에 새로운 원소 리스트 연장

extend,extendleft 예시

from collections import deque

deq1 = deque([1,0,0,4])
deq2 = deque([1,0,0,4])

deq1.extend("sky")
deq2.extendleft("sky")

print("deq1 =",deq1)
print("deq2 =",deq2)

실행결과

deq1 = deque([1, 0, 0, 4, 's', 'k', 'y'])
deq2 = deque(['y', 'k', 's', 1, 0, 0, 4])

실행 결과를 보면 오른쪽에 “sky”를 연장시킬 때는 정순으로 원소가 배열되지만, 왼쪽에 “sky”를 연장시킬 때는 역순으로 원소가 배열됩니다.

3. deq.pop(), deq.popleft()

deq.pop(): 가장 오른쪽 원소를 반환 후 리스트에서 삭제 deq.popleft(): 가장 왼쪽 원소를 반환 후 리스트에서 삭제

pop,popleft 예시

from collections import deque

deq1 = deque([1,0,0,4])
deq2 = deque([1,0,0,4])

deq1.pop()
deq2.popleft()

print("deq1 =",deq1)
print("deq2 =",deq2)

실행결과

deq1 = deque([1, 0, 0])
deq2 = deque([0, 0, 4])

4. deq.rotate()

deq.rotate(“양수”): “양수”번 오른쪽으로 deque 순환 deq.rotate(“음수”): “음수”번 왼쪽으로 deque 순환

rotate 예시

from collections import deque

deq1 = deque([1,0,0,4])
deq2 = deque([1,0,0,4])
deq3 = deque([1,0,0,4])

deq1.rotate(1)
deq2.rotate(-1)
deq3.rotate(-2)
print("deq1 =",deq1)
print("deq2 =",deq2)
print("deq3 =",deq3)

실행결과

deq1 = deque([4, 1, 0, 0])
deq2 = deque([0, 0, 4, 1])
deq3 = deque([0, 4, 1, 0])

실행 결과를 보면 deq1.rotate(1) 일 때 오른쪽으로 한 번 순환했고 deq2.rotate(-1) 일 때 왼쪽으로 한 번 순환했으며 deq3.rotate(-2)일 때 왼쪽으로 deque가 두 번 순환했음을 알 수 있습니다.

※주의: deque의 rotate메소드는 기존의 deque값을 변환시키는 메소드입니다. 예를 들어서 deq1 = deque([1,0,0,4]) 에서 deq1.rotate(1)을 하면 deq1 = deque([4, 1, 0, 0])으로 기존 deq1값이 변합니다. (참고로 deq1.rotate(1)값은 return값이 없습니다. 사용할 때 deque를 rotate한 값을 출력/반환 하고자 print(deq1.rotate(1))또는 return (deq1.rotate(1)) 을 하게 되면 rotate한 값이 출력/반환 되는게 아니라 그냥 None타입이 출력/반환 됩니다.

5. deq.insert()

deq.insert(“인덱스”,”원소”): 원하는 위치(인덱스)에 원소 삽입

insert 예시

from collections import deque

deq1 = deque([1,0,0,4])
deq2 = deque([1,0,0,4])
deq3 = deque([1,0,0,4])

deq1.insert(1,"sky")
deq2.insert(-1,"sky")
deq3.insert(100,"sky")
print("deq1 =",deq1)
print("deq2 =",deq2)
print("deq3 =",deq3)

실행결과

deq1 = deque([1, 'sky', 0, 0, 4])
deq2 = deque([1, 0, 0, 'sky', 4])
deq3 = deque([1, 0, 0, 4, 'sky'])

실행 결과를 보면 deq1.insert(1,”sky”) 일 때 인덱스 1의 위치에 “sky” 가 들어가지만 deq2.insert(-1,”sky”)인 경우 “sky”가 인덱스 -1 위치의 바로 앞에 오게 되는 것을 알 수 있습니다. 추가적으로 deq3.insert(100,”sky”) 처럼 deque의 maxlen을 넘어선 값을 인덱스로 지정할 경우에는 마지막 위치에 원소를 삽입합니다.

6. deq.remove()

deq.remove(“원소”): 왼쪽부터 deque의 원소들을 조사해서 “원소”가 있으면 삭제합니다.

remove 예시

from collections import deque

deq1 = deque([1,0,4,0])

deq1.remove(0)

print("deq1 =",deq1)

실행결과

deq1 = deque([1, 4, 0])

실행결과를 보면 remove를 이용해 원소를 삭제했을 때 같은 원소라도 왼쪽의 원소를 먼저 삭제하는 것을 알 수 있습니다.

7. deq.reverse()

deq.reverse(): deque 원소들의 순서를 거꾸로 합니다.(좌우반전)

reverse 예시

from collections import deque

deq1 = deque([1,0,0,4])

deq1.reverse()

print("deq1 =",deq1)

실행결과

deq1 = deque([4, 0, 0, 1])