Queue

 

큐는 First In Last Out의 구조를 가진 스택과 반대되는 개념으로, First In First Out의 구조를 가진 자료구조이다.

 

티켓을 끊을 때 가장 먼저 기다린 사람이 가장 먼저 티켓을 끊고 나가는 것처럼 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있을 때 사용되는 자료구조이다. 절미 거두하고 구현한 코드를 보겠다!

 

class Node:
    def __init__(self, data, next):
        self.data = data            # 노드 객체를 생성하면 자동으로 실행되는 생성자 메서드(매개 변수로 data와 next를 받고 있다!)
        self.next = next

class Queue:
    def __init__(self):
        self.front = None           # Queue 객체를 생성하면 자동으로 front를 None으로 초기화한다.

    def push(self, value):
        if not self.front:                  # front에 값이 없다면 front에 노드를 넣는다.
            self.front = Node(value, None)
            return

        node = self.front  # front에 값이 있다면 node에 front를 넣는다.
        while node.next:
            node = node.next    # next에 저장된 값(노드가 가리키는 다음 노드가 있으면 next를 노드에 넣어줌) // 앞의 노드로 이동하기 위한 동작
        node.next = Node(value, None)   # 반복문이 끝나고 next에 push할 노드를 넣는다.

    def pop(self):          # 가장 앞 요소를 제거하는 pop 함수
        if not self.front:  # front에 값이 없으면 None 반환
            return None

        node = self.front   # 값이 있다면 front에 노드를 넣는다.
        self.front = self.front.next    # next가 가리키는 것을 앞으로 당긴다.
        return node.data    # pop을 할 데이터를 반환

    def is_empty(self):     # 큐에 노드가 없으면 True 있으면 False
        return self.front is None

 

 

🧑‍💻

이렇게 큐를 구현해보았다. 하지만 파이썬에는 양방향 큐라고 불리기도 하는 'Deque'라는 것이 있다. 선입선출(First In First Out)의 방식을 가진 큐와 달리 이름에서 알 수 있듯이 데큐(Deque)는 양방향에서 삽입과 삭제가 자유롭다. 그렇기에 데큐는 큐는 물론이고 스택(리스트)의 역할도 동시에 하고 있음을 알 수 있다. 데큐는 리스트보다 속도와 성능면에서 훨씬 빠르기 때문에 파이썬에서 제공하는 데큐를 쓰면 될 거 같다!