[자료구조][Python] 덱 (Deque)

 

 

덱

덱(Double Ended QUEue)는 앞서 이야기한 스택(Stack)과 큐(Queue)의 특성을 모두 가지고 있는 자료구조이다.

두 가지의 특성을 모두 가지고 있는 자료구조답게 덱의 앞과 뒤 모두에서 삽입과 삭제가 이루어진다.

덱의 구조

 

또한 덱을 잘 이용하면 효율적으로 시간복잡도를 줄이거나, 정렬 효과를 얻을 수 있으니 잘 알아두도록 하자.

 

스택(Stack)과 큐(Queue)가 뭔지 잘 모르겠다면, 아래 게시글을 참고하자.

 

https://pink-saurus.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0python-%EC%8A%A4%ED%83%9D-Stack

[자료구조][Python] 스택 (Stack)

https://pink-saurus.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0python-%ED%81%90-Queue

[자료구조][Python] 큐 (Queue)

 

---

덱의 초기화

덱을 import하고 초기화하는 방법은 다음과 같다.

from collections import deque

D = deque()

---

덱의 연산/메서드

메서드	설명
D.append(data)	덱(D)의 오른쪽에 data를 삽입한다.
D.appendleft(data)	덱(D)의 왼쪽에 data를 삽입한다.
D.pop()	덱(D)의 가장 오른쪽 data를 삭제한다. 이때 삭제된 원소가 리턴된다.
D.popleft()	덱(D)의 가장 왼쪽 data를 삭제한다. 이때 삭제된 원소가 리턴된다.
D.extend(array)	덱(D)의 오른쪽에 array를 순회하며 삽입한다.
D.extendleft(array)	덱(D)의 왼쪽에 array를 순회하며 삽입한다.
D.insert(n, data)	덱(D)의 n번째 인덱스에 data를 삽입한다. n의 뒤쪽은 한 칸씩 밀려난다.
D.remove(data)	덱(D)에서 data를 삭제한다. 중복되는 data가 있을 시 가장 왼쪽의 data부터 삭제된다.
D.rotate(n)	덱(D)을 n만큼 회전한다. n이 양수면 시계방향, 음수면 반시계방향이다.
D.reverse()	덱(D)을 반전시킨다.
D.clear()	덱(D)을 초기화한다.

---

덱의 삽입(apeend)과 삭제(pop)

from collections import deque

D = deque()

D.append(0)       # 0
D.append(1)       # 0 1
D.appendleft(-1)  # -1 0 1

D.pop()      # -1 0
D.popleft()  # 0

---

덱의 확장(extend)

from collections import deque

D = deque()

D.append(0)  # 0

array = [10, 11, 12]

D.extend(array)  # 0 10 11 12
D.extendleft(array) # 12 11 10 0 10 11 12

 

---

덱의 insert와 remove

from collections import deque

D = deque()

D.append(0)  # 0

array = [10, 11, 12]

D.extend(array)  # 0 10 11 12

D.insert(1, 9)  # 0 9 10 11 12
D.insert(1, 9)  # 0 9 9 10 11 12
D.remove(9)  	# 0 9 10 11 12

---

덱의 회전(rotate)과 반전(reverse), 그리고 초기화(clear)

from collections import deque

D = deque()

D.append(0)  # 0

array = [10, 11, 12]

D.extend(array)  # 0 10 11 12

D.rotate(1)  # 12 0 10 11

D.rotate(-1) # 0 10 11 12

D.reverse()  # 12 11 10 0

D.clear()    #