큐 (자료 구조) 편집하기

'''큐'''(queue)는 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하고 관리하는 선형 자료 구조이다. 큐에서는 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다.
==개요==
큐는 한쪽 끝에서는 데이터를 삽입(Enqueue)하고, 다른 한쪽 끝에서는 데이터를 삭제(Dequeue)하는 방식으로 동작한다. 이처럼 입출력 방향이 분리되어 있어, 데이터가 들어간 순서대로 처리되어야 하는 상황에서 적합하다. 일상적인 예로는 줄 서기(대기열)가 있다.
==주요 연산==
*'''Enqueue'''
**큐의 뒤쪽(Rear) 끝에 새로운 데이터를 추가하는 연산.
*'''Dequeue'''
**큐의 앞쪽(Front) 끝에서 데이터를 제거하고 반환하는 연산.
*'''Peek (Front)'''
**큐의 앞쪽에 있는 데이터를 삭제하지 않고 확인하는 연산.
*'''isEmpty'''
**큐가 비어 있는지 확인하는 연산.
*'''isFull''' (고정 크기 큐의 경우)
**큐가 가득 찼는지 확인하는 연산.
==특징==
*'''선입선출(FIFO)''' 방식을 따른다.
*데이터가 들어간 순서대로 처리된다.
*일반적으로 배열이나 연결 리스트를 사용하여 구현된다.
*고정 크기의 큐에서는 오버플로우(Overflow)나 언더플로우(Underflow) 상태를 관리해야 한다.
==종류==
*'''선형 큐(Linear Queue)'''
**단순히 삽입과 삭제를 선형으로 처리하는 큐.
*'''원형 큐(Circular Queue)'''
**큐의 양 끝을 연결하여 공간을 재활용할 수 있도록 한 큐.
*'''우선순위 큐(Priority Queue)'''
**삽입된 순서가 아니라 우선순위(priority)에 따라 요소를 처리하는 큐.
*'''이중 큐(Deque, Double-Ended Queue)'''
**양쪽 끝에서 모두 삽입과 삭제가 가능한 큐.
==활용 예시==
*프로세스 스케줄링(운영체제)
*프린터 작업 대기열
*네트워크 패킷 처리
*BFS(너비 우선 탐색) 알고리즘에서 노드 탐색
*실시간 데이터 스트림 처리
==큐와 스택의 차이==
*'''큐''': 선입선출(FIFO) 방식
*'''스택''': 후입선출(LIFO, Last In First Out) 방식
==간단한 구현 예시==
<syntaxhighlight lang="python">
class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        raise IndexError("dequeue from empty queue")

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        raise IndexError("peek from empty queue")

    def size(self):
        return len(self.items)

# 사용 예시
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
print(q.dequeue())  # 출력: 10
print(q.peek())     # 출력: 20
</syntaxhighlight>
==같이 보기==
*[[스택]]
*[[우선순위 큐]]
*[[원형 큐]]
*[[이중 큐]]
*[[연결 리스트]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms'' (3rd ed.). MIT Press.
*Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). ''Data Structures and Algorithms in Java'' (6th ed.). Wiley.
[[분류:자료 구조]]