덱이란 ?
양쪽에서 넣고 빼고가 가능한 특이한 큐를 의미
스택과 큐의 역할이 모두 가능한 큐를 말한다.
- Dequeue은 큐의 출력을 의미하기도 하지만, Double-ended Queue의 준말이기도 하다.
- pushBack, pushFront로 뒤/앞으로 넣을 수 있고, popBack, popFront로 뒤/앞에서 뺄 수 있다.
- 덱은 스택과 큐를 합쳐놓은것과 같다
- 큐 : pushFront + popBack 혹은 pushBack + popFront
- 스택 : pushFront + popFront 혹은 pushBack + popBack
Deque의 종류
스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
셀프(Shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱
특징
- 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 없다.
- 보통 두가지 이유 중 하나로 사용한다. (입력과 출력을 추가하는 방식으로 사용)
- 큐에서 양쪽에서 출력할 수 있어야하거나 (스크롤, scroll)
- 덱에 입력을 제한하는 경우
- 스택에서 양쪽에서 입력하고 싶은 경우 (셸프, shelf)
- 덱에 출력을 제한하는 경우
- 큐에서 양쪽에서 출력할 수 있어야하거나 (스크롤, scroll)
Dequeue의 용도
- 보통 스케줄링에 사용
- 스케줄링이 복잡해질수록 큐와 스택보다 덱이 더 효율이 잘 나오는 경우가 있음
- 우선순위를 조절하게 될 때
- 옛날에 있던걸 우선순위를 높이기 위해서는 앞에서 빼낼 수 있어야 되는데 스택에서는 불가능함
- 최근에 들어온걸 우선순위를 주고 싶은데 이 역시 큐의 구조에서는 불가능함
- 결국 앞뒤로 다 인출이 가능한 덱(Deque)만이 이 조건을 충족시킴
python collection 모듈
기본적인 deque 생성시에는 다음과 같은 형태로 생성
collections.deque([iterable[, maxlen]])
# deque 생성
import collections
basedata = ['a','b','c','d']
dequedata = collections.deque(basedata)
dequedata1 = collections.deque([1,2,3,4])
print(dequedata)
print(dequedata1)
-> 리스트 등과 같이 iterable 기반의 데이터를 인자로 받아 deque 생성
Deque 생성시 사이즈 고정하기
위에서 deque 생성시에 다음과 같이 maxlen을 인자로 추가할 수 있다.
이럴 경우 deque의 사이즈가 고정이 된다.
import collections
basedata = ['a','b','c','d']
dequedata = collections.deque(basedata, maxlen=3)
print(dequedata)
-> maxlen을 지정하면 데이터가 뒤에서부터 순차적으로 저장되고,
deque가 꽉 차면, 추가 입력데이터는 버려진다.
데이터 추가 / append, appendleft
리스트의 명령어와 같이 append를 이용해서 데이터를 하나씩 추가할 수 있습니다. appendleft의 경우 왼쪽에서 데이터를 추가할 수 있습니다.
import collections
basedata = ['a','b','c','d']
sampleData = ['z','k','e','r']
dequedata = collections.deque(basedata)
print("append example")
dequedata.append('e')
print(dequedata)
dequedata.appendleft('z')
print(dequedata)
데이터 추가(확장)/ extend, extendleft
기본 deque에 iterable 데이터를 합치는 명령어이다.
기본적으로 오른쪽 방향으로 합치고, extendleft의 경우은 왼쪽에 데이터를 합침
import collections
basedata = ['a','b','c','d']
sampleData = ['z','k','e','r']
print("extend example")
dequedata.extend(sampleData)
print(dequedata)
dequedata = collections.deque(basedata) # deque 새로 생성
dequedata.extendleft(sampleData)
print(dequedata)
데이터 반환 / Pop, Popleft
pop의 경우는 데이터를 하나씩 반환하고, 기존 큐에서 삭제하는 명령어이다.
popleft의 경우는 왼쪽 방향에서 데이터를 반환하고 삭제하는 명령어이다.
import collections
basedata = ['a','b','c','d']
dequedata = collections.deque(basedata)
print("pop/popleft example")
dequedata.pop()
print(dequedata)
dequedata.popleft()
print(dequedata)
데이터 삭제/remove, clear
remove의 경우 인자로 넣은 데이터를 deque에서 삭제하는 명령어이다.
clear의 경우는 deque안의 모든 맴버를 삭제한다.
import collections
basedata = ['a','b','c','d']
dequedata = collections.deque(basedata)
print("remove, clear example")
dequedata.remove('a')
print(dequedata)
dequedata.clear()
print(dequedata)
데이터 값 위치 바꾸기/reverse, rotate
reverse의 경우 데이터를 뒤집어 버립니다. 그냥 데이터를 통째로 뒤집어 버린다.
그리고 rotate 명령어는 가장 오른쪽 데이터를 pop해서 appendleft한다.
이런식으로 데이터를 하나씩 순회하게 한다.
만약 인자로 들어간 숫만큼 회전을 한다.
import collections
basedata = ['a','b','c','d']
dequedata = collections.deque(basedata)
print("reverse, rotate example")
dequedata.reverse()
print(dequedata)
dequedata.rotate()
print(dequedata)
dequedata.rotate(2)
print(dequedata)
