[알고리즘] Queue

 

 

Queue

---

Queue는 stack과 같이 선형 자료구조 중 하나이며 대표적인 자료구조이다. 선형구조는 '자료가 일렬로 존재하는 구조'를 뜻한다. 예를들면 stack, queue, linked list 등이 있다. Queue에서 꼭 알아야할 개념은 FIFO이다. FIFIO는 First in First out이며 '가장 먼저 들어간 값이 가장 먼저 나간다'라는 의미이다. 즉 우리가 일반적으로 비행기 탑승게이트에서 줄을 서게 되면 먼서 줄선 사람이 먼저 비행기에 탑승할 수 있는 것과 동일하다. 

그림을 보면 알 수 있듯이 '앞'에 인는 정보가 추출이 되고 삽입되는 정보는 '뒤'에 쌓이는 것을 알 수 있다. 프로그래밍에서 사용될때는 보통 프린터 버퍼나 영상 버퍼와 같은 '버퍼'를 구현할때도 사용하고, 시뮬레이션을 진행할때도 사용한다. 필자는 프로젝트를 진행하면서 M/G/1 Queueing 모델을 사용하여 traffic 발생량 simulator를 개발해보기도 하였다.

 

알고리즘에서 Queue로 풀 수 있는 문제는 일반적으로 데이터의 입력이 순서대로 이루어지고, 출력도 입력된 순서대로 이루어지는 경우가 대표적이다. 즉 큐에 들어가면 언제 나올지는 모르지만 언젠가는 추출되게 되고 추출되는 순서가 입력 순서와 동일하다면 큐를 사용하여 해결할 수 있는 문제이다. 

 

 

Keywords

---

FIFO	First in First out
Enqueue	Queue에서 데이터를 삽입하는 명령어 (가장 뒤에 삽입됨)
Dequeue	Queue에서 데이터를 추출하는 명령어 (가장 앞에서 추출)
peek	Queue에서 가장 앞에 있는 데이터를 반환
isEmpty	Queue가 비어있을때는 true, 아니면 false를 반환
overflow	Queue가 꽉 차서 더 이상 데이터를 넣을 수 없는 상태
underflow	Queue가 비어서 더 이상 데이터를 추출할 수 없는 상태

* 추출은 자료구조에서 데이터를 제거 후 반환하는 것을 의미

* 반환은 자료구조에서 데이터를 제거하지 않고 값만 반환하는 것을 의미

 

 

Implementation

---

Queue는 대표적인 자료구조이기 때문에 대부분의 프로그래밍 언어에서 기본 라이브러리로 제공한다. Python3에서는 queue 모듈을 사용할 수도 있고, 그냥 list 자체에서도 사용할 수 있다.

from queue import Queue
q = Queue()
q.put(3)
q.put(2)
q.put(1)
print(q.get())
print(q.get())

queue = []
queue.append(1)
queue.append(2)
queue.append(3)

print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

위 처럼 사용할 수 있다. Queue 라이브러리를 사용해도 되고, 파이썬의 내장 라이브러리인 리스트를 사용해도 된다. 개인적으로 리스트를 사용해서 푸는게 좀더 편하다? 라는 느낌이 있다. Java도 마찬가지로 java.utils.Queue 라이브러리를 통해서 Queue를 구현할 수 있다. Java에서는 Generic으로 타입을 고정해서 queue를 사용할 수 있다. 

C#의 경우도 System.Collections.Generic에 Queue<T>가 따로 구현되어 있기 때문에 여기서 가져다가 쓰면 된다.