[파이썬] 스택/큐 - deque ( from collections import deque )

Deque란

• 주로 큐 구현에 사용
• Deque는 double-ended queue 의 줄임말로, 앞과 뒤에서 즉, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조를 의미한다. 스택과 큐의 기능을 모두 가졌다.

+ 스택(Stack)

• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조(LIFO) -> 오른쪽 끝에서 입출력
• 리스트 사용해 append(), pop() 사용

stack = [1,2,3]

# 원소 추가
stack.append(4) 
stack
>>> [1, 2, 3, 4]

# 가장 마지막 원소 삭제 후 그 값 리턴
top = stack.pop() 
print(top)
stack
>>> 4
>>> [1, 2, 3]

# 스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1] 사용
top = stack[-1] 
top
stack
>>> 3
>>> [1, 2, 3]

※ pop() : 맨 마지막 요소 삭제 / pop(x) : x번째 요소를 리턴 후 삭제 -> x는 인덱스임

 + list.remove('값') : 인덱스가 아니고 값임

 

 

+ 큐(Queue)

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조(FIFO) -> 오른쪽에 입력 왼쪽으로 출력
• deque를 사용해 append(), popleft() 사용
• 데이터를 입력된 순서대로 처리해야 할 때, BFS(너비 우선 탐색) 구현 할 때 사용

※ 스택과 달리 큐를 list로 이용하지 않는 이유

 스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다. 하지만 pop()의 시간복잡도는 O(1)인 반면 pop(0)의 시간복잡도는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

 

디큐 함수 ( from collections import deque)

• 스택 구현(오른쪽 끝에서 입출력) : append(), pop()
• 큐 구현 : appendleft(), pop(), append(), popleft()
• depue 확장하기 : extend(), extendleft()
• 리스트 처럼 수정 삭제 : insert(), remove()
• deque 내용 좌우로 반전 : reverse()
• 회전 : rotate(n)
• 모든 원소 제거 : clear()

from collections import deque # 모듈 임포트
queue = deque([4, 5, 6]) # 디큐 생성

# append(x) : 오른쪽(마지막)에 원소 추가(삽입)
queue.append(7)
queue.append(8)
print(queue)
>>> [4, 5, 6, 7, 8]

# popleft() : 왼쪽(앞쪽)부터 차례대로 제거와 반환
queue.popleft()
>>> 4
queue.popleft()
>>> 5
print(queue)
>>> [6, 7, 8]

# rotate(n) : 요소들을 값 만큼 회전 해주는 메소드
# 음수면 왼쪽으로, 양수면 오른쪽으로 회전
deq = deque(['a', 'b', 'c', 'd', 'e'])
deq.rotate(1)
>>> e a b c d

deq2 = deque(['a', 'b', 'c', 'd', 'e'])
deq3.rotate(-1)
>>> b c d e a

 

 

+ 스택/큐 관련 문제 정리  ( 프로그래머스 )

# 다리를 지나는 트럭 (Level2) : 2021.04.17 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 다리를 지나는 트럭 - deque

# 주식가격 (Level2) : 2021.03.31 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 주식가격

# 기능개발 (Level2) : 

# 프린터 (Level2) : 2021.04.15 - [알고리즘] - [ 프로그래머스 / 파이썬 ] 프린터 - deque