Queue.py

# =============================================
# 큐(Queue) 예제
# =============================================

from collections import deque

# ==================== 기본 큐 구현 (deque) ====================
print("=== 기본 큐 구현 ===")

queue = deque()

# enQueue - 데이터 삽입
queue.append(10)
queue.append(20)
queue.append(30)
print(f"enQueue 후: {list(queue)}")  # [10, 20, 30]

# deQueue - 데이터 제거
front = queue.popleft()
print(f"deQueue된 값: {front}")      # 10
print(f"deQueue 후: {list(queue)}")  # [20, 30]

# 비어있는지 확인
print(f"큐 비었는지: {len(queue) == 0}")  # False

# ==================== deque 양방향 연산 ====================
print("\n=== deque 양방향 연산 ===")

dq = deque([1, 2, 3, 4, 5])
print(f"초기: {list(dq)}")

# 왼쪽에 추가
dq.appendleft(0)
print(f"appendleft(0): {list(dq)}")  # [0, 1, 2, 3, 4, 5]

# 오른쪽에서 제거
right = dq.pop()
print(f"pop(): {right}, 결과: {list(dq)}")  # 5, [0, 1, 2, 3, 4]

# 회전
dq.rotate(2)  # 오른쪽으로 2칸 회전
print(f"rotate(2): {list(dq)}")      # [3, 4, 0, 1, 2]

dq.rotate(-2)  # 왼쪽으로 2칸 회전
print(f"rotate(-2): {list(dq)}")     # [0, 1, 2, 3, 4]

# ==================== 리스트로 큐 구현 (비효율적) ====================
print("\n=== 리스트로 큐 구현 (비효율적) ===")

# 리스트의 pop(0)은 O(n) 시간복잡도
queue_list = []
queue_list.append(1)
queue_list.append(2)
queue_list.append(3)
front = queue_list.pop(0)  # 비효율적! O(n)
print(f"pop(0) 결과: {front}, 리스트: {queue_list}")

# ==================== 큐 클래스 구현 ====================
print("\n=== 큐 클래스 구현 ===")

class Queue:
    def __init__(self):
        self.queue = deque()

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

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어있습니다.")
            return None
        return self.queue.popleft()

    def front(self):
        if self.is_empty():
            return None
        return self.queue[0]

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

q = Queue()
q.enqueue("A")
q.enqueue("B")
q.enqueue("C")
print(f"front: {q.front()}")         # A
print(f"dequeue: {q.dequeue()}")     # A
print(f"size: {q.size()}")           # 2

# ==================== 원형 큐 구현 ====================
print("\n=== 원형 큐 구현 ===")

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = 0
        self.rear = 0

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        return (self.rear + 1) % self.size == self.front

    def enqueue(self, data):
        if self.is_full():
            print("큐가 가득 찼습니다.")
            return
        self.rear = (self.rear + 1) % self.size
        self.queue[self.rear] = data

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어있습니다.")
            return None
        self.front = (self.front + 1) % self.size
        return self.queue[self.front]

cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(f"dequeue: {cq.dequeue()}")    # 1
print(f"dequeue: {cq.dequeue()}")    # 2

# ==================== 프린터 큐 예제 ====================
print("\n=== 프린터 큐 예제 ===")

def printer_queue(priorities, location):
    """프린터 대기열에서 특정 문서가 몇 번째로 출력되는지"""
    queue = deque(enumerate(priorities))
    count = 0

    while queue:
        current = queue.popleft()
        # 대기열에 더 높은 우선순위가 있으면 뒤로 보냄
        if queue and current[1] < max(item[1] for item in queue):
            queue.append(current)
        else:
            count += 1
            if current[0] == location:
                return count
    return count

# 테스트
print(printer_queue([2, 1, 3, 2], 2))  # 1 (우선순위 3이 가장 높음)
print(printer_queue([1, 1, 9, 1, 1, 1], 0))  # 5