"큐(Queue) 안 잡히네"는 잘못 된 말입니다.

김재만·2022년 1월 19일

큐(Queue)야말로 직관성의 끝판왕

큐는 스택처럼 프로그래밍의 역사를 함께한 고대 자료구조입니다. 프로그래밍의 역사 중 고대에 해당하는 시기에 자주 사용됐을 뿐만 아닙니다. 인류의 고대부터 인간이 식량을 획득하면 먼저 획득한 것이 나중에 획득한 것보다 먼저 상해, 가치를 잃기 일수였습니다. 때문에 조금이라도 배운 인간 혹은 사회에서는 (포장지에 유통기한이 적혀있지 않더라도)먼저 얻은 것을 먼저 소비하는 것이 상식입니다. 즉, 선입선출하는 자료구조는 특별한 자료구조 공부를 하지 않아도 효용과 입-출의 구조를 이해하기 쉬운 형태입니다.

이러한 자료구조는 오늘날 수많은 대기열(게임, 업무, 작업순서)처럼 자료 구조에 차례로 모였다 처리되는 업무에 활용되고 있습니다. 대기하는 일은 고객만족을 크게 떨어뜨리기 때문에, 현대 사회에서 기업의 가장 큰 골칫거리 중 하나입니다. 그렇다고 무작정, 가장 요청이 많은 시간에 맞춰 처리인력을 갖추기란 현실적으로 쉽지 않습니다. 그렇기에 대부분의 서비스에서는 대기 고객의 스트레스를 최소화하기 위해 큐를 활용합니다. 먼저 온 만큼 먼저 이용한다는 것은 직관적인 처리방식이고, 각자의 대기시간을 비슷하게 조정하는 효과가 있기 때문입니다.(물론 큐인줄 알고 믿고 살았지만, 알고리즘의 희생양인 경우도 있을 수 있습니다.)

큐의 구조와 기능

큐의 구조는 들어오는 입구와 나가는 출구가 다른 구조로 이루어져있습니다. 큐에는 필수족으로 요소를 넣는 push, 요소를 빼내는 pop, 내용물의 유무를 확인하는 is_empty의 기능이 필요합니다.

큐를 파이썬으로 작성해보겠습니다.

1. 클래스 Node 생성

# 클래스 Node 생성
class Node:
    
    # 초기화 함수를 통해 Node의 초기데이터값 설정
    def __init__(self, val, next):
    
        # (노드이름).val로 접근하면 저장된 val값을 호출
        self.val = val
        # (노드이름)next로 접근하면 저장된 next(노드)를 호출
        self.next = next

노드를 선언하는 이유는 Single Linked List의 형태에 함수를 추가하여 큐의 자료구조를 구현하기 위함입니다.

2. 클래스 Queue생성

# 클래스 Queue 생성
class Queue:
    
    # 초기화 함수를 통해 Queue의 초기 데이터값 설정
    def __init__(self):
        # 초기 self.front가 없음을 설정
        self.front = None

큐를 구현할 때, 비어있는 형태로 구현하고 self.front 값을 여러가지 함수에서 호출하여 안의 노드 값을 넣거나, 빼거나, 확인하는 용도로 사용합니다.

3. 클래스 안에 함수 선언 - 1 : push

    def push(self, val):
        # 만약 self.front가 None이라면(안에 요소가 없다면)
        if self.front is None:
            # 새로운 노드를 self.front로 저장
            self.front = Node(val, None)
            return
        
        # self.top이 있다면, node에 self.front를 저장
        node = self.front
        
        # 큐 안의 node 값을 node.next값으로 갱신 하며, 노드를 하나씩 순회
        while node and node.next:
            # node 값을 node.next값으로 갱신
            node = node.next
            
        # 더 이상 node.next가 없다면(마지막 노드가 node에 저장됐다면)
        # node.next에 새로운 노드 값을 저장
        node.next = Node(val, None)

큐 안에 새로운 요소를 넣는 푸쉬 함수입니다. 안에 요소가 없으면 self.front 값으로 요소를 저장합니다. 안에 다른 요소가 있다면, 출구와 가장 가까운 요소(self.front)부터 차례로 순회하여 마지막 요소의 next값으로 가리켜 줍니다.

4. 클래스 안에 함수 선언 - 2 : pop

    def pop(self):
        # 만약 self.front가 없으면
        if self.front is None:
            # 아무것도 반환하지 않음
            return None
            
        # self.front를 갱신하기 전에, node에 현재 self.front 값을 저장.
        node = self.front
        # self.front 값을 바로 다음 요소로 갱신
        self.front = self.front.next
        # node에 저장한 기존 self.front값을 반환
        return node

5. 클래스 안에 함수 선언 - 3 : is_empty

    def is_empty(self):
        # self.front가 가리키고 있는 것이 있으면 True, 없으면 False를 반환하라
        return self.front is None

큐의 특징

선입선출(FIFO) : pop으로 요소를 꺼내면 먼저 들어온 값이 가장 먼저 반환되고, 나중에 들어온 값은 나중에 반환됩니다.
시간복잡도
- Insertion O(1)
- Deletion O(1)
- Search O(n)
삭제 시에는 출구, 삽입시에는 입구에 데이터를 처리하기 때문에 시간복잡도는 O(1)입니다. 하지만 특정 위치에 값을 삽입, 삭제, 검색하는 경우 O(n)의 시간복잡도를 가집니다.