큐(Queue)의 추상 자료형

큐란?

입출력이 선입선출(First-In First-Out)인 자료구조.

삽입과 삭제가 같은 위치에서 일어나는 스택과 달리 큐는 삽입과 삭제가 다른 위치에서 일어나는데, 삽입이 일어나는 곳을 후단(rear), 삭제가 일어나는 곳을 전단(front)이라고 한다.

Untitled

큐의 추상 자료형

Untitled

큐의 활용

컴퓨터 장치들 사이에 데이터를 주고받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 큐가 사용되는데, 이것을 보통 버퍼(buffer)라고 한다. 대부분의 장치에서 발생하는 이벤트는 불규칙하지만, 이를 받아 처리하는 CPU는 일정한 처리 속도를 갖기 때문에 이 둘의 속도 차이를 버퍼를 사용하여 해결한다.

Untitled

큐의 구현

선형 큐

배열로 큐를 구현할 때는 크기가 정해진 배열과 삭제를 위한 변수 front, 삽입을 위한 변수 rear가 필요하다. front는 큐의 첫 번째 요소를 가리키고, rear는 큐의 마지막 요소를 가리킨다.

큐가 처음 생성되면 front와 rear의 초기값은 -1로 정해진다. enqueue를 통해 데이터가 삽입되면 먼저 rear를 하나 증가하고 그 위치에 데이터를 저장한다. 삭제 시에는 front를 먼저 하나 증가시키고 front가 가리키는 위치에 있는 요소를 삭제한다.

Untitled