큐와 데크

• 큐는 선입선출 방식으로 작동한다.
• 데크는 양방향 큐이다.
  -즉, 앞, 뒤 방향에서 element를 추가하거나 삭제할 수 있다.
  결국 양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 형태의 추상자료형이다.

데크 구조

• 파이썬은 데크 자료형을 Collections 모듈에서 deque라는 이름으로 지원한다.

• 이중연결 리스트로 구현 되어있다.

• 리스트의 pop(0)은 시간복잡도가 O(n) 인데 반해, 데크의 popleft는 O(1) 이기 때문에 성능차이가 크다. -> 팰린드롭 문자열 판별에 사용하면 유의미한 개선이 가능할것 같다.

데크의 사용법

from collections import deque

deq = deque()

# Add element to the start
deq.appendleft(10)

# Add element to the end
deq.append(0)

# Pop element from the start
deq.popleft()

# Pop element from the end
deq.pop()

deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
deque.extend(array): 주어진 리스트를 데크의 오른쪽에 추가한다.
deque.extendleft(array): 주어진 리스트를 데크의 왼쪽에 추가한다.
deque.remove(item): item을 데크에서 찾아 삭제한다. (제일 처음 나온 해당 string만 제거됨)
deque.clear(): 해당 deque 전체 삭제
deque.reverse(): 말그대로 역순으로 정렬한다.
deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

데크를 언제 어디서 활용할까?

데크(deque)는 스택처럼 사용할 수도 있고, 큐 처럼 사용할 수도 있다.
시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다. 즉, 대부분의 경우에 데크(deque)는 리스트(list)보다 월등한 옵션이다.

데크는 특히 push/pop 연산이 빈번한 알고리즘에서 리스트보다 월등한 속도를 자랑한다.