오뚝이개발자

[Python] deque 사용법 본문

Language/파이썬

[Python] deque 사용법

땅어 2020. 12. 15. 17:13
728x90
300x250

 

deque(double ended queue)는 양방향 연결리스트로 구현되어 있어 양 끝단에 접근이 가능하고 데이터의 삽입, 삭제가 용이하다.(단, 중간 데이터는 제외) 여기선 대표적으로 많이 쓰이는 5가지 operation에 대해 사용법을 정리하려고 한다.

아, 참고로 deque를 사용하려면 import collections.deque를 해주어야 한다.

 

append(x), appendleft(x)


append(x)는 오른쪽 끝에 데이터 x를 추가, appendleft(x)는 왼쪽 끝에 데이터 x를 추가한다.

리스트와 달리 deque는 doubly linked list라 둘의 시간복잡도는 모두 O(1)이다.

 

pop(), popleft()


pop()은 일반적으로 알고있는 그 pop 연산이 맞다. 즉, stack의 pop처럼 오른쪽 끝의 원소를 pop한다.

popleft()는 맨 왼쪽 item을 pop한다.

마찬가지로 deque는 doubly linked list이므로 둘의 시간복잡도는 O(1)이다.

 

첫번째 원소 접근


사실 이부분이 좀 헷갈려서 포스팅하면서 정리하려고 했다. 

pop을 하지 않고 맨 처음 원소(가장 왼쪽)를 어떻게 알지? 하는 의문이 들어서 무슨 특별한 연산이 있을 줄 알았는데 그냥 단순히 q[0]을 해주면 된다... ㅎㅎ(허무...)

 

 

728x90
300x250
Comments