Queue

FIFO (first in first out)

• FIFO 원칙에 기반한 자료구조로,
• 가장 먼저 insert된 요소가 가장 먼저 나오는 형식입니다.
• enqueue : 큐의 뒷부분에 요소를 추가하는 작업입니다. 이는 큐에 새로운 항목을 삽입하는 과정을 말합니다.
• dequeue : 큐의 앞부분에서 요소를 제거하는 작업입니다. 이는 큐에서 가장 오래된 항목을 삭제하는 과정을 의미하며, 이 항목은 큐에 가장 먼저 추가된 항목입니다.

기본 작업

• Enqueue : 큐 끝에 요소 insert
• Dequeue : 큐 앞의 요소 delete
• isEmpty : stack이 비어있으면 true, 그렇지 않으면 false 반환
• isFull : 큐가 꽉 차있으면 true, 그렇지 않으면 false 반환
• peek : 대기열을 제거하지 않고 대기열의 앞부분 값 가져오기
  
  

시간복잡도

• O(1) : 요소의 추가와 제거가 큐의 끝과 시작에서만 일어나므로, 요소의 수에 관계없이 작업 시간이 일정하게 걸립니다.
  
  

활용예시

1) 프린터의 출력 처리
2) 콜센터 고객 대기 시간
3) 캐시(cache) 구현

from collections import deque

class Cache:
    def __init__(self, size):
        self.cache = deque(maxlen=size)  # 고정 크기의 큐 생성
        self.size = size

    def access_data(self, data):
        if data in self.cache:
            # 데이터가 캐시에 있으면, 최근 접근된 데이터로 업데이트하기 위해 제거 후 다시 추가
            self.cache.remove(data)
            self.cache.append(data)
            print(f"'{data}'은(는) 캐시에서 발견되어 최근 항목으로 업데이트됨")
        else:
            # 캐시에 데이터가 없으면 추가
            self.cache.append(data)
            print(f"'{data}'을(를) 캐시에 추가함")

    def display_cache(self):
        print("현재 캐시 상태:", list(self.cache))

# 캐시 생성 및 사용 예시
cache_size = 3
cache = Cache(cache_size)

# 데이터 접근
cache.access_data("A")
cache.access_data("B")
cache.access_data("C")
cache.display_cache()

# 캐시가 가득 찼을 때, 새로운 데이터 추가
cache.access_data("D")
cache.display_cache()

# 이미 캐시에 있는 데이터 접근
cache.access_data("B")
cache.display_cache()

캐시 관리에 Queue를 쓰는 이유
-> 캐시가 가득 차서 새 데이터를 추가하는 경우 가장 오래된 데이터 (Queue 맨 앞의 데이터)가 제거되는데, 가장 오래된 데이터가 다시 사용될 가능성이 가장 적기 때문.

이미지 출처
https://www.programiz.com/dsa/queue
참고
https://www.programiz.com/dsa/queue