Data structures (with python) - 6. Queue

Data structures (with python) - 6. Queue

 

💡 Queue is a linear collection of items where items are inserted and removed in a particular order. The queue is also called a FIFO Data Structure because it follows the “First In, First Out” principle i.e., the item that is inserted in the first is the one that is taken out first.

큐는 특정 순서로 항목이 삽입되고 제거되는 항목의 선형 컬렉션입니다. 큐는 "선입선출" 원칙, 즉 가장 먼저 삽입된 항목이 가장 먼저 제거되는 원칙을 따르기 때문에 FIFO 데이터 구조라고도 합니다.

 

위키피디아

 

 

자료구조의 대표 주자 2개 큐 & 스택,  큐 이다

 

큐(Queue) 는 '선입선출' (First In First Out, FIFO) 원칙을 따르는 자료구조입니다.

즉, 가장 먼저 들어간(선입) 데이터가 가장 먼저 나오게(선출) 됩니다. 이는 실생활에서 사람들이 줄을 서서 기다리는 것과 같은 원리입니다.

 

1. Enqueue: 큐의 뒤쪽에 항목을 추가합니다.

2. Dequeue: 큐의 앞쪽에서 항목을 제거하고 그 항목을 반환합니다.

 

In Python

Python에서는 리스트를 사용하여 큐를 구현할 수 있습니다.

리스트의 append() 메서드르 사용하여 enqueue 연산을 구현하고,

pop() 메서드를 사용하여 dequeue 연산을 구현할 수 잇습니다.

 

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

    # 큐에 요소 추가 (enqueue)
    def enqueue(self, data):
        self.queue.append(data)

    # 큐의 맨 앞 요소 제거 및 반환 (dequeue)
    def dequeue(self):
        if self.is_empty():
            return None
        else:
            return self.queue.pop(0)

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

 

위에 정의한 Queue 클래스를 활용하는 방법을 상펴 보자

 

q = Queue()

q.enqueue(1)  # 1을 큐에 추가
q.enqueue(2)  # 2를 큐에 추가
q.enqueue(3)  # 3을 큐에 추가

print(q.dequeue())  # 1을 반환하고 큐에서 제거
print(q.dequeue())  # 2를 반환하고 큐에서 제거
print(q.dequeue())  # 3을 반환하고 큐에서 제거

 

위 코드에서는 1,2,3 순서대로 큐에 추가(enqueue)했고, 이후 세 번 dequeue 연산을 수행하여 1,2,3 순서대로 데이터가 반환되고 큐에서 제거되는 것을 확인할 수 있다.

 

코테 & 알고리즘

너비 우선 탐색 (BFS)에 사용하는 방법

from collections import deque

def bfs(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.append(vertex)
            queue.extend(graph[vertex] - set(visited))
    return visited

graph = {'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'}}
print(bfs(graph, 'A'))  # A에서 가장 가까운 노드부터 순서대로 출력

 

이외에도, 큐는 다양한 코딩 테스트 문제에서 활용될 수 있습니다.

 

1. 탐색 문제 : 특정 조건을 만족하는 경로를 찾는 문제 등에서 큐를 활용할 수 있습니다.

2. 시물레이션 문제 : 실시간으로 데이터가 들어오고 처리되는 시스템을 시뮬레이션하는 문제에서 큐를 사용하여 데이터를 관리할 수 있습니다.

3. 스케쥴링 문제 : 특정한 우선순위에 따라 작업을 처리해야 하는 문제에서 우선순위 큐를 활용할 수 있습니다.