큐(Queue): 선입선출(FIFO) 구조의 개념과 활용

🔹 큐란?

1. 큐(Queue)의 정의

큐(Queue)는 선입선출(FIFO, First In First Out) 원칙을 따르는 선형 데이터 구조로, 먼저 들어온 데이터가 먼저 나가는 방식으로 동작합니다. 큐는 데이터를 일정한 순서로 처리해야 하는 프로그램에서 필수적으로 사용됩니다.

✅ 큐의 주요 특징:

• 선입선출(FIFO) 방식으로 작동
• 삽입(Enqueue)과 삭제(Dequeue) 연산 제공
• O(1)의 시간 복잡도로 연산 수행 가능
• 데이터를 순차적으로 처리하는 데 적합

📌 큐는 작업 스케줄링, 네트워크 패킷 처리, 프린터 작업 대기열 등에서 필수적인 데이터 구조입니다.

---

🔹 큐의 주요 연산

1. 삽입(Enqueue) - O(1)

✅ 새로운 요소를 큐의 뒤쪽(Rear)에 추가하는 연산

✔️ Enqueue 연산 예제 (Python):

from collections import deque
queue = deque()
queue.append(10)  # 10 추가
queue.append(20)  # 20 추가
print(queue)  # 출력: deque([10, 20])

📌 큐의 삽입 연산은 O(1) 시간 복잡도를 가집니다.

2. 삭제(Dequeue) - O(1)

✅ 큐의 앞쪽(Front)에서 요소를 제거하고 반환하는 연산

✔️ Dequeue 연산 예제 (Python):

queue = deque([10, 20, 30])
print(queue.popleft())  # 출력: 10
print(queue)  # 출력: deque([20, 30])

📌 큐의 삭제 연산은 O(1) 시간 복잡도를 가집니다.

3. 조회(Peek) - O(1)

✅ 큐의 맨 앞 요소를 제거하지 않고 조회하는 연산

✔️ Peek 연산 예제 (Python):

queue = deque([10, 20, 30])
print(queue[0])  # 출력: 10 (맨 앞의 요소)

📌 큐의 맨 앞 요소를 확인할 수 있지만, 제거되지는 않습니다.

4. 큐가 비어있는지 확인(Is Empty) - O(1)

✅ 큐가 비어있는지 확인하는 연산

✔️ Is Empty 연산 예제 (Python):

queue = deque()
print(len(queue) == 0)  # 출력: True

📌 비어있는지 확인하는 것은 프로그램의 오류 방지에 유용합니다.

---

🔹 큐의 구현 방법

1. 리스트(List)를 이용한 큐 구현 (Python)

✅ Python의 리스트를 활용한 기본적인 큐 구현

✔️ 리스트 기반 큐 예제:

class Queue:
    def __init__(self):
        self.queue = []

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

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        return "Queue is empty"

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        return "Queue is empty"

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

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

q = Queue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())  # 출력: 10
print(q.peek())  # 출력: 20

📌 리스트를 활용한 큐는 간단하지만, pop(0) 연산이 O(n)이므로 비효율적일 수 있습니다.

2. 연결 리스트(Linked List)를 이용한 큐 구현

✅ 연결 리스트를 활용한 큐 구현은 O(1) 성능을 유지하면서 메모리를 효율적으로 사용 가능

✔️ 연결 리스트 기반 큐 예제:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.front = self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = self.rear = new_node
            return
        self.rear.next = new_node
        self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return "Queue is empty"
        temp = self.front
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return temp.data

q = LinkedListQueue()
q.enqueue(10)
q.enqueue(20)
print(q.dequeue())  # 출력: 10

📌 연결 리스트 기반 큐는 삽입 및 삭제가 O(1)로 효율적입니다.

---

🔹 큐의 활용 사례

1. 작업 스케줄링(Task Scheduling)

✅ 운영체제에서 작업을 순차적으로 처리하는 데 사용

✔️ 예제:

queue = deque()
queue.append("Task 1")
queue.append("Task 2")
queue.append("Task 3")
while queue:
    print("Processing:", queue.popleft())

📌 작업이 순서대로 처리됩니다.

2. 네트워크 패킷 처리(Network Packet Processing)

✅ 네트워크에서 패킷을 처리할 때 먼저 도착한 패킷부터 처리하는 방식

✔️ 예제:

packet_queue = deque(["Packet 1", "Packet 2", "Packet 3"])
while packet_queue:
    print("Processing:", packet_queue.popleft())

📌 패킷을 수신한 순서대로 처리합니다.

---

📌 결론

✅ 큐(Queue)는 선입선출(FIFO) 원칙을 따르는 선형 데이터 구조입니다.
✅ 삽입(Enqueue)과 삭제(Dequeue)은 O(1)의 시간 복잡도를 가집니다.
✅ 작업 스케줄링, 네트워크 패킷 처리, 대기열 관리 등 다양한 분야에서 활용됩니다.
✅ 배열 기반, 연결 리스트 기반 등 다양한 방식으로 큐를 구현할 수 있습니다.