[자료구조] 큐(Queue) / python 데크(deque) 함수 정리

큐(Queue)란?

• 데이터의 순서가 중요한 상황에서 자주 사용되는 자료구조
• FIFO (First-In-First-Out) : 먼저 들어간 데이터가 먼저 나오는 구조. 선입선출
• 두 개의 끝점을 가짐
  • front : 요소가 제거되는 쪽
  • rear : 요소가 추가되는 쪽
• 줄 서기나 대기열과 같은 개념에서 유래됨
• 배열, 연결 리스트, 또는 데크(deque)로 구현할 수 있음

 

기본 동작

1. enqueue : 큐의 끝에 요소 추가
2. dequeue : 큐의 앞에서 요소 제거하고 반환

---

데크(Deque)란?

• 파이썬에서 구현된 큐 : collections 모듈에서 제공
• deque = Double-Ended Queue = 양방향 큐
  • 앞, 뒤 양쪽 방향에서 요소 추가 또는 제거 가능
• 양 끝 요소의 append와 pop 속도가 매우 빠름
  • 일반적인 리스트의 경우, 양 끝 요소에 접근하여 삽입 또는 제거시 O(n) 소요
  • 데크의 경우, 양 끝 요소에 접근하여 삽입 또는 제거시 O(1) 소요
• 다음과 같이 생성 가능

from collections import deque

deq = deque()

# 리스트를 전달하는 것도 가능하다.
a = [1,2,3,4]
deq = deque(a)

 

---

메서드 정리

요소 추가 및 제거

• append(x) : 'x'를 deque의 오른쪽 끝에 추가
• appendleft(x) : 'x'를 deque의 왼쪽 끝에 추가
• pop() : deque의 오른쪽 끝 요소를 제거하고 반환
• popleft() : deque의 왼쪽 끝 요소를 제거하고 반한

# append
d.append(4)  # d = deque([1, 2, 3, 4])

# appendleft
d.appendleft(0)  # d = deque([0, 1, 2, 3, 4])

# pop
d.pop()  # 반환: 4, d = deque([0, 1, 2, 3])

# popleft
d.popleft()  # 반환: 0, d = deque([1, 2, 3])

요소 삽입 및 제거

• insert(i, x) : 인덱스 i에 'x'를 삽입
• remove(value) : deque에서 첫 번째로 등장하는 value 제거

# insert
d.insert(1, 1.5)  # d = deque([1, 1.5, 2, 3])

# remove
d.remove(1.5)  # d = deque([1, 2, 3])

기타

• extend(iterable) : iterable의 모든 요소를 deque의 오른쪽 끝에 추가
• extendleft(iterable) : iterable의 모든 요소를 deque의 왼쪽 끝에 추가. iterable의 순서가 반대로 추가됨!
• rotate(n) : deque를 n만큼 회전시킴. 양수 값은 오른쪽, 음수 값은 왼쪽으로 회전시킴.
• clear() : deque의 모든 요소 제거
• count(value) : deque에서 value 개수 세기
• reverse() : deque의 요소 순서를 반대로 바꿈

# extend
d.extend([4, 5])  # d = deque([1, 2, 3, 4, 5])

# extendleft
d.extendleft([0, -1])  # d = deque([-1, 0, 1, 2, 3, 4, 5])

# rotate
d.rotate(1)  # d = deque([5, -1, 0, 1, 2, 3, 4])
d.rotate(-1)  # d = deque([-1, 0, 1, 2, 3, 4, 5])

# clear
d.clear()  # d = deque([])

# count
d = deque([1, 2, 3, 1, 2, 1])
d.count(1)  # 반환: 3

# reverse
d.reverse()  # d = deque([5, 4, 3, 2, 1])

 

rotate 함수를 알아두면 좋을 것 같다!