💡데크 기본 개념
- 스택(stack)과 큐(Queue)의 연산을 모두 가지고 있는 복합 자료형 자료구조
- 데크(Deque) : Double Ended Queue의 줄임말로서 양쪽 끝 데이터를 모두 추출할 수 있는 큐의 형태
- 데크 자료구조는 양쪽 끝에서 삽입 삭제 모두 가능하다
- 파이썬에서는 데크 자료구조를 collections 라이브러리를 활용하여 사용 가능하다
- 데크 자료구조는 이중 연결 리스트로 구현하는 것이 유용하다. 포인터를 2개 활용해서 앞뒤에서 삽입 삭제가 가능하다.
💡데크 자료구조 직접 구현
- 다음 연산을 지원하는 원형 데크를 디자인하라
- MyCircularDeque(k: int) - k값으로 최대 원형 데크의 사이즈 초기화하기
- insertFront(value: int) - 입력값(value)을 데크의 앞쪽에 삽입하고, 성공했다면 True, 실패했다면 False 반환하기
- insertLast(vlaue: int) - 입력값(value)을 데크의 뒤쪽에 삽입하고, 성공했다면 True, 실패했다면 False
- deleteFront() - 데크 자료구조의 맨 앞의 값을 삭제하고, 성공했다면 True, 실패했다면 False
- deleteLast() - 데크 자료구조의 맨 뒤의 값을 삭제하고, 성공했다면 True, 실패했다면 False
- getFront() - 데크 자료구조의 맨 앞의 값을 반환하되 만약 값이 없다면 -1을 반환
- getLast() - 데크 자료구조의 맨 뒤의 값을 반환하되 만약 값이 없다면 -1을 반환
- isEmpty() - 데크 자료구조의 값이 비어있다면 True, 아니면 False
- isFull() - 데크 자료구조의 값이 가득 차 있다면 True, 아니면 False
- 이중 연결 리스트를 활용하여 원형 데크 자료구조 구현
💻 원형 데크 초기화
class MyCircularDeque(object):
def __init__(self, k):
"""
:type k: int
"""
# 왼쪽(head), 오른쪽(tail) index 역할을 할 연결리스트 정의
self.head, self.tail = ListNode(None), ListNode(None)
self.head.right, self.tail.left = self.tail, self.head
# 최대 길이와 현재 길이 정보를 담을 변수 정의
self.maxlen, self.length = k, 0
💻 원형 데크 데이터 추가 내장함수
def _add(self, node: ListNode, new: ListNode):
# 삽입할 연결 리스트의 기존 오른쪽 값을 정의한다
# 아마 None 값일 것으로 예상한다.
# front : n --> self.head.right.right --> self.tail.right
# last n --> self.tail.left.right --> self.head.right
n = node.right
# 연결 리스트의 오른쪽 값을 새로운 값으로 업데이트한다.
# front : self.head.right.right == ListNode(value)
# last : self.tail.left.right == ListNode(value)
node.right = new
# 새로운 노드의 left 값은 기존 node의 값으로 정의하고 (즉, head 역할)
# right 값은 위에서 따로 정의한 None 값으로 정의해준다
# head - new - None
new.left, new.right = node, n
# 그리고 n의 left 값을 새로운 값으로 정의한다.
# front : n = self.head.right.right
# last : n = self.tail.left.right
n.left = new
💻 원형 데크 데이터 삭제 내장함수
def _del(self, node: ListNode):
# ? None 값을 미리 정의하는건가?
n = node.right.right
# 업데이트
node.right = n
# ? n의 왼쪽 값을 입력한 포인터의 값으로 정의? 왜?
n.left = node
💻 원형 데크 앞쪽, 뒤쪽 데이터 추가
def insertFront(self, value):
"""
:type value: int
:rtype: bool
"""
# 현재 길이 정보를 확인한다
# 현재 길이가 최대 길이와 같다면 더이상 삽입할 수 없기에 False를 return
if self.length == self.maxlen:
return False
# 현재 길이가 아직 최대 길이에 도달하지 않았다면 데이터를 삽입할 것이기에
# 현재 길이를 업데이트 해준다
self.length += 1
# value값을 원형 데크 자료구조에 추가해준다.
# 내장 함수 _add 메서드를 사용할 예정
# value 값을 연결리스트 자료구조 형태에 담아서 추가한다.
self._add(self.head, ListNode(value))
def insertLast(self, value):
"""
:type value: int
:rtype: bool
"""
# 현재 길이 확인하여 최대 길이에 도달했다면 False return
if self.length == self.maxlen:
return False
# 현재 길이 업데이트
self.length += 1
# 뒤쪽에 값을 삽입할 때는 self.tail 포인터를 활용
# self.tail.left == 초기에 self.head로 지정했음
# 업데이트 될 것으로 예상하면서 작업
self._add(self.tail.left, ListNode(value))
💻 원형 데크 앞쪽, 뒤쪽 데이터 삭제
def deleteFront(self):
# 삭제할 값이 없다면 False return
if self.length == 0:
return False
# 현재 길이 업데이터
self.length -= 1
# 삭제 로직
self._del(self.head)
return True
def deleteLast(self):
# 삭제할 값이 없다면 False return
if self.length == 0:
return False
# 현재 길이 업데이터
self.length -= 1
# 삭제 로직
# 뒷 부분을 삭제할 때는 tail 포인터를 활용하는데
# 왜 left.left의 값을 넣어주는지 궁금함
self._del(self.tail.left.left)
💻 원형 데크 데이터 상태 확인 및 판별
def getFront(self):
"""
:rtype: int
맨 앞의 값 반환
"""
return self.head.right.val if self.length else -1
def getRear(self):
"""
:rtype: int
맨 뒤 값 반환
"""
return self.tail.left.val if self.length else -1
def isEmpty(self):
"""
:rtype: bool
데크 자료구조의 값이 비어 있는지 판별
"""
return self.length == 0
def isFull(self):
"""
:rtype: bool
데크 자료구조의 값이 가득 차 있는지 판별
"""
return self.length == self.maxlen
