C로 만드는 자료구조- Queue란?

큐(Queue)이란?

 큐도 자료를 차례대로 저장하는 선형 자료구조이다. 큐가 가지는 고유 특성은 FIFO(First-In-First-Out) - 선입선출(先入先出), 즉, 가장 먼저 들어간 자료가 가장 먼저 나오는 자료이다'라는 특성이다. 일상생활에서도 큐라는 단어를 자주 접한다.. 예를 들어 식당에 들어가기 위해 길게 늘어진 사람들의 줄을 대기열 혹은 큐라고 말한다. 큐가 길다는 말은 기다리는 사람들이 많아서 시간이 오래 걸린다는 의미로도 사용한다. 이러한 큐에 특징은 선입선출의 특성을 가진다. 

 스택에서는 스택의 특성 때문에 모든 연산이 스택의 제일 위(Top)에서 일어난다. 큐에서는 자료를 추가할 때는 뒤에서 추가하고 자료를 반환할 때는 앞에서 자료를 빼가기 때문에 스택보다 좀 더 생각해야 하는 부분이 많아진다. 큐에서는 맨 앞에 있는 자료를 프런트(front)라고 하며 맨 끝에 있는 자료를 리어(rear)라고 한다. 따라서 큐에서의 연산은 front와 rear를 어떻게 설정해줘야 할지 잘 생각해야 한다.

큐의 개념

 앞서 말했듯이 스택은 자료를 한 방향으로만 쌓는 자료구조이다. 큐에는 3가지 핵심 연산이 있는데 이를 알아보자.

- 인큐(enqueue)

인큐는 새로운 자료를 큐에 추가하는 연산을 말한다. 앞서 말했듯이 새로운 자료는 큐에 제일 뒤에 추가된다.

- 디큐(dequeue)

디큐는 큐에서 자료를 꺼내는 연산을 말한다. 이때 자료를 반환하고 제거까지 한다. 앞서 말했듯이 자료를 꺼내는 것은 큐에 제일 앞(front)에서만 실행된다.

- 피크(peek)

피크는 스택에서의 피크와 똑같은 개념이다. 큐에서 front에 있는 자료를 반환하는 것은 디큐와 동일하지만 디큐와 다르게 반환한 자료를 제거하지는 않는다.

큐의 추상 자료형

스택 사용에 필요한 기본 연산을 정리한 스택의 추상 자료형(ADT:Abstract Data Type)을 표로 정리했다. 

이름	입력	출력	설명
큐 생성	최대 원소 개수 n	큐 Q	최대 n 개의 원소를 가지는 공백 리스트 Q를 생성
큐 삭제	큐 Q	n/a	큐 제거
원소 추가 가능 여부 판단(isFull)	큐 Q	True/False	큐의 공간이 가득 찼는지 판단
공백 큐인지 판단(isEmpty)	큐 Q	True/False	큐가 공백인지 아닌지 판단
자료 추가(enqueue)	큐 Q	성공/실패 여부	큐의 제일 뒤에 새로운 원소 추가
디큐(dequeue)	큐 Q	원소 E	큐의 맨 앞에 있는 원소 E를 큐에서 제거 후 반환
피크(peek)	큐 Q	원소 E	큐의 맨 앞에 있는 원소를 반환

  큐 생성 시에 필요한 입력 파마 리터 최대 원소 저장 개수를 뜻하는 n은 배열을 이용해 큐를 구현할 때만 필요한 입력 파라미터이다.

 enqueue, dequeue, peek는 앞서 설명한 연산들을 의미하며 isFull과 isEmpty는 각각 큐가 가득 차있는 상태인지, 공백 큐인지 알려주며 연산을 실행할 때 도움을 준다.

큐의 구현

 큐도 스택과 마찬가지로 배열을 이용한 구현과 포인터를 이용한 구현 2가지로 나뉜다. 그에 따른 장단점도 똑같다.  배열로 구현할 때는 구현이 비교적 간단하지만 메모리 활용 측면에서는 비효율적이고 포인터를 이용하여 구현 할때는 구현은 어렵지만 메모리를 효율적으로 사용이 가능하다.