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

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

---

 

1. 덱(Deque) 구조란?

• 덱 구조는 양쪽 끝에 자료를 넣거나 양쪽 끝에서 자료를 뺼 수 있는 구조이다.
• 스택과 큐를 모두 구현할 수 있는 자료구조이다.

 

2. 파이썬에서 Deque 만들어보기

 

• 파이썬의 collections 라이브러리에 내장되어있는 deque함수를 활용하여 구현했다.
• 다음 예를 보면, deque 안에는 iterable한 객체가 들어가야 하므로 리스트를 넣어주었다.
• 리스트와 똑같이 인덱싱도 가능하다.

from collections import deque
mydeq = deque([1,2,3,4])    # deque 안에 들어가는 객체는 iterable이어야 함.
for i in range(len(mydeq)):
    print(mydeq[i])

1
2
3
4

 

i) append & appendleft

 

Input:

mydeq.appendleft(-10)   #왼쪽에 원소추가
mydeq

Output:

deque([-10, 1, 2, 3, 4])

 

Input:

mydeq.append(10)    #오른쪽에 원소추가
mydeq

Output:

deque([-10, 1, 2, 3, 4, 10])

 

ii) pop & popleft

 

Input:

print(mydeq.pop())    #오른쪽에서 원소빼냄
mydeq

Output:

10
deque([-10, 1, 2, 3, 4])

 

Input:

print(mydeq.popleft())    #왼쪽에서 원소빼냄
mydeq

Output:

-10
deque([1, 2, 3, 4])

 

iii) 번외 : list에는 특정 인덱스를 빼오는 pop(숫자)방법이 있는데 이는 덱에서 적용이 안될까?

Input:

print(mydeq.pop(0))    #덱에서도 리스트의 pop(0)같은 특정 인덱스 pop가 될까?

Output:

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-37-5d182d45b422> in <module>()
----> 1 print(mydeq.pop(0))   ##덱에서도 리스트의 pop(0)같은 특정 인덱스 pop가 될까?

TypeError: pop() takes no arguments (1 given)

그렇다. 발생한 에러를 보면 알 수 있듯, deque객체의 pop()는 arguments를 받아들이지 않는다고 한다.

 

결론

그러면 덱(Deque) 객체는 어떤 부분에 활용할 수 있을까?

1. 파이썬에서 자주 사용하는 리스트와 매우 유사하지만, 덱에는 appendleft()와 같이 왼쪽 부분에 원소를 추가하는 기능이 존재하는 점이 굉장히 큰 장점으로 보인다.

2. 리스트와 마찬가지로 pop(), popleft()를 통해 왼쪽, 오른쪽 어느쪽에서든지 원소를 빼낼 수 있다. 하지만 list에는 특정 인덱스를 빼오는 기능도 있으므로 → pop() 관점에서 본다면 리스트가 더 장점이 있는 것으로 보인다.

3. list를 활용하여 문제를 처리할 때, 원소를 오른쪽뿐만 아니라 왼쪽에도 추가해야하는 경우가 발생한다면 덱(Deque)을 활용할 수 있도록 하자. 그 후, 다시 리스트 객체로 변환시킨 뒤 pop() 등의 처리를 해야할 때 이점을 챙길 수 있을 것으로 보인다.