목차
collections 모듈
deque
collections.deque([iterable[, maxlen]])
double-ended queue 의 줄임말
앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미
list와 비슷
collections.deque([iterable[, maxlen]])
큐를 일반화한 형태의 추상 자료형(ADT)
head 와 tail 이라는 이름의두 포인터를 갖고 있다가 새로운 아이템이 추가될 때마다 앞쪽 또는 뒤쪽으로 연결시켜 주기만 하면 됨.
연결 후에는 포인터를 이동
list와 차이점, 장점
데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠름
컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우,
list: O(n)이 소요deque: O(1)로 접근 가능
collections.deque의 메소드(method)들
데이터 추가
append(x)
deque의 오른쪽(마지막)에 추가(삽입)
# list.append() vs deque.append()
import collections
# list
lst = ['a', 'b']
lst.append('c')
print(lst)
#['a', 'b', 'c']
# collections.deque
deq = collections.deque(['a', 'b'])
deq.append('c')
print(deq)
#deque(['a', 'b', 'c'])
appendleft(x)
왼쪽 즉, 앞쪽에서 x를 추가(삽입)해주는 메소드
import collections
deq = collections.deque(['a', 'b'])
deq.appendleft('c')
print(deq)
#deque(['c', 'a', 'b' ])
extend(iterable)
iterable argument(list, str, tuple...)를 오른쪽(마지막)에 elements를 추가(삽입)해주는 메소드
append추가요소를 하나로 봄extend추가요소를 각각 하나로 봄
deq = collections.deque(['a', 'b'])
deq.extend('cd')
print(deq)
#deque(['a', 'b', 'c', 'd'])
extendleft(iterable)
iterable argument(list, str, tuple...)를 왼쪽(앞쪽)에 elements를 추가(삽입)해주는 메소드
deq = collections.deque(['a', 'b'])
deq.extend('cd')
print(deq)
# deque(['c', 'd', 'a', 'b'])
데이터 반환
pop()
오른쪽(마지막)에서 부터 차례대로 반환 후 제거 하는 메소드
deq = collections.deque(['a', 'b'])
deq.pop()
print(deq)
#'b'
#deque(['a'])
popleft()
왼쪽(앞쪽)에서 부터 차례대로 반환 후 제거 하는 메소드 deq = collections.deque([‘a’, ‘b’]) deq.popleft()
deq = collections.deque(['a', 'b'])
deq.pop()
print(deq)
#'a'
#deque(['b'])
데이터 위치 변환
rotate(n)
[n = 양수]
오른쪽 데이터를 pop해서 appendleft
즉, 입력한 수만큼 deque의 값들을 오른쪽으로 이동.
[n = 음수]
오른쪽 데이터를 pop해서 append
즉, 입력한 수만큼 deque의 값들을 왼쪽으로 이동.
## 양수
deq = collections.deque(['a', 'b', 'c', 'd'])
deq.rotate(1)
print(deq)
#deque(['d', 'a', 'b', 'c'])
deq = collections.deque(['a', 'b', 'c', 'd'])
deq.rotate(2)
print(deq)
#deque(['c', 'd', 'a', 'b'])
## 음수
deq = collections.deque(['a', 'b', 'c', 'd'])
deq.rotate(-1)
print(deq)
#deque(['b', 'c', 'd', 'a'])
deq = collections.deque(['a', 'b', 'c', 'd'])
deq.rotate(-2)
print(deq)
#deque(['c', 'd', 'a', 'b'])
revrese
데이터를 통째로 뒤집어 버림
deq = collections.deque(['a', 'b', 'c', 'd'])
deq.reverse()
print(deq)
#deque(['d', 'c', 'b', 'a'])