3-3 덱

 

덱 = 스택 + 큐이다! 스택과 큐를 잠깐 복습하고 보는 것을 추천한다.

3-1. 스택

 

3-2. 큐

 

1. 덱

 위에서 썼듯 덱은 스택과 큐를 합쳐놓은 듯한 자료구조이다. 즉, LIFO형식과 FIFO 방식이 모두 적용되는 자료구조이다. 덱(Deque)은 큐의 양쪽 끝에서 자료를 넣거나 뺄 수 있는 구조로, Double-ended Queue라고도 한다.

덱

2. 덱 기본 연산

Operation	Comment
D.add_first(e)	front에 새로운 요소를 추가
D.add_last(e)	back에 새로운 요소를 추가
D.delete_first()	- 첫 번째 요소를 제거하고 반환 - 단, 덱이 비어 있으면 error 생성
D.delete_last()	- 마지막 요소를 제거하고 반환 - 단, 덱이 비어 있으면 error 생성
D.first()	- 첫 번째 요소 반환 (단, 요소를 제거하지는 않음) - 덱이 비어 있으면 error 생성
D.last()	- 마지막 요소 반환 (단, 요소를 제거하지는 않음) - 덱이 비어 있으면 error 생성
D.is_empty()	덱이 비어 있으면 True를 반환
len(D)	덱에 저장된 요소의 개수를 반환

 

3. 원형 배열 기반의 덱 구현

• 변수는 큐와 동일하게: _data, _size and _front
• 처음과 끝의 index 계산 시에는 mod 연산

# delete_last()
back = (self._front + self._size -1) % len(self._data)


# add_first()
self.front = (self._front -1) % len(self._data)

• ArrayDeque.add_last: ArrayQueue.enqueue와 동일
• ArrayDeque.delete_first: ArrayQueue.dequeue와 동일

4. 기본 연산 성능 분석

 리스트로 덱을 구현하면 모든 연산이 O(1) 시간 복잡도를 갖는다.

Operation	Running Time(amortized)
D.add_first(e)	O(1)
D.add_last(e)	O(1)
D.delete_first()	O(1)
D.delete_last()	O(1)
D.first()	O(1)
D.last()	O(1)
D.is empty()	O(1)
len(D)	O(1)

 

5. 파이썬에서의 덱

 Python에서 덱은 collections.deque로 제공된다. 이는 리스트와 일관성을 갖고 있다.

• append, pop과 같은 이름을 갖는다.

Our Deque	collections.deque	Description
len(D)	len(D)	요소 개수
D.add_first()	D.appendleft()	front에 추가
D.add_last(e)	D.append()	back에 추가
D.delete_first()	D.popleft()	front에서 삭제
D.delete_last()	D.pop()	back에서 삭제

• 인덱스 접근이 가능하다.

Our Deque	collections.deque	Description
D.first	D[0]	첫 번째 요소 반환
D.last	D[-1]	마지막 요소 반환

• 임의의 요소에 접근이 가능하다.

Our Deque	collections.deque	Description
	D[j]	인덱스 i번째 요소 반환
	D[j] = val	인덱스 i번째 요소 수정
	D.clear()	모든 요소를 삭제
	D.rotate(k)	오른쪽으로 k번 원형으로 이동(Circular shift)
	D.remove(e)	첫번째 매칭되는 e를 삭제
	D.count(e)	e에 매칭되는 개수 반환

 

파이썬에선 덱을 고정 길이로 만들 수 있다. 이 경우 덱이 다 찼을 때 한쪽에서 append를 하면 다른 쪽에서 밀려 나간다. 즉, append를 하면 자동으로 leftpop이 되고 반대로 appendleft를 하면 내부적으로 pop이 된다.

고정 길이 덱 append

 파이썬에서 덱은 하이브리드 방식을 취한다. 이 말은 외형상 원형 배열(Circular Array)의 특징을 갖지만 내부적으로는 양방향 연결 리스트(Doubly Linked List)로 구현되어 있다는 의미이다.

• 양끝 연산의 경우: O(1)

Operation	Running Time
len(D)	O(1)
D.appendleft()	O(1)
D.append()	O(1)
D.popleft()	O(1)
D.pop()	O(1)
D[0]	O(1)
D[-1]	O(1)

• 임의의 요소에 접근할 경우: O(n)

Operation	Running Time
D[j]	O(n)
D[j] = val	O(n)
D.clear()	O(n)
D.rotate(k)	O(n)
D.remove(e)	O(n)
D.count(e)	O(n)

 

다음 게시물부터 연결 리스트에 대해 다룬다!