큐 개념잡기
큐는 '줄서기'와 같다고 정의할 수 있다.
또, 다른 말로는 '대기 행렬'이라고도 한다.
'선입선출(FIFO)' 특징을 가지고 있기 때문이다.
큐의 의미가 현실에 반영된 것이 뭐가 있을까 생각해보니 자판기가 떠올랐다.
자판기를 채울 때 음료가 나오는 입구의 반대 방향에서부터 음료를 채운다.
그리고 음료를 꺼낼 땐 버튼을 눌러서 꺼내게 되는데,
반대 방향에서 음료를 채워넣었으니까 제일 처음 채워 넣은 음료가 제일 먼저 나온다.
이것이 선입선출의 개념이다.
이처럼 음료를 채우는 액션을 '인큐'라고 부르고,
음료를 꺼내는 액션은 '디큐'라고 부른다.
결국엔 인큐는 데이터를 추가하는 작업이고, 디큐는 데이터를 꺼내는 작업이라고 볼 수 있다.
큐 개념 형상화
자판기 말고 또 어떤 케이스가 큐에서 사용되는지 알아보자.
프린트 작업 대기열
문서 10개에 대해 프린트 요청을 했다고 가정한다.
프린터는 한 번에 1장씩만 출력할 수 있으니 요청이 들어오는데로 순서를 매길 것이다.
그것이 바로 대기열의 개념이고, 대기열에 쌓여있는 요청들을 요청한 순서대로 프린트 처리한다.
서버 요청 처리
티켓팅 사이트를 개발했다고 가정해보자. 티켓의 수는 한정되어 있을 것이다.
요청 순서를 무시하고 랜덤으로 처리하면 형평성이 어긋난다.
때문에 요청 경로를 통해 들어온 순서대로 대기열에 쌓아두고, 응답은 요청한 순서대로 처리해주어야한다.
Python에서 큐 사용하기
파이썬에서 큐를 사용하는 방법을 크게 2가지로 나누었다.
하나는 queue module을 사용하는 방식이고,
또 하나는 collections.deque를 사용하는 방식이다.
현재는 algorithm 문제 풀기를 위한 기초 개념을 공부중이기 때문에,
deque를 중점적으로 알아볼 예정이다.
algorithm 문제 풀 때는 멀티스레드가 필요없기 때문에 , 일반적으로는 duque를 사용해서 queue를 구현한다.
queue module은 종류가 여러가지이고,
구현하려는 기능에 맞는 module을 상황에 맞게 선택하면 된다.
queue module을 사용할 때는 멀티 스레딩 환경
즉, 동시에 같은 데이터에 접근하는 케이스일 경우 에러가 발생할 수 있다.
이와 같은 상황을 방지하기 위해 '락'을 거는 개념이 포함된다.
deque는 '락'이라는 개념이 없다.
그렇기 때문에 안정성은 보장하지 못하지만 처리 속도가 매우 빠르다.
그래서 algorithm 문제 풀이 시 deque를 많이 사용한다.
deque 예제로 이해하기
deque는 양쪽 입구가 열려있는 자료구조이다.
그래서 아래 예제처럼 append랑 popleft를 쓰면 queue처럼 동작 시킬 수 있다.
from collections import deque
q = deque()
q.append("A")
q.append("B")
q.append("C")
print(q.popleft()) # A
print(q.popleft()) # B
print(q.popleft()) # Cdeque를 사용하기 위해 import 해주고,
q라는 변수에 대기줄([])을 하나 만들어준다.
이제 q라는 배열에 A, B, C append 한다.
q가 왼쪽부터 시작해서 오른쪽([A, B, C]) 방향으로 채워진다.
데이터를 꺼내줄때는 선입선출을 해야하니, popleft를 사용한다.
왼쪽에서부터 시작했기 때문에 왼쪽에서부터 꺼내준다는 의미이다.
앞서 말했듯이 deque는 양방향 자료구조이기 때문에
데이터 꺼내는 방향만 바꾸면 stack으로도 활용 가능하다.
stack으로 사용하려면 아래와 같이 pop으로 데이터를 빼내주면 된다.
from collections import deque
s = deque()
s.append("A")
s.append("B")
s.append("C")
print(s.popleft()) # C
print(s.popleft()) # B
print(s.popleft()) # A