deque

• from collections import defaultdict 로 defaultdict를 사용한 적이 있다.

• 그것 처럼 deque 도, collections에서 가져온다.
  • list를 이용한 queue, stck를 써도 되지 않는가?

데크는 스택과 큐를 일반화 한 것입니다 (이름은 《deck》이라고 발음하며 《double-ended queue》의 약자입니다). 데크는 스레드 안전하고 메모리 효율적인 데크의 양쪽 끝에서의 추가(append)와 팝(pop)을 양쪽에서 거의 같은 $O(1)$ 성능으로 지원합니다.
출처: https://docs.python.org/ko/3.9/library/collections.html

• 즉, list를 queue 처럼 혹은 stack 처럼 사용하려고 append(x), insert(0,x) 하는 것은 $O(N)$ 이다.
• deque를 사용하면 $O(1)$ 이다.

---

deque 생성

1. deque 생성

from collections import deque

if __name__ == '__main__':
    dq=deque()

---

2. 기존 list -> deque

from collections import deque

if __name__ == '__main__':
    build=[3,2,1,3,4]
    
    dq=deque( build ) <- 기존 list인 'build'를 deque로 만듦

---

deque(maxlen=<int>)

• max값을 지정함
• max값이 다 차도, error를 내지 않고, append()시, index[0] 값을 빼고 append()한다.
  • appendleft()시, index[-1] 값을 빼고 appendleft()를 수행한다.
    

---

접근

print(dq[1]) <- 그냥 idx 넣어서 접근하면 됨

dq=deque()
dq.append(1)
dq.append(2)
print(dq[1]) # 2

• 그냥 list 처럼 idx 접근할 수 있다.

---

count(x): x 요소 수 셈

dq.count(3)

---

index(x[,s,e])

index(x[, start[, stop]])
데크에 있는 x의 위치를 반환합니다 (인덱스 start 또는 그 이후, 그리고 인덱스 stop 이전). 첫 번째 일치를 반환하거나 찾을 수 없으면 ValueError를 발생시킵니다.

---

빈요소 접근

• 만약 위 처럼 빈 데크에 접근했을 때, index out of range 에러가 발생한다.
  

---

deque append

append(x) = push

append(x)
데크의 오른쪽에 x를 추가합니다.

---

appendleft(x)

appendleft(x)
데크의 왼쪽에 x를 추가합니다.

insert(i, x)
x를 데크의 i 위치에 삽입합니다.

삽입으로 인해 제한된 길이의 데크가 maxlen 이상으로 커지면, IndexError가 발생합니다.

---

deque pop

pop() / popleft()

---

clear()

데크에서 모든 요소를 제거하고 길이가 0인 상태로 만듭니다.

---

copy()

copy()
데크의 얕은 복사본을 만듭니다.

버전 3.5에 추가.

---

count()

count(x)
x 와 같은 데크 요소의 수를 셉니다.

버전 3.2에 추가.

---

extend()

extend(iterable)
iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장합니다.

extendleft(iterable)
iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장합니다. 일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤집는 결과를 줍니다.

---

제거

remove(val)

value의 첫 번째 항목을 제거합니다. 찾을 수 없으면, ValueError를 발생시킵니다.

---

기타

reverse()

데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환합니다.

---

rotate()

• dq.rotate(n=1)
  deque를 오른쪽으로 n 번 회전한다.
  n이 음수면, 왼쪽으로 회전한다.
  데크가 비어 있지 않으면, 오른쪽으로 한 단계 회전하는 것은 d.appendleft(d.pop())과 동등하고, 왼쪽으로 한 단계 회전하는 것은 d.append(d.popleft())와 동등합니다.

데크 객체는 하나의 읽기 전용 어트리뷰트도 제공합니다:

---

count(val)

extend(iter)

• dq.extend(iterable)
  • iterable 인자에서 온 요소를 추가하여 데크의 오른쪽을 확장합니다.

extendleft(iter)

---

deque로 stack 사용

• 조건하에 싹 pop 해버림

---

스택의 종류

1. FA(Full Ascend)
   

• SP: 유효 value
• push 마다 SP 증가

---

2. FD(Full Descend)
   

• SP: 유효 value
• push 마다 SP 감소

---

3. ED(Empty Ascend)
   

• SP: 유효 value +1 pointer
• push 마다 SP 증가

---

4. ED(Empty Descend)
   

• SP: 유효 value -1 pointer
• push 마다 SP 감소