10월 자료구조 - 큐(Queue)

 

1. 이번 달 소개할 자료구조 주제

큐 (Queue)

 

2. 고른 자료구조의 정의

큐(Queue)는 선입선출(FIFO, First In First Out) 방식으로 작동하는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 원리입니다. 큐는 파이프라인, 은행의 줄, 대기열과 같은 일상적인 시스템에서 자주 사용됩니다. 큐의 주요 연산은 다음과 같습니다:

• 인큐(Enqueue): 큐에 데이터를 추가하는 연산
• 디큐(Dequeue): 큐에서 데이터를 제거하는 연산
• 프론트(Front): 큐의 가장 앞에 있는 데이터를 확인하는 연산
• 이즈엠티(IsEmpty): 큐가 비어있는지 확인하는 연산

큐는 주로 운영 체제의 작업 스케줄링, 네트워크 데이터 처리, BFS(너비 우선 탐색) 알고리즘 등에 사용됩니다.

 

3. 고른 자료구조를 구현한 파이썬 코드 전문

파이썬에서는 큐를 구현할 때 리스트를 사용하거나 collections.deque 모듈을 사용할 수 있습니다. 리스트를 이용한 큐 구현을 아래에 제시합니다.

class Queue:
    def __init__(self):
        self.queue = []  # 큐를 저장할 리스트

    def is_empty(self):
        # 큐가 비어있는지 확인
        return len(self.queue) == 0

    def enqueue(self, item):
        # 큐에 아이템을 추가
        self.queue.append(item)

    def dequeue(self):
        # 큐에서 아이템을 제거하고 반환
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            return "큐가 비어 있습니다."

    def front(self):
        # 큐의 가장 앞에 있는 아이템을 반환
        if not self.is_empty():
            return self.queue[0]
        else:
            return "큐가 비어 있습니다."

    def size(self):
        # 큐에 현재 저장된 아이템 수 반환
        return len(self.queue)

# 예시 사용
my_queue = Queue()
my_queue.enqueue(10)
my_queue.enqueue(20)
my_queue.enqueue(30)

print("Front item:", my_queue.front())  # 가장 앞에 있는 아이템 출력
print("Dequeued item:", my_queue.dequeue())  # 아이템 제거 및 출력
print("Queue size:", my_queue.size())  # 큐의 크기 출력

 

 

4. 고른 자료구조의 원리를 어떻게 파이썬으로 구현했는지

위 코드는 큐 자료구조를 파이썬의 클래스로 구현한 예시입니다. 코드 해설을 해보겠습니다.

• 클래스 정의: Queue 클래스를 정의하여 큐를 객체지향적으로 구현합니다. 이 클래스는 큐를 나타내는 리스트 self.queue를 가지고 있습니다.
• __init__ 메서드: 생성자 메서드로, 객체가 생성될 때 빈 리스트 self.queue를 초기화합니다. 이 리스트는 큐의 데이터를 저장하는데 사용됩니다.
• is_empty 메서드: 큐가 비어 있는지 확인하는 메서드입니다. 리스트의 길이가 0이면 큐가 비어 있다고 판단합니다.
• enqueue 메서드: 큐에 아이템을 추가하는 연산입니다. 큐의 끝에 아이템을 추가하려면 append() 메서드를 사용합니다. 큐에 데이터가 들어오는 순서대로 쌓입니다.
• dequeue 메서드: 큐에서 아이템을 제거하고 반환하는 연산입니다. 큐의 가장 앞에 있는 데이터를 꺼내기 위해 pop(0)을 사용합니다. 이 방법은 큐의 선입선출(FIFO) 원리를 따르며, 큐가 비어있으면 "큐가 비어 있습니다."라는 메시지를 반환합니다.
• front 메서드: 큐의 가장 앞에 있는 아이템을 반환하는 메서드입니다. pop(0)과는 달리 데이터를 제거하지 않고 가장 앞의 아이템을 확인만 합니다. 큐가 비어 있으면 메시지를 반환합니다.
• size 메서드: 현재 큐에 저장된 아이템의 개수를 반환하는 메서드입니다. 리스트의 길이인 len(self.queue)을 사용하여 큐의 크기를 계산합니다.

 

5. 느낀점

큐는 선입선출(FIFO) 방식으로 작동하는 매우 직관적인 자료구조입니다. 파이썬에서 리스트를 이용하여 큐를 구현하는 것은 간단하지만, 큐의 효율성을 고려할 때 pop(0)과 같은 연산은 큐의 크기가 커지면 성능이 저하될 수 있습니다. 실제로 대용량의 데이터를 다룰 때는 collections.deque를 사용하는 것이 더 효율적입니다. 그럼에도 불구하고, 큐의 원리와 이를 파이썬으로 구현하는 방법을 배움으로써 큐를 활용한 알고리즘 문제를 쉽게 풀 수 있다는 자신감을 얻었습니다. 큐는 다양한 분야에서 중요한 역할을 하므로, 이를 잘 이해하는 것이 많은 문제 해결에 도움이 될 것입니다.