[자료구조] 데크(Deque)

데크(Deque) : 앞ㆍ뒤 양쪽 방향에서 엘리먼트를 추가하거나 제거

보통의 큐(Queue)나 스택(Stack)의 경우 한방향으로 진행되지만 Deque의 경우 양쪽 방향으로 엘리먼트를 추가하거나    제거할수 있으며 일반적인 리스트가 삽입이나 제거를 할경우 O(n)이 걸리지만, Deque의 경우 O(1)로 굉장히 빠르다. 

https://www.studytonight.com/java-examples/arraydeque-in-java

---

1. Deque의 특징

1. 시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다.

2. 삽입 / 삭제 연산이 빈번한 알고리즘에서 시간복잡도가 O(1)이므로  빠른 속도를 보여준다.

 

2. Deque 라이브러리

from collections import deque

 

3. 파이썬의 Deque 연산 

1. deque.append(): Deque의 뒤에 엘리먼트를 삽입한다.

list = ["a", "b", "c"]
deq = deque(list)

deq.append("★")
print(deq)
>>> deque(['a', 'b', 'c', '★'])

 

2. deque.appendleft(): Deque의 앞에 엘리먼트를 삽입한다.

list = ["a", "b", "c"]
deq = deque(list)

deq.appendleft("★")
print(deq)
>>> deque(['★', 'a', 'b', 'c'])

 

3. deque.extend(): iterable한 값을 넣으면 Deque의 뒤에 차례로 엘리먼트를 추가한다

list = ["a", "b", "c"]
deq = deque(list)

deq.extend(["★", "☆"])
print(deq)
>>> deque(['a', 'b', 'c', '★', '☆'])

 

4. deque.extendleft(): iterable한 값을 넣으면 Deque의 앞에 차례로 엘리먼트를 추가한다.

list = ["a", "b", "c"]
deq = deque(list)

deq.extendleft(["★", "☆"])
print(deq)
>>> deque(['☆', '★', 'a', 'b', 'c'])

 

5. deque.pop(): Deque의 뒤쪽 엘리먼트를 가져오면서 해당 엘리먼트를 데크에서 삭제한다.

list = ["a", "b", "c"]
deq = deque(list)

deq.pop()
print(deq)
>>> deque(['a', 'b'])

 

6. deque.popleft(): Deque의 앞쪽 엘리먼트를 가져오면서 해당 엘리먼트를 데크에서 삭제한다.

list = ["a", "b", "c"]
deq = deque(list)

deq.popleft()
print(deq)
>>> deque(['b', 'c'])

 

7. deque.clear() : Deque의 모든 요소를 삭제한다. 

list = ["a", "b", "c"]
deq = deque(list)

deq.clear()
print(deq)
>>> deque([])

 

8. deque.remove(value): value를 Deque에서 찾아 삭제한다.

list = ["a", "b", "c"]
deq = deque(list)

deq.remove("b")
print(deq)
>>> deque(['a', 'c'])

 

9. deque.rotate(n): 요소들을 n만큼 회전 해주는 메소드이다. (양수[오른쪽] / 음수[왼쪽] 이동)

list = ["★", "b", "c", "d", "e"]

# 1번 오른쪽 방향 이동
deq1 = deque(list)
deq1.rotate(1)
print(deq1)
>>> deque(['e', '★', 'b', 'c', 'd'])

# 3번 오른쪽 방향 이동
deq2 = deque(list)
deq2.rotate(3)
print(deq2)
>>> deque(['c', 'd', 'e', '★', 'b'])

# 1번 왼쪽 방향 이동
deq3 = deque(list)
deq3.rotate(-1)
print(deq3)
>>> deque(['b', 'c', 'd', 'e', '★'])

# 3번 왼쪽 방향 이동
deq4 = deque(list)
deq4.rotate(-3)
print(deq4)
>>> deque(['d', 'e', '★', 'b', 'c'])

---

참고서적

Do it! 알고리즘 코딩 테스트: 파이썬 편 (코딩 테스트를 처음 준비하는 취준생의 필독서!)

이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드)

 

추천 사이트

collections — Container datatypes — Python 3.11.0 documentation