[자료구조]큐(Queue)에 대한 모든 것-개념,사용예시, 파이썬 내장 함수

안녕하세요. 진또배기 입니다. 오늘은 저번 스택 자료구조에 이어서 큐에 대해 알아보겠습니다. 

저번에 설명한 스택 개념과 이번에 설명드릴 큐 개념을 동시에 가져가시는 것을 추천드립니다.

 

---

1. 큐(Queue)란?

큐는 '밑빠진 독에 물붓기'와 같습니다. 밑빠진 독에 물을 붓는 것처럼 가장 먼저 들어간 물이 가장 먼저 나오는 것입니다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 처리되는 자료구조입니다. 

이 규칙을 FIFO 규칙으로 불리며 First-in First-out의 줄임말입니다.

이를 그림으로 표현하면 

큐 설명 그림1

이와 같은데요. 큐를 다른 말로 하면 가장 나중에 들어간 데이터가 가장 나중에 처리되는 자료구조입니다.

Queue를 영어로 직역하면 '열'이라는 뜻인데 왜 이 뜻인지는 이제 이해하시겠죠?

 

2. 큐 사용예시

큐는 정말 다양한 곳에서 쓰입니다. 큐가 쓰이는 곳에는 가장 먼저 들어간 것이 가장 먼저 처리되는 영역에서 쓰이겠죠?

예를 들면, 프린터에서 인쇄물이 차례대로 나올 수 있도록 프린터 인쇄 대기열이나 콜센터에서의 전화선 고객 대기열에서 쓰입니다. 또는 스마트 팩토리에서도 쓰일 수 있는데요. 모든 재화는 조립 공정이라는 것이 존재합니다.

예를 들면, 자동차 공장에서 바퀴를 조립할 때, 축위에 --> 디스크를 얹고 --> 그 위에 휠을 얹고--> 그 위에 허브를 얹습니다. 만약 이 순서가 틀어지게 된다면 튼튼하지 못한 바퀴가 생산됩니다.

 

3. 파이썬에서의 큐 활용

파이썬에서 스택은 지원하지 않지만 큐는 지원을 합니다. 큐를 사용하는 방식에는 두 가지가 있습니다.

하나는 Collections 모듈의 deque객체를 이용하는 방법이고 다른 하나는 Queue 클래스를 이용하는 방법입니다.

차례대로 사용하는 함수와 예시를 나열하겠습니다.

 

1) collections 모듈의 deque 객체 이용하는 방법

0. 모듈 불러오기
from collections import deque
1. 큐 생성(초기화)
listA=[1,2,3]
deque(listA,maxlen=5) #초기화 함수입니다. iterable(리스트 등)을 인자로 건네면 이를 deque화 해줍니다
- 빈 큐 만들기
deque1 = deque()
- 원소가 있는 큐 만들기
deque2 = deque([1, 2, 3])
- 큐 최대 길이 명시하기(원소 수가 maxlen에 도달했을 때 새로운 값을 넣으면, 앞서 넣은 값은 사라집니다
그리고 pop이 일어난 뒤 뒤에 새 값이 들어갑니다)
만약 다음과 같은 큐를 생성해주었다면,
deque3 = deque(maxlen=5)
deque3.append(1)
deque3.append(2)
deque3.append(3)
deque3.append(4)
deque3.append(5)
deque3
---------------------------------
>>> deque([1, 2, 3, 4, 5])
deque3.append(6)
deque3
>>> deque([2, 3, 4, 5, 6])
와 같은 결과가 나오게 됩니다.

2. 큐 원소제거 my_deque.popleft() , clear()
my_deque = deque([1,2,3])
my_deque.popleft()
>>> 1
my_deque
>>> deque([2,3])

3. 큐에 원소추가 
my_deque.append(x) : x를 큐의 오른쪽에 삽입합니다.

4. 인덱스 접근
my_queue[0]과 같은 것이 가능합니다.

그리고 힙정렬은 나중에 포스팅할 내용인데요. 이해가 안되어도 힙정렬에 대해 배운 뒤 개념을 가져가시길 추천합니다.

5. deque를 사용해 힙정렬을 할 수 없다!
reqs = [[1, 7], [4, 1], [5, 2], [3, 1], [7, 2]]
q=deque(reqs)
heapq.heapify(q)
-------------------------------------
오류: heap module must be a list

2) Queue 모듈의 Queue 클래스 이용하는 방법

파이썬에서는 Queue 클래스가 존재해 다양한 함수를 지원합니다.

하지만

deque(listA,maxlen=5)

처럼 Queue에는 원소 N개를 한 번에 넣는 방법은 없습니다. 이때에는 데이터 수만큼 삽입 연산을 호출해주셔야 합니다.

0. 모듈 불러오기
from queue import Queue				

1. 빈 큐 생성						
empty_queue = Queue()						
empty_queue	
							            
2. 큐에 원소추가.
my_queue = Queue()
my_queue.put(3)
my_queue.queue
>>> deque([3])

데이터를 가져올 때는 get()메소드를 사용합니다. get()메소드를 사용하면 해당 데이터는 큐에서 제거됩니다.

즉, 큐에서 원소를 제거하고 제거한 원소를 리턴합니다.

그런데 만약,

put을 할때 큐가 꽉차있다면 (queue overflow)가 발생하고

get을 할 때 큐가 비어있다면 (queue underflow)가 발생합니다.

해당 프로세스는 큐에서 데이터가 빠지거나 들어올때까지 영원히 대기하게 됩니다.(데드락)

이는 put과 get함수가 기본적으로 blocking 함수이기 때문인데,

이를 방지하기 위해서는 다음과 같이 put_nowait 함수와 get_nowait 함수를 사용하면 됩니다.

3. get_nowait()
my_queue = Queue()
my_queue.put(3)
my_queue.put(4)
my_queue.put(5)
front = my_queue.get_nowait()
print(front)
my_queue.queue
>>> 3
>>> deque([4,5])

현재 큐에 들은 원소의 수를 알아낼 때에는 qsize 메소드를 사용합니다.

4. 큐 사이즈
from queue import Queue
my_queue = Queue()
for val in range(5):
    my_queue.put(val)
    print('큐 크기:', my_queue.qsize())
>>> 큐 크기: 1
>>> 큐 크기: 2
>>> 큐 크기: 3
>>> 큐 크기: 4
>>> 큐 크기: 5

큐에 대한 활용 함수는 여기까지 하겠습니다.

오늘은 큐라는 자료구조에 대해 알아보았습니다.

 

진또배기기 올림