대학생 쩡딱구리
3-3 덱 본문
덱 = 스택 + 큐이다! 스택과 큐를 잠깐 복습하고 보는 것을 추천한다.
3-1. 스택
1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되고(push), �
jjeongttakgoori.tistory.com
3-2. 큐
3-1. 스택 1. 스택이란? 스택(Stack)이란 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조이다. 스택은 LIFO(Last In First Out) 형태의 자료구조로, 가장 최근에 저장된 값 다음에 자료가 저장되
jjeongttakgoori.tistory.com
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이 된다.
파이썬에서 덱은 하이브리드 방식을 취한다. 이 말은 외형상 원형 배열(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) |
다음 게시물부터 연결 리스트에 대해 다룬다!
'STUDIES > DATA STRUCTURE' 카테고리의 다른 글
| 4-2. 연결 리스트로 스택, 큐 구현하기 (0) | 2020.10.21 |
|---|---|
| 4-1. 한방향 연결 리스트 (0) | 2020.10.19 |
| 3-2. 큐 (0) | 2020.10.17 |
| 3-1. 스택 (0) | 2020.10.17 |
| 2-3. 분할 분석과 성능 분석 (0) | 2020.10.16 |