큐(Queue)

큐란?

• 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 자료구조
• 줄 서기, 대기열, BFS 등에서 사용됨

---

주요 연산

연산	설명
enqueue(x)	뒤에 데이터 추가
dequeue()	앞에서 제거
peek()	맨 앞 값 확인 (제거 X)
is_empty()	비었는지 확인

---

큐 구현

리스트

queue = []
queue.append(1)
queue.pop(0)  # O(N) → 앞에서 제거 시 전체 이동 발생

deque

from collections import deque

queue = deque()
queue.append(1)       # enqueue
queue.popleft()       # dequeue

---

고정 길이 큐 클래스 구현

class FixedQueue:
    def __init__(self, size):
        self.data = [None] * size
        self.front = 0
        self.rear = 0
        self.count = 0
        self.size = size

    def enqueue(self, x):
        if self.count == self.size:
            raise Exception("Full")
        self.data[self.rear] = x
        self.rear = (self.rear + 1) % self.size
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise Exception("Empty")
        value = self.data[self.front]
        self.front = (self.front + 1) % self.size
        self.count -= 1
        return value

    def peek(self):
        return self.data[self.front] if self.count > 0 else None

    def is_empty(self):
        return self.count == 0

실제 값을 삭제하진 않고, front 포인터만 이동

원형 큐(Circular Queue) 방식

---

시간 복잡도 비교

연산	리스트	deque
enqueue	O(1)	O(1)
dequeue	O(N)	O(1)
peek	O(1)	O(1)

---

큐 활용 예시

• BFS 탐색
• 프린터 대기열
• 캐시 시뮬레이션
• 생산자-소비자 모델

---

C 언어 구현 시 유의

항목	설명
동적 배열 없음	배열 직접 선언 필요
front/rear	포인터 변수 직접 관리
pop(0) 없음	인덱스로 직접 처리
원형 구조 필수	공간 낭비 막기 위해 mod 연산 필요