큐(Queue)란?

큐의 개념

• 먼저 집어넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식
• 삭제의 위치와 방법이 제한되어 있는 유한 순서 리스트
• 스택(LIFO)과 반대되는 개념
• 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황(프린터의 출력 처리, 윈도 시스템의 메시지 처리기 등)에서 이용

큐의 연산

• enQueue : 큐 안에 데이터를 넣는 연산
• deQueue : 큐 안의 데이터를 빼내는 연산
• peek : 큐의 front 데이터를 반환하는 연산
• isEmpty : 큐가 빈 경우 true를 그렇지 않은 경우 false를 반환

큐의 종류

1. 선형 큐(Linear Queue)
   • 기본적인 큐의 형태
   • 막대 모양으로 된 큐
   • 크기가 제한, 빈 공간 사용 시 모든 자료를 꺼내거나 옮겨야 하는 단점
2. 원형 큐(Circular Queue)
   • 선형큐의 단점을 보완하는 구조
   • front와 rear가 연결된 형태
   • front와 rear의 구분을 위한 공간이 필요 -> 'front = rear' 라면 공백상태로 인지
3. 우선순위 큐(Priority Queue)
   • 데이터 삽입 시 우선순위에 따라 정렬 후 저장하는 방식
4. 링크드 큐(Linked Queue)
   • 연결 리스트로 구현한 큐(연결 리스트를 사용한 것)
   • 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 것이 특징
   • 필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리

큐의 구조

 

 

cf) 큐와 스택의 비교!

항목 자료구조	삽입연산		삭제연산
	연산자	삽입 위치	연산자	삽입 위치
STACK	push	top	pop	top
QUEUE	enQueue	rear	deQueue	front