큐(Queue)는 컴퓨터 과학에서 가장 기본적인 자료구조 중 하나로, 선입선출(FIFO: First In First Out) 방식으로 작동한다. 즉, 먼저 들어온 데이터가 먼저 나가는 형태의 자료구조이다. 대기열이라고도 불리며, 현실 세계의 줄서기와 유사한 개념이다.

큐의 기본 연산

큐는 다음과 같은 기본 요소를 가지고 있다:

• front(head): 큐의 맨 앞 위치로, 데이터가 삭제되는 곳이다.
• rear(tail): 큐의 맨 뒤 위치로, 새로운 데이터가 삽입되는 곳이다.
• enqueue: 큐의 rear에 새로운 데이터를 추가하는 연산이다.
• dequeue: 큐의 front에서 데이터를 제거하고 반환하는 연산이다.
• peek: 큐의 front에 있는 데이터를 제거하지 않고 확인하는 연산이다.
• isEmpty: 큐가 비어있는지 확인하는 연산이다.
• isFull: 큐가 가득 찼는지 확인하는 연산이다(배열 기반 구현에서 사용).

큐의 종류

큐는 구현 방식에 따라 여러 유형이 있다:

• 선형 큐(Linear Queue): 배열을 이용한 기본적인 큐 구현 방식으로, 데이터가 삭제되면 앞쪽에 빈 공간이 생기는 단점이 있다.
• 원형 큐(Circular Queue): 선형 큐의 단점을 보완한 구현 방식으로, 배열의 처음과 끝이 연결되어 있는 형태이다.
• 링크드 리스트 큐(Linked List Queue): 연결 리스트를 이용한 구현 방식으로, 크기 제한 없이 동적으로 메모리를 할당한다.
• 우선순위 큐(Priority Queue): 각 요소에 우선순위가 부여되어, FIFO 방식이 아닌 우선순위에 따라 데이터가 처리되는 큐이다. 이번 페이지에서는 구현방법을 설명하지 않는다
• 덱(Deque, Double-Ended Queue): 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐이다. 이번 페이지에서는 구현방법을 설명하지 않는다

배열을 이용한 선형 큐 구현

1. 큐의 구조체 정의