큐의 개념
큐(queue)는 차례를 기다리는 줄이라는 의미를 가지고 있는 단어처럼 먼저 들어온 자료부터 순서대로 처리하는 방식을 말한다.
한 쪽 끝에서는 자료의 삽입 연산만 가능하고 반대쪽 끝에서는 삭제만 가능한 구조로서 선입선출(FIFO : First In First Out)의 특징을 가진다.
위의 사진과 같이 앞(front)에서는 삭제만 일어나고, 뒤(rear)에서는 삽입만 일어난다.
실생활의 예시로는 은행 대기 줄, 에스컬레이터, 작업 큐, 프린터 인쇄 처리 방식 등이 있다.
큐의 종류
큐는 일반적으로 배열이나 연결 리스트(Linked List)를 이용한다. 배열을 이용할 경우 쉽게 구현이 가능한데 구현 형태에 따라 선형 큐, 원형 큐 등으로 나뉜다.
1) 선형 큐
선형 큐는 배열을 선형으로 나타낸 형태이다. 자료의 삽입이나 삭제가 용이하나 큐에 빈 자리가 있어도 포화 상태로 인식하는 경우가 있어 빈 자리를 따로 정리 과정을 거쳐야 한다는 단점이 있다.
예시는 아래의 그림과 같은 구조를 생각하면 좋다.
2) 원형 큐
배열을 원형의 모습으로 표현한 것으로 논리적으로 배열의 처음과 끝을 연결한 형태이다. 자리를 이동시킬 필요가 없어 실용적인 특징을 가지고 있다.
원형 큐에서는 초기 공백 상태에서 front와 rear의 값을 0으로 하고 공백 상태와 포화 상태를 구분하기 위해 자리를 비워둔다. 자료를 삽일할 경우 rear의 위치를 한 칸 앞으로 옮기고 그곳에 자료를 삽입한다. 따라서 front가 지정하는 위치는 항상 비워진 상태로 유지된다.
큐의 연산
앞서 스택에서 고려하였던 것과 같이 크기가 3인 선형 큐와 원형 큐에 각각 원소 A, B를 각각 삽입하고 원소 1개를 삭제한 후 원소 C를 삽입하는 과정에 대해 고려해 보자.
해당 과정을 순서대로 정리하면 아래와 같다.
- 크기가 3인 공백 큐를 생성한다.
- 원소 A를 삽입한다.
- 원소 B를 삽입한다.
- 원소 1개를 삭제한다.
- 원소 C를 삽입한다.
1) 선형 큐
이를 그림으로 나타내면 아래와 같다.
1. 크기가 3인 공백 선형 큐를 생성
2. 원소 A 삽입
3. 원소 B 삽입
4. 원소 1개 삭제
5. 원소 C 삽입
2) 원형 큐
동일한 과정을 거친다고 가정 후 이를 그림으로 나타내면 아래와 같다.
1. 크기가 3인 공백 원형 큐 생성
여기서 공백 상태와 포화 상태를 구분하기 위해 front가 있는 자리 하나를 항상 비워두므로 크기가 3이지만 실제 배열에서는 크기가 4인 배열을 생성한다.
2. 원소 A 삽입
3. 원소 B 삽입
4. 원소 삭제
5. 원소 C 삽입
다음 시간에는 선형 큐와 원형 큐를 C언어 상에서 구현해 보는 연습을 할 것이다.
참고
정관용, 임종범, 박병기, 복대원. (2013). 고등학교 정보과학 (pp. 196-200). 서울: (주)현대아트컴.
