[자료구조] 큐 (Queue)란?

1. 큐 (Queue)란?

큐(Queue)는 선형 자료구조로, 데이터를 저장하고 검색하는 데 사용되는 중요한 자료구조입니다. 큐는 데이터를 저장할 때 "선입선출" (FIFO, First-In-First-Out) 원칙을 따릅니다. 즉, 먼저 큐에 추가된 데이터는 먼저 처리되고 제거됩니다.

2. 큐의 구성 요소

• 데이터 요소 (Elements): 큐에 저장되는 실제 데이터 항목들로, 큐에 추가되거나 제거됩니다.
• 프런트(Front)와 리어(Rear): 큐의 시작과 끝 지점을 나타내는 두 포인터입니다. 이들은 데이터의 추가 및 제거에 사용됩니다.
• 리어(Rear): 큐의 끝 지점을 가리키는 포인터입니다. 큐에 추가 연산이 수행되면, 새로운 데이터가 리어에 추가됩니다.

[큐 용어]

• add() : 데이터를 추가하는 작업
• delete() : 데이터를 꺼내 사용하는 작업
• rear : 가장 최근에 추가한 데이터를 지시하는 포인터 또는 인덱스
• front : 사용할 데이터를 지시하는 포인터 또는 인덱스
• overflow : 끝까지 add()된 경우, rear == SIZE -1 일 때 add()시도하면 발생
• underflow : 더 이상 꺼낼 수 없는 경우, front > rear 일 때 delete() 시도하면 발생

3. 큐의 기본 동작

• Enqueue (데이터 추가): 큐의 리어에 데이터를 추가합니다. 새로운 데이터가 큐의 가장 뒤에 추가됩니다.
• Dequeue (데이터 제거): 큐의 프런트에서 데이터를 제거하고 반환합니다. 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다.
• Peek (데이터 확인): 큐의 프런트에서 데이터를 확인하지만 제거하지 않습니다.

4. 큐의 종류

• 선형 큐 (Linear Queue): 데이터를 FIFO 순서로 처리하는 가장 기본적인 큐
  

• 환형 큐 (Circular Queue): 큐의 마지막 요소가 첫 요소와 연결된 큐로, 원형으로 순환
  

• 우선순위 큐 (Priority Queue): 각 데이터 요소에 우선순위를 할당하고 해당 우선순위에 따라 데이터를 처리하는 큐
  

• 데큐(De Queue) : 양쪽에서 삽입, 삭제가 가능한 구조
  

5. 큐 vs 스택 비교

• 큐 (Queue): 데이터를 FIFO 순서로 처리합니다. 먼저 추가된 데이터가 먼저 제거됩니다.
• 스택 (Stack): 데이터를 LIFO 순서로 처리합니다. 가장 최근에 추가된 데이터가 가장 먼저 제거됩니다.

특성	큐 (Queue)	스택 (Stack)
처리 방식	선입선출 (FIFO, First-In-First-Out)	후입선출 (LIFO, Last-In-First-Out)
데이터 추가	리어(Rear)에서 추가 (Enqueue)	탑(Top)에서 추가 (Push)
데이터 제거	프런트(Front)에서 제거 (Dequeue)	탑(Top)에서 제거 (Pop)
데이터 확인 (Peek)	프런트(Front)에서 확인 (Peek)	탑(Top)에서 확인 (Peek)
주요 용도	작업 대기열 관리, 너비 우선 탐색	함수 호출 및 재귀, 깊이 우선 탐색
구현 방식	연결 리스트 또는 배열 사용	연결 리스트 또는 배열 사용
예시	일반 큐, 우선순위 큐, 환형 큐	일반 스택

6. 큐 활용문제 풀어보기

Q1. 큐에서 element를 삽입할 경우의 설명으로 맞는 것은?
① front의 위치를 감소시킨 후 element를 삽입

② front의 위치를 증가시킨 후 element를 삽입

③ rear의 위치를 감소시킨 후 element를 삽입

④ rear의 위치를 증가시킨 후 element를 삽입

Q2. 파이프의 입구와 출구를 연결시킨 형태의 큐로 기억장소의 낭비를 줄이기 위한 자료구조는 무엇인가?

① 연결 큐

② 이중 큐

③ 원형 큐

④ 데 큐