저번 포스트에서는 나서스의 스택에 스택과 큐에 대해 알아보았다. 이번 포스트에서는 큐의 연장선상 개념(?)인 데크에 대해서 알아보겠다. 데크는 풀네임 영어로 Double Ended Queue를 의미한다. 즉, 양방향으로 끝이 존재하는 큐를 뜻한다. 이번에도 역시 그림을 그려보자.
큐와 모양 자체는 똑같다! 하지만, 큐는 한뱡으로 들어가고 나갈 수 없는 방면에 데크는 양끝에 데이터가 들어오고 나갈 수 있는 특징이 있다. 그렇다면 데크를 왜 사용하는지 알아보자. 이는 파이썬의 리스트 자료형과 비교하면 알 수 있다.
우리가 리스트에 insert하는 과정을 그림으로 그리면 다음과 같다. 먼저 insert를 하기 위한 공간 하나를 할당해주어야 한다. 그 다음 기존에 존재하던 자료의 갯수(N개, 위 그림에서는 2개)만큼 데이터들을 한칸씩 전부 뒤로 N번 밀어줘야한다. 극단적으로 생각했을 때, 리스트의 길이가 1억이라면 1억번을 뒤로 한칸씩 밀어줘야(Shift 연산)한다. 이는 시간복잡도가 O(N)이 소요된다. (N번의 연산이 필요하므로)
반면에 데크는 뒤로 밀어주는 과정이 필요없이 그냥 앞에다가 새로운 데이터를 넣으면 끝이다. 이로써 시간복잡도는 O(1)이 소요된다. (단 한번의 연산으로 끝나므로)
이제 코드로 직접 데크를 경험해보자. 필자는 데크를 collections 라이브러리를 통해서 사용하는 방법과 직접 구현하는 방법 두 가지를 모두 소개할 것이다.
[collections 라이브러리를 사용한 deque]
# 01. collections 라이브러리를 사용하여 데크를 사용하는 방법 & 리스트와의 속도 비교
import time
import datetime
from collections import deque
def timestamp(obj, iter_=200):
print(type(obj))
start = time.time()
for i in range(iter_):
if isinstance(obj, deque):
obj.appendleft(i)
elif isinstance(obj, list):
obj.insert(0, i)
print(datetime.timedelta(time.time() - start), '\n')
dq = deque([i for i in range(100)])
li = list([i for i in range(100)])
timestamp(dq) # 0:00:02.410126
timestamp(li) # 0:00:06.385803collections 내장 라이브러리에 구현되어 있는 데크를 사용한 코드이다. timestamp 메소드는 인자로 받은 obj가 데크 타입일 경우 appendleft, 리스트 타입을 경우 insert를 반복적으로 수행하고 걸리는 시간을 출력한다. 초만 보아도 압도적으로 데크가 속도가 빠르다!
[직접 구현한 데크]
# 02. 데크 직접 구현 (연결, 노드 사용)
class Node:
def __init__(self, data):
# 해당 노드의 데이터와 앞, 뒤 노드
self.data = data
self.front = None
self.behind = None
class Deque:
def __init__(self, data):
# 맨 앞과 맨 뒤의 노드와 현재 탐색중인 위치의 노드
self.front = None
self.last = None
self.current = None
# 입력값이 리스트로 들어온 경우
if isinstance(data, list):
# for loop 안에서의 기준 노드
curr_node = None
for i in range(len(data)-1):
if i == 0:
# 첫 노드와 두 번째 노드를 생성한다.
self.front = self.current = Node(data[i])
self.last = next_node = Node(data[i+1])
# 첫 노드와 두 번째 노드를 양방향으로 연결한다.
self.front.behind = next_node
self.last.front = self.front
# 다음 노드를 for loop 안에서의 기준 노드로 설정한다.
curr_node = next_node
else:
# 새로운 노드로 생성하고 self.last 로 설정한다.
self.last = next_node = Node(data[i+1])
# 기준 노드와 새로운 노드를 양방향으로 연결한다.
curr_node.behind = next_node
self.last.front = curr_node
# 기준 노드를 새로 생성한 노드로 설정한다.
curr_node = next_node
# 입력값이 정수로 들어온 경우
elif isinstance(data, int):
self.front = self.current = Node(data)
def peek_all(self) -> List[Node]:
"""
데크의 모든 노드를 리스트로 반환한다. (순차탐색)
:return:
"""
# 맨 앞의 노드를 탐색을 시작할 노드로 설정한다. (존재하지 않으면 끝낸다.)
retrieve_node = self.front
if retrieve_node is None:
return None
# 다음 노드가 존재하지 않을 때까지 nodes 리스트에다 (Node 인스턴스들을) 추가한다.
nodes = list([retrieve_node])
while retrieve_node.behind is not None:
nodes.append(retrieve_node.behind)
retrieve_node = retrieve_node.behind
return nodes
def is_empty(self):
"""
데크가 비었는지 검사한다.
:return:
"""
return True if not len(self.peek_all()) else False
def push_front(self, data):
"""
데크의 맨 앞에 새로운 노드를 생성한다.
:param data:
:return:
"""
new_node = Node(data)
new_node.behind = self.front
self.front.front = new_node
self.front = new_node
def push_behind(self, data):
"""
데크의 맨 뒤에 새로운 노드를 생성한다.
:param data:
:return:
"""
new_node = Node(data)
new_node.front = self.last
self.last.behind = new_node
self.last = new_node
def pop_front(self):
"""
데크의 맨 앞에 노드를 제거한다.
:return:
"""
assert self.front is not None, '지울 값이 존재하지 않습니다.'
remove_node = self.front
self.front = self.front.behind
self.front.front = None
return remove_node
def pop_last(self):
"""
데크의 맨 뒤에 노드를 제거한다.
:return:
"""
assert self.last is not None, '지울 값이 존재하지 않습니다.'
remove_node = self.last
self.last = self.last.front
self.last.behind = None
return remove_node
def peek_front(self):
"""
데크의 맨 앞의 노드를 반환한다.
:return:
"""
print(self.front, self.front.data)
return self.front
def peek_last(self):
"""
데크의 맨 뒤의 노드를 반환한다.
:return:
"""
print(self.last, self.last.data)
return self.last
def peek_current(self):
"""
데크의 현재 탐색중인 노드를 반환한다.
:return:
"""
print(self.current, self.current.data)
return self.current
def peek_next(self):
"""
데크의 현재 탐색중 노드의 다음 노드를 반환한다.인 (현재 위치를 다음 위치로 변경)
:return:
"""
assert self.current.behind is not None, '더 이상 값이 존재하지 않습니다.'
self.current = self.current.behind
return self.peek_current()
def peek_prev(self):
"""
데크의 현재 탐색중인 노드의 이전 노드를 반환한다. (현재 위치를 이전 위치로 변경)
:return:
"""
assert self.current.front is not None, '더 이상 값이 존재하지 않습니다.'
self.current = self.current.front
return self.peek_current()
custom_dq = Deque([1, 2, 3])
custom_dq.peek_front() # 1
custom_dq.peek_last() # 3
custom_dq.peek_current() # 1
custom_dq.peek_next() # 2
custom_dq.peek_next() # 3
# custom_dq.peek_next() # Assertion error
custom_dq.peek_prev() # 2
custom_dq.peek_prev() # 1
# custom_dq.peek_prev() # Assertion error
custom_dq.push_front(10) # [10, 1, 2, 3]
custom_dq.peek_front() # 10
custom_dq.push_behind(20) # [10, 1, 2, 3, 20]
custom_dq.peek_last() # 20
nodes = custom_dq.peek_all()
[print(node.data) for node in nodes]위 코드는 필자가 양방향 연결 리스트 형태를 통해 직접 구현한 코드이다. 생각보다 많이 길어졌다. (코드가 긴 관계로 설명을 주석으로 대체했다.) 하지만, 기본으로 구현해야하는 메소드인 push_front(), push_last(), pop_front(), pop_last() 이외에도 정상적으로 데크가 생성되었는지 검증하기 위한 메소드들을 추가로 구현했다.
이 부분은 직접 구현하기 어렵다면 코드를 복사해서 직접 하나하나 디버거를 돌려가며 분석해도 좋다. 그리고 필자의 코드 없이도 스스로 구현할 수 있을 때까지 반복 연습을 하기를 바란다.
'[CS] - Data Structure' 카테고리의 다른 글
| # 3. 단방향 연결 리스트 (Single Linked List) (0) | 2021.12.03 |
|---|---|
| # 1. 스택과 큐 (Stack and Queue) (0) | 2021.12.02 |
| # 0. 자료구조 카테고리의 시작.. (0) | 2021.12.02 |
댓글