데크(deque)

deque

double-ended queue의 줄임말로 큐의 앞(front)과 뒤(rear)에서 삽입과 삭제가 가능한 큐를 의미한다.


파이썬 collections.deque


요소 추가deque.append(x)

deque의 오른쪽(마지막)에 삽입한다.

import collections
deq = collections.deque(['a', 'b', 'c'])
deq.append('d')
# deque(['a', 'b', 'c', 'd'])


요소 추가deque.appendleft(x)

deque의 왼쪽(앞)에 삽입한다.

deq = collections.deque(['a', 'b', 'c'])
deq.appendleft('d')
# deque(['d', 'a', 'b', 'c'])


iterable 추가 deque.extend(iterable)

iterable argument(list, tuple, str)를 오른쪽(마지막)에 삽입한다.

deq = collections.deque(['a', 'b', 'c'])
deq.extend('d')
# deque(['a', 'b', 'c', 'd'])


iterable 추가 deque.extendleft(iterable)

iterable argument(list, tuple, str)를 왼쪽(앞)에 삽입한다.

deq = collections.deque(['a', 'b', 'c'])
deq.extendleft('d')
# deque(['d', 'a', 'b', 'c'])


append와 extend 차이점
a = ['a', 'b','c']
b = ['a', 'b','c']
a.append('de')
b.extend('de')

print('append 결과 : ', a)
print('extend 결과 : ', b)

# append 결과 :  ['a', 'b', 'c', 'de'] 
# extend 결과 :  ['a', 'b', 'c', 'd', 'e']
요소 제거deque.pop()

오른쪽(마지막)에서 부터 차례대로 제거와 반환한다.

deq = collections.deque(['a', 'b', 'c'])
print('deque.pop() :', end=' ')
while True:
    try:
        print(deq.pop(), end=' ')
    except:
        break
# deque.pop() : c b a


요소 제거deque.popleft()

왼쪽(앞)에서 부터 차례대로 제거와 반환한다.

deq = collections.deque(['a', 'b', 'c'])
print('deque.popleft() :', end=' ')
while True:
    try:
        print(deq.popleft(), end=' ')
    except:
        break
# deque.popleft() : a b c


요소 회전deque.rotate(n)

요소를 값만큼 회전 해주는 메소드이다. 인자(n) 값이 음수이면 왼쪽으로 회전하고, 양수이면 오른쪽으로 회전한다.

deq = collections.deque(['a', 'b', 'c', 'd', 'e'])
deq.rotate(1)
print('deq >>', ' '.join(deq))

deq2 = collections.deque(['a', 'b', 'c', 'd', 'e'])
deq2.rotate(2)
print('deq2 >>', ' '.join(deq2))

deq3 = collections.deque(['a', 'b', 'c', 'd', 'e'])
deq3.rotate(-1)
print('deq3 >>', ' '.join(deq3))

deq4 = collections.deque(['a', 'b', 'c', 'd', 'e'])
deq4.rotate(-2)
print('deq4 >>', ' '.join(deq4))

# deq >> e a b c d
# deq2 >> d e a b c
# deq3 >> b c d e a
# deq4 >> c d e a b


데크의 시간 복잡도
함수 시간복잡도
append O(1)
appendleft O(1)
pop O(1)
popleft O(1)
extend O(k)
extendleft O(k)
rotate O(k)
remove O(n)