[자료구조] 데큐(deque; double-ended queue)

데큐(deque; double-ended queue)

리스트의 양쪽 끝에서 삽입과 삭제를 모두 허용하는 자료의 구조.

이것은 스택과 큐의 자료 구조를 복합한 형태

 

 

Deque 구조

 

 

Deque import 및 생성

 

from collections import deque

# deque 생성
deq = deque()

 

 

Deque 원소 삽입

 

# item을 deque 오른쪽 끝에 삽입
deq.append(item) 

# item을 deque 왼쪽 끝에 삽입
deq.appendleft(item)

 

 

Deque 원소 삭제

 

# deque 오른쪽 끝에 있는 item을 pop한 후 삭제
deq.pop()

# deque 왼쪽 끝에 있는 item을 pop한 후 삭제
deq.popleft()

# item을 deque에서 찾아 삭제
deq.remove(item)

 

# deque 원소 삽입 삭제 예시
>>> deq.append(3)
>>> deq.append(1)
>>> deq.append(8)
>>> deq.pop()
8
>>> deq.popleft()
3
>>> deq.pop()
1

 

 

 

item을 추가해주는 메소드 - extend(), extendleft()

 

append() vs extend()

 

>>> deq.append('A')
>>> deq.append('B')
>>> deq.append('C')

# append를 통해 두 글자 삽입
>>> deq.append('DE')
# extend를 통해 두 글자 삽입
>>> deq.extend('FG')

>>> deq.popleft()
'A'

# extend를 통해 삽입한 경우 한 글자씩 따로 삽입되어있음
>>> deq.pop()
'G'
>>> deq.pop()
'F'

# extend를 통해 삽입한 경우 두 글자가 같이 삽입되어있음
>>> deq.pop()
'DE'

 

 

item들을 값 만큼 회전 해주는 메소드 - rotate(값)

음수 - 왼쪽 회전

양수 - 오른쪽 회전

 

# deque 생성
>>> deq = deque(['A','B','C','D','E'])
>>> deq
deque(['A', 'B', 'C', 'D', 'E'])

# 오른쪽으로 1 회전
>>> deq.rotate(1)
>>> deq
deque(['E', 'A', 'B', 'C', 'D'])

# 왼쪽으로 1 회전
>>> deq.rotate(-1)
>>> deq
deque(['A', 'B', 'C', 'D', 'E'])
>>> deq.rotate(3)
>>> deq
deque(['C', 'D', 'E', 'A', 'B'])
>>> deq.rotate(-3)
>>> deq
deque(['A', 'B', 'C', 'D', 'E'])