큐 Queue 정리(+ 큐 Queue로 풀 수 있는 프로그래밍 문제, 파이썬)

 

<큐의 특징>

1. 선입선출, FIFO, First In First Out

 

<큐 Queue의 ADT>

1. 큐의 개념

• 선입선출(FIFO, First In First Out) 구조를 가지는 자료구조
• 먼저 들어온 데이터가 먼저 나가는 구조 (줄 서기와 같음)
• 삽입은 rear(뒤), 삭제는 **front(앞)**에서 일어남

2. 큐를 위한 기본 필드

• data[maxSize]
  • 큐의 원소들을 저장하는 고정 크기 배열
  • 최대 크기 = maxSize
• front
  • 큐의 첫 번째 원소가 있는 위치(인덱스)
  • dequeue할 때 사용
  • 초기값: 보통 0 또는 -1
• rear
  • 큐의 마지막 원소가 들어간 위치(인덱스)
  • enqueue할 때 사용
  • 초기값: 보통 -1

---

3. 큐 ADT 연산 (배열 버전)

1. create(maxSize)
   • 크기 maxSize의 배열 생성
   • front = 0, rear = -1 초기화
2. isEmpty(Q)
   • front > rear → 큐가 비어있음
3. isFull(Q)
   • rear == maxSize - 1 → 큐가 가득 참
4. enqueue(Q, x)
   • rear++ 후 data[rear] = x
   • 큐 끝(rear)에 원소 삽입
5. dequeue(Q)
   • data[front] 반환 후 front++
   • 큐 앞(front)에서 원소 제거
6. peek(Q)
   • data[front] 반환 (삭제하지 않음)

---

4. 문제점과 개선

• 단순 배열 큐는 enqueue / dequeue 반복 시 앞 공간이 남아도 못 씀 → 메모리 낭비
• 해결책: 원형 큐(Circular Queue)
  • rear = (rear + 1) % maxSize
  • front = (front + 1) % maxSize
  • 배열을 “원형”으로 이어 붙여서 사용

---

✅ 정리:

• 큐는 배열 기반으로 구현할 때 front, rear, data[maxSize] 세 요소로 정의됨
• enqueue는 rear 이동, dequeue는 front 이동
• 메모리 낭비 방지를 위해 원형 큐 구현이 자주 쓰임