Queue와 Priority Queue란?

📌 Queue란?

큐(Queue): 데이터를 임시 저장하는 자료구조로, 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)구조이다.

• 스택(Stack): 큐와 같이 데이터를 임시 저장하는 자료구조로, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 후입선출(LIFO)구조이다.

큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 반대로 큐에서 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다.

큐에서 데이터를 넣는 쪽을 리어(rear)라 하고, 반대로 큐에서 데이터를 꺼내는 쪽을 프런트(front)라고 한다.

 

큐의 가장 큰 특징은 선입선출(FIFO)의 구조를 띄고 있다는 점과 너비 우선 탐색(BFS)에서 자주 사용된다는 점이다. 

[ 그림 1. 큐(Queue)의 FIFO ]

---

📌 OS scheduler와 Queue

OS에서 프로세스를 스케줄링하기 위해 Queue가 사용되며, 크게 3개의 Queue가 있다.

1. 작업 큐(Job Queue): 보조 기억 장치에 있는 프로세스가 주 메모리로 적재되기 위해 보조 기억 장치에서 주 메모리의 할당 순서를 기다리는 큐
2. 준비 큐(Readey Queue): 메모리 내에 있으면서 CPU를 할당받기 위해 기다리고 있는 프로세스들이 모여있는 큐. 즉, CPU 점유 순서를 기다리는 큐
3. 장치 큐(Device Queue): I/O 작업을 위해 대기하고 있는 프로세스들의 집합을 말한다.  I/O 작업을 위한 여러 장치들이 있는데, 각 장치를 기다리고 있는 큐가 존재한다.

3개의 큐는 각각의 스케줄러가 존재한다.

1. 작업 큐(Job Queue) - Job Scheduler(Long-term scheduler)
   • 장기 스케줄러(long-term scheduler)는 보조 기억 장치에 존재하는 프로세스들 중 어떤 프로세스를 주 메모리로 적재할지 결정하는 역할을 한다. 오늘날 시분할 시스템에서 사용되는 OS는 통상적으로 장기 스케줄러를 두지 않는다.
2. 준비 큐(Ready Queue) - CPU Scheduler(Short-term scheduler)
   • 단기 스케줄러(short-term scheduler)는 현재 메모리에 올라와있는 프로세스 중 어떤 프로세스가 CPU 점유권을 가질지 결정해주는 역할을 한다.
3. 장치 큐(Device Queue) - Device Scheduler

---

📌 Python과 Queue

파이썬에서 큐를 사용하는 방법은 크게 3가지가 있다.

1. 파이썬의 list
   • list의 append()와 pop(0)를 활용하여 큐를 구현할 수 있다.
2. 파이썬의 queue 모듈의 queue (from queue import queue)
   • queue 의 put()과 get()을 활용하여 큐를 구현할 수 있다.
   • queue는 list와 deque와는 다르게 인덱스로 데이터를 접근하는 것을 지원하지 않는다.
3. 파이썬의 collections 모듈의 deque (from collections import deque)
   • deque(= double-ended queue)는 맨 앞과 맨 끝 양쪽에서 데이터를 모두 삽입, 삭제할 수 있는 자료구조이다.
   • deque는 양쪽에서 삽입, 삭제할 수 있으며 간단하게 큐와 스택을 합친 형태라고도 볼 수 있다.
   • deque의 가장 큰 특징은 popleft()를 제공한다는 점인데, 이는 list의 pop(0)을 통해 나오는 결과와 같다.

추가로 파이썬에서는 queue 모듈의 LifoQueue (from queue import LifoQueue)가 있는데, 이는 후입선출(LIFO)로 되어 있으며 put()을 사용하여 요소를 넣고, get()을 사용하여 요소를 제거할 수 있다. get()을 사용할 경우, 후입선출 구조이기 때문에 가장 마지막에 추가된 요소가 제거된다.

---

📌 Priority Queue란?

우선순위 큐(Priority Queue): 데이터가 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조

일반적인 큐(Queue)는 선입선출(FIFO)구조이지만, 우선순위 큐(Priority Queue)는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.

 

우선순위 큐의 구현 방식은 배열, 연결리스트, 힙이 있다. 이 중에서 힙 방식이 최악의 경우여도 시간복잡도 O(logn)을 보장하기 때문에 일반적으로 힙을 갖고 구현을 한다.

---

📌 Python과 Priority Queue

파이썬에서 우선순위 큐를 사용하는 방법은 크게 2가지가 있다.

1. 파이썬의 queue 모듈의 PriorityQueue (from queue import PriorityQueue)
   • PriorityQueue의 put()과 get() 함수를 활용하여 우선순위 큐를 구현할 수 있다.
   • 요소를 저장할 때 우선순위를 지정하고 싶을 경우, put(우선순위, 요소)를 활용하여 구현할 수 있다.
2. 파이썬의 heapq 모듈
   • heapq 모듈의 heappush()와 heappop()을 활용하여 우선순위 큐를 구현할 수 있다.

---

출처:

1. https://dkwjdi.tistory.com/241 

스케줄러 (scheduler) + Job,Ready,Device Queue란?

2. https://www.daleseo.com/python-queue/

파이썬에서 큐(queue) 자료 구조 사용하기

3. https://yoongrammer.tistory.com/81

[자료구조] 우선순위 큐 (Priority Queue) 개념 및 구현

4. https://www.daleseo.com/python-priority-queue/

파이썬의 우선순위 큐(PriorityQueue) 사용법

5. https://product.kyobobook.co.kr/detail/S000001817975

Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편 | 시바타 보요 - 교보문고