큐(Queue)

목차

1. 큐 란?
2. 큐의 특징
3. 큐의 연산
   3-1. front
   3-2. pop
   3-3. push
   3-4. empty
4. 큐 사용 예시

1. 큐 란?

양 끝에서 각각 입력과 출력을 담당하는 자료구조입니다.

2. 큐의 특징

자료의 입력과 삭제가 각기 다른 정해진 곳에서 일어나기 때문에 순차적으로 진행 됩니다.
즉,

선입선출(FIFO: First In Fisrt Out)의 현태를 가집니다.

'A', 'B', 'C', 'D','E'를 차례로 입력한 다음 'F'를 입력할 때의 모습입니다.
설명의 편의를 위해,
출력이 일어나는 끝을 '앞', 입력이 일어나는 끝을 '뒤'라고 가정하겠습니다.

3. 큐의 연산

3-1. front

지난 업로드(stack)에서는 top을 사용했습니다.
큐에서는 top대신 front라는 연산이 있습니다.
top과 마찬가지로 pop를 실행했을 시에 사라질 자료를 출력합니다.
하지만 stack과는 다르게 가장 먼저 입력된 자료를 출력하게 됩니다.

3-2. pop

큐의 pop은 가장 먼저 입력된 자료를 삭제합니다.

위의 설명은 pop을 진행한 후 'A'가 삭제된 뒤의 상황입니다.

3-3. push

입력을 할 때에 사용하는 연산자입니다.
앞서 설명들렸듯 입력은 '뒤'에서 발생합니다.
다음의 예시는 push('F')가 일어난 뒤의 상황입니다.

3-4. empty

stack에서의 설명과 동일합니다.
큐 안에 들어가있는 자료가 존재하지 않은체로 front나 pop일 실행되면 오류를 유발할 수 있기 때문에
이를 방지하기 위해 큐가 비어있는지 아닌지를 검사합니다.

4. 큐 사용 예시

1. 은행 대기 순번표
   은행 대기 순번표 뿐만 아니라 각종 대기열 등에서 주로 사용됩니다.
   특정 우선순위가 없는 이상 순서대로 입출력이 이루어지는 queue의 형태를 채용합니다.
2. 너비 우선 탐색(BFS: Breadth First Search)
   간단하게 설명하면
   그래프 안의 출발점 좌표를 큐에 추가합니다.
   큐의 프론트 좌표를 꺼낸 뒤에 해당 좌표에서 갈 수 있고, 방문한 적 없는 모든 좌표를 큐에 입력합니다.
   이러한 과정을 큐가 빌 때까지 합니다.
   이 과정은 후에 알고리즘을 올릴 때 좀 더 깊이 설명하도록 하겠습니다.