Queue 기초

Queue를 이해하기 위해 stack을 알아야한다.

stack은 FILO이다.

Queue는 FIFO이다.

 

데이터를 Queue에 넣는 행동 enqueue 빼는 행동 dequeue이다.

enqueue, dequeue모두 O(n) time complexity를 갖는다.

 

이를 구현하기 위해 doubly linked list를 사용하면된다.(LRU cache 참고)

 

# FIFO policy Queue를 implementation 하여라

# 함수 : enqueue() dequeue()

class QueueNode:
    def __init__(self, val:int) -> None:
        self.val = val
        self.left = None
        self.right = None
        
class Queue:
    def __init__(self) -> None:
        self.head = QueueNode(0)
        self.tail = QueueNode(0)
        self.head.right = self.tail
        self.tail.left = self.head

    def enqueue(self, val:int)->None:
        new_node = QueueNode(val)
        last_node = self.tail.left

        last_node.right = new_node
        new_node.left = last_node

        new_node.right = self.tail
        self.tail.left = new_node

    def dequeue(self) -> int:
        first_node = self.head.right
        if first_node == self.tail:
            raise RuntimeError('No Elem')

        value = first_node.val
        second_node = first_node.right
        self.head.right = second_node
        second_node.left = self.head

        return value

queue = Queue()
queue.enqueue(1)
queue.enqueue(3)
queue.enqueue(5)
queue.enqueue(7)
queue.enqueue(9)

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

 

참조 : (3) 코딩테스트, 기초, Queue 소개 - YouTube