자료구조/Python3) 연결 리스트로 큐 구현하기

Queue는 선입선출 (First In First Out) 형식의 자료구조이다. 브라우저가 Javascript를 동작시킬 때 api콜, setTimeout 등 비동기로 처리할 수 있는 함수들은 콜 스택에 쌓지 않고 web api에서 비동기로 처리한 후 처리 결과와 함께 콜백 함수를 테스크 큐에 넣는다. 이 때 테스크 큐가 큐 구조로 이루어져 선입선출 방식으로 작동한다. python에서는 collections라는 라이브러리에 deque 모듈을 임포트해서 사용하면 간단하지만 원리를 이해하기 위해 연결리스트로 구현해보았다. 

class Node 

연결리스트의 노드는 각 노드의 값과 다음 노드를 가리키는 포인터로 이루어져있다. 

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

class Queue

class Queue:
    def __init__(self) -> None:
        self.head = None
        self.tail = None

큐는 head와 tail 노드를 가지고 있다. 나머지 노드들은 각 노드의 next 포인터로 연결되어 있다. 

enqueue(data)

큐가 비어있으면 head와 tail은 초기화 상태 그대로 None이다. 비어있다면 새로 추가한 노드가 head와 tail이다.

비어있지 않다면 tail의 다음 노드로 새로운 노드가 들어가야한다. 그러므로 tail의 next 노드로 새로운 노드를 넣고, 큐의 tail을 새로 넣은 노드로 갱신해준다. 

...
    def enqueue(self, data) -> None:
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else :
            self.tail.next = new_node
            self.tail = self.tail.next
  ...

dequeue()

큐가 비어있다면 dequeue할 데이터가 없다. 있는 경우 head에서 데이터를 꺼내야 한다. head 노드의 데이터를 꺼내고 head의 next 노드를 새로운 Head로 갱신해준다. 꺼낸 Head에 저장된 값을 반환해주어야 한다. 이때, 큐에 head 노드 하나 뿐인 상태였다면 head노드를 꺼냉 후 남은 노드가 없다. 이 경우 head와 tail을 모두 초기화하여 완전히 빈 상태로 만들어주어야 한다. 

...
    def dequeue(self) -> int or None:
        if self.head == None:
            print("Queue is Empty")
            return None
        else:
            v = self.head.data
            self.head = self.head.next 

        if self.head == None:
            self.tail = None
        return v
...

전체 

아래는 큐를 연결리스트로 구현한 코드 전체이다. 큐를 프린트하는 메소드와 큐의 사이즈를 반환하는 메소드가 추가로 구현되어 있다. 

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

class Queue:
    def __init__(self) -> None:
        self.head = None
        self.tail = None
    
    def enqueue(self, data) -> None:
        new_node = Node(data)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else :
            self.tail.next = new_node
            self.tail = self.tail.next
        
    def dequeue(self) -> int or None:
        if self.head == None:
            print("Queue is Empty")
            return None
        else:
            v = self.head.data
            self.head = self.head.next 

        if self.head == None:
            self.tail = None
        return v
        
    def print_queue(self) -> None:
        current_node = self.head
        string = ""
        while current_node:
            string += str(current_node.data)
            if current_node.next:
                string += " -> "
            current_node = current_node.next
        print(string)

    def queue_size(self) -> int:
        current_node = self.head
        size = 0
        while current_node:
            current_node = current_node.next
            size += 1
        return size