[Python] 큐 (queue) 기본개념

데이터를 임시 저장할 때 쓰는 자료구조
입, 출력 순서는 선입 선출 FIFO(First In First Out) 방식

개요

큐는 데이터를 저장할 때 한쪽 끝(뒤, rear)에서 삽입(enqueue)하고, 다른 쪽 끝(앞, front)에서 삭제(dequeue)하는 자료구조. 즉, 먼저 들어온 데이터가 가장 먼저 나감

©️ 나

주요 특성

• FIFO 특성:
  선입선출(First-In, First-Out): 큐에 먼저 삽입된 데이터가 가장 먼저 삭제
  이는 대기열, 티켓 발권 시스템, 네트워크 패킷 처리 등 실제 상황에서 자연스럽게 발생하는 순서를 반영

기본 연산

©️ 나

• enqueue(item):
  큐의 뒤쪽에 새로운 데이터를 추가
  큐가 가득 찬 경우(배열을 사용한 고정 크기 구현 시) 예외 처리를 하거나, 동적 크기 조정을 수행할 수 있
• dequeue():
  큐의 가장 앞에 있는 데이터를 선택
  선택된 데이터를 큐에서 제거한 후, 해당 데이터를 반환
  큐가 비어 있을 경우, 예외를 발생시키거나 특별한 값(None 등)을 반환
• peek() 또는 front():
  큐의 front 요소를 읽어 반환. 데이터는 큐에서 제거되지 않음
• isEmpty(): 큐 내 데이터가 하나도 없으면 True, 그렇지 않으면 False를 반환
• size(): (구현에 따라 제공) 큐에 저장된 데이터의 개수를 반환

구현

• 배열(Array) 기반 큐 : 고정 크기 배열 사용
  • 단점: 일반 배열은 front와 rear 이동으로 빈 공간 생김 → 원형 큐 필요
• 원형 큐(Circular Queue) : 배열의 끝과 시작을 연결하는 구조
  • 장점: 배열 전체 공간 효율적 사용, 삽입/삭제 O(1)
  • 구현: 모듈로 연산 사용하여 인덱스 순환 처리
  • 연결 리스트(Linked List) 기반 큐
• 단일 연결 리스트 사용
  • 장점: 동적 크기, 삽입/삭제 O(1)
  • 단점: 추가 메모리 오버헤드 있음

배열을 활용한 큐 구현 예제

아래는 내가 백준 18258-큐 2를 풀이한 내용이다
문제 보기
위에 언급한 기본 연산 + ⍺ 를 구현하여, 그 연산에 맞게 큐처럼 동작하면 된다.

import sys


T = int(sys.stdin.readline().rstrip())
# 큐로 사용할 배열 선언
arr = []
# 제시한 push, pop, size, empty, front, back 함수 선언
def push(val):
    arr.append(val) # append로 배열의 끝(rear)에 값 저장되도록
def pop():
    if len(arr) == 0:
        print(-1)
    else :
        print(arr[0])
        arr.pop(0) # pop함수의 idx 0을 지정해줌으로써 배열의 앞(front)에서 값이 제거되도록
def size():
    print(len(arr)) # 배열의 크기 출력
def empty(): # 큐가 비어있으면 1, 아니면 0 출력
    if len(arr) == 0:
        print(1)
    else:
        print(0)
def front(): # 가장 앞 데이터 확인
    if len(arr) != 0:
        print(arr[0])
    else:
        print(-1)
def back(): # 가장 뒤 데이터 확인
    if len(arr) != 0:
        print(arr[-1]) # arr[-1]을 할 경우 인덱스에서 가장 끝에잇는 값을 가리킨다
    else:
        print(-1)

for i in range(T):
    command = sys.stdin.readline().rstrip().split()
    num = 0
    if 'push' in command:
        command, num = map(str, command)
        num = int(num)
        push(num)
    elif 'pop' in command:
        pop()
    elif 'size' in command:
        size()
    elif 'empty' in command:
        empty()
    elif 'front' in command:
        front()
    elif 'back' in command:
        back()

