[Algorithm] 큐, 덱

* Python을 기준으로 합니다

---

큐 (Queue), 덱 (Deque)

- 개념

• 큐 : FIFO (First In First Out) 형태의 자료구조
  • 처리해야 하는 작업들을 큐에 쌓음으로써 쉽게 처리할 수 있음
  • 스택과 마찬가지로 삽입과 삭제를 핵심적인 연산으로 가짐
    - 배열에서 `append()`나 `pop(0)`를 통해 삽입/삭제를 수행할 수 있지만, `pop(0)`는 $O(n)$을 소모함
    - 따라서 큐는 연결 리스트를 통해 구현하는 것이 좋음
  • 큐의 주요 연산
    1. `enqueue()` : 큐의 맨 마지막에 새로운 요소를 추가
    2. `dequeue()` : 큐의 첫 번째 요소를 pop()
    3. `isEmpty()` : 큐가 비어있으면 `True` 아니면 `False`

선형 큐와 원형 큐

• 원형 큐 (Circular Queue)
  • 선형 큐(Linear Queue)는 큐가 가득 찬 상태에서 front의 삭제가 발생해도 rear에 새로운 데이터를 삽입할 수 없음
    - 결과적으로 메모리 낭비가 발생하고, 삽입을 위해서는 기존 큐의 요소들을 앞으로 이동시켜야 함
  • 이를 방지하기 위해 front와 rear를 연결한 원형 큐를 사용함
    - 큐가 가득 찬 상태에서도 가장 오래된 데이터를 삭제해 큐의 메모리 낭비 없이 포화 상태를 유지할 수 있음
  • 이때 실제 데이터를 원형으로 옮기는 것이 아니라 index (front/rear)를 이동시켜 동작
    - $\textrm{front} \leftarrow \textrm{(front+1) % size}$
    - $\textrm{rear} \leftarrow \textrm{(rear+1) % size}$

선형 큐의 비효율성

• 덱 : front와 rear 양쪽에서 삽입과 삭제가 가능한 일반화된 형태의 큐
  • 덱은 일반적으로 이중 연결 리스트를 사용하여 구현함
  • 큐와 덱은 구조적으로 거의 동일하기 때문에, 원형 큐와 마찬가지로 원형 덱 형태로 구현하는 것이 좋음
    - $\textrm{front} \leftarrow \mathrm{(front-1+size) % size}$
    - $\textrm{rear} \leftarrow \mathrm{(rear-1+size) % size}$
  • 덱의 주요 연산
    1. `addFront()`, `deleteFront()` : front에서 삽입, 삭제
    2. `addRear()`, `deleteRear()` : rear에서 삽입, 삭제
    3. `isEmpty()` : 덱이 비어있으면 `True` 아니면 `False`

- 구현

1. collections의 deque 모듈을 통한 큐의 구현

• 일반적으로 `collections`에서 `deque`를 import 하여 사용 (큐와 덱을 함께 지원함)
  • `append()` : 오른쪽에 삽입
  • `appendleft()` : 왼쪽에 삽입
  • `pop()` : 오른쪽에서 요소를 제거하고, 해당 요소를 반환
  • `popleft()` : 왼쪽에서 요소를 제거하고, 해당 요소를 반환
  • `rotate()` : n 만큼 오른쪽으로 회전, 음수면 왼쪽 회전
  • `clear()` : 큐 초기화
  • `count()` : 일치하는 요소의 개수를 반환

import collections

queue = collections.deque() #큐 선언

queue.append(1)
queue.append(2)
queue.append(3)
print(queue) #[1,2,3]

queue.popleft()
print(queue) #[1,2]

2. queue의 Queue 모듈을 통한 큐의 구현

• `queue`를 import 하여 사용할 수 있지만, 해당 라이브러리는 멀티 스레드를 지원하는 것이 목적이기 때문에 `collections`를 사용하는 것이 좀 더 효율적임
  • `put()` : 큐에 데이터 삽입
  • `get()` : 큐에서 데이터 삭제
  • `empty()` : 큐 상태 확인

import queue

q = queue.Queue()

#삽입
q.put(1)
q.put(2)
q.put(3)

while not q.empty(): #큐가 빌 때까지
  print(q.get(), end=' ') #삭제

3. collections의 deque 모듈을 통한 덱의 구현

• 앞선 큐와 마찬가지로 collections에서 deque를 import 하여 사용
  
  • `appendleft()`, `append()` : 각각 덱의 왼쪽, 오른쪽 삽입
  • `popleft()`, `pop()` : 각각 덱의 왼쪽, 오른쪽 삭제

import collections

dq = collections.deque() #덱 생성

dq.append(1)
dq.appendleft(2)
dq.append(3)
dq.appendleft(4)
print(dq) #[4, 2, 1, 3]

print(dq.pop()) #3
print(dq.popleft()) #4

print(dq) #[2, 1]