[Data Structure] Linear - (6) Queue

---

---

큐(Queue)

 선입선출(First-In First-Out, FIFO)특징을 가진 자료구조다. 즉, 가장 나중에 들어온 자료가 가장 먼저 나가도록 되어 있다.

 

큐 구조

---

커스텀 큐 구현

 싱글리 링크드 리스트로 큐를 구현해보자. 스택과 차이점은 한쪽 끝에서 연산이 이루어 지는 게 아니라 양쪽에서 각각 삽입과 인출이 일어난다는 것이다. 따라서 레퍼런스를 front와 rear로 두고 rear측에 새로운 노드가 삽입되고, front측에서 노드가 나가는 형태로 구현을 해야 한다.

 

 

from typing import Iterable, Optional


class Node:
    """싱글리 링크드 리스트 노드"""

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

    def __repr__(self) -> str:
        return str(self.data)


class CustomQueue:
    def __init__(self, arr: Optional[Iterable] = None) -> None:
        self.front = None
        self.rear = None

        # arr가 있을 경우
        if arr:
            for i in arr:
                self.enqueue(i)

    def enqueue(self, __x):

        new_node = Node(__x)

        if not self.rear:
            self.front = self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if not self.front:
            raise IndexError("큐가 비어있습니다.")

        __x = self.front.data
        self.front = self.front.next

        if not self.front:
            self.rear = None

        return __x

    def __repr__(self) -> str:

        list_for_return = []
        iterator = self.front

        while iterator:
            list_for_return.append(str(iterator.data))
            iterator = iterator.next

        return "queue([" + ", ".join(list_for_return) + "])"

 

---

코드 리뷰

 

노드 클래스

 

class Node:
    """싱글리 링크드 리스트 노드"""

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

    def __repr__(self) -> str:
        return str(self.data)

 

 스택과 마찬가지로 기본적인 싱글리 링크드 리스트 노드를 만들어 주었다. 

 

 

커스텀 큐 클래스

 

class CustomQueue:
    def __init__(self, arr: Optional[Iterable] = None) -> None:
        self.front = None
        self.rear = None

        # arr가 있을 경우
        if arr:
            for i in arr:
                self.enqueue(i)

 

 커스텀 큐 클래스는 front와 rear를 갖는다. rear로 새로운 노드가 삽입되고 front로 노드가 인출된다.

 

 

 

Enqueue 메소드

 

def enqueue(self, __x):
    new_node = Node(__x)

    if not self.front:
        self.front = self.rear = new_node
    else:
        self.rear.next = new_node
        self.rear = new_node

 

 rear, 즉 들어오는 쪽에 데이터가 없다면 큐가 비어있다는 뜻이므로 front와 rear의 레퍼런스가 둘다 새로운 노드를 가리키도록 하고, 만약 rear가 어떤 노드를 가리키고 있다면 그 노드의 next속성이 새로운 노드를 가리키도록 하고, rear또한 새로운 노드를 가리키도록 한다.

 

 

 

Dequeue 메소드

def dequeue(self):
    if not self.front:
        raise IndexError("큐가 비어있습니다.")

    __x = self.front.data
    self.front = self.front.next

    if not self.front:
        self.rear = None

 

 Dequeue에서는 큐가 비어있는지 검사한 후에, front가 다음 노드를 가리키도록 한다. 이때 다음 노드가 비어 있다면 큐가 전부 비어있는 상태이므로 rear또한 None으로 설정해준다.

 

 

---

테스트

 

custom_queue = CustomQueue([1, 2, 3, 4, 5])
print(custom_queue)

custom_queue.enqueue(100)
custom_queue.enqueue(300)
print(custom_queue)

print(custom_queue.dequeue())
print(custom_queue.dequeue())

print(custom_queue)

queue([1, 2, 3, 4, 5])
queue([1, 2, 3, 4, 5, 100, 300])
1
2
queue([3, 4, 5, 100, 300])

 

 왼쪽이 front, 오른쪽이 rear다. 따라서 새로운 데이터가 삽입되면 오른쪽에 새로운 값들이 추가되고, dequeue 메소드로 데이터가 나갈 때는 왼쪽에서 나가게 된다.

 

 스택과 같이 파이썬의 List 혹은 Deque를 쓰도록 하자.