원형 큐(링 버퍼; ring buffer)를 활용한 큐 구현 예제

class CircularQueue:
    def __init__(self, capacity):
        # capacity: 큐의 최대 용량. 고정 크기 배열 사용.
        self.capacity = capacity

        # queue: 고정 크기 배열 초기화. 모든 요소는 None으로 설정.
        self.queue = [None] * capacity

        # front: 큐의 맨 앞 위치. 데이터가 제거(dequeue)되는 위치임.
        self.front = 0

        # rear: 큐의 맨 뒤 위치. 새 데이터가 삽입(enqueue)되는 위치임.
        self.rear = 0

        # size: 현재 큐에 저장된 요소의 개수. 큐가 비었는지 또는 꽉 찼는지 판단하는데 사용됨.
        self.size = 0

    def is_empty(self):
        # 큐가 비었으면 True 반환, 아니면 False 반환.
        return self.size == 0

    def is_full(self):
        # 큐가 꽉 찼으면 True 반환, 아니면 False 반환.
        return self.size == self.capacity

    def enqueue(self, item):
        # 큐에 새 데이터를 삽입하는 연산.
        if self.is_full():
            # 만약 큐가 꽉 찼다면, 데이터 삽입이 불가능하므로 IndexError 발생.
            raise IndexError("Queue is full")

        # 현재 rear 위치에 item 삽입.
        self.queue[self.rear] = item

        # rear 포인터를 1 증가시키되, capacity로 나눈 나머지를 취해 원형으로 순환하게 함.
        # 즉, 배열 끝에 도달하면 다시 0번 인덱스로 돌아감.
        self.rear = (self.rear + 1) % self.capacity

        # 큐에 저장된 요소의 개수 증가.
        self.size += 1

    def dequeue(self):
        # 큐에서 데이터를 제거하고 반환하는 연산.
        if self.is_empty():
            # 만약 큐가 비어있다면, 제거할 데이터가 없으므로 IndexError 발생.
            raise IndexError("Queue is empty")

        # front 위치의 데이터를 item에 저장. 이 데이터가 제거될 대상임.
        item = self.queue[self.front]

        # 제거된 위치를 None으로 초기화 (선택적 처리; 메모리 관리 및 디버깅에 도움).
        self.queue[self.front] = None

        # front 포인터를 1 증가시키되, capacity로 나눈 나머지를 취해 원형으로 순환하게 함.
        self.front = (self.front + 1) % self.capacity

        # 큐에 저장된 요소의 개수 감소.
        self.size -= 1

        # 제거한 데이터를 반환.
        return item

    def peek(self):
        # 큐의 front 위치에 있는 데이터를 확인하는 연산 (제거하지 않음).
        if self.is_empty():
            # 큐가 비어 있으면 확인할 데이터가 없으므로 IndexError 발생.
            raise IndexError("Queue is empty")

        # front 위치의 데이터를 반환.
        return self.queue[self.front]

    def __str__(self):
        # 큐 전체 상태를 문자열로 반환 (디버깅 및 출력용).
        return str(self.queue)

# 원형 큐 사용 예제
if __name__ == '__main__':
    # 용량 5인 원형 큐 생성
    cq = CircularQueue(5)

    # 큐에 10, 20, 30 삽입
    cq.enqueue(10)
    cq.enqueue(20)
    cq.enqueue(30)

    # 현재 큐의 상태 출력
    print("현재 큐 상태:", cq)

    # 큐의 front 요소 확인 (삭제되지 않음)
    print("첫번째 요소:", cq.peek())

    # dequeue 연산으로 front 요소 제거 후 반환
    print("dequeue:", cq.dequeue())

    # 제거 후 큐의 상태 출력
    print("큐 상태:", cq)

활용

• 프로세스 스케줄링: 도착 순서대로 프로세스 처리
• 네트워크 패킷 처리: 패킷 도착 순서 유지
• 프린터 작업 관리: 인쇄 요청 순서대로 처리
• 너비 우선 탐색(BFS): 그래프 탐색 시 방문 순서 관리