큐 구현

큐

큐 설명

구현

큐 또한 스택과 마찬가지로 자료를 입출력하는 자료구조이기 때문에 링크드리스트를 활용한 방식으로 구현했다.

노드

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

스택 구현에 사용할 노드이다.
노드는 데이터와 다음 노드를 가리키는 포인터로 구성되어 있다.

enqueue

    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return
        self.head.next = new_node
        self.tail = new_node

큐에 자료를 삽입하는 메서드이다.
구현 방식은

1. value를 사용해 새로운 값을 담은 노드를 생성
   • 큐가 비어있는 경우
     • 새로운 노드를 head, tail 노드로 지정한다.
2. 현재 head 노드의 다음 노드를 새로운 노드로 지정한다.
3. tail 노드를 새로운 노드로 지정한다.

dequeue

    def dequeue(self):
        if self.is_empty():
            return 'Queue is empty'
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

큐의 head 노드의 데이터를 추출하는 메서드이다.

1. 큐가 비어있는지 확인한다.
2. head 노드를 다른 변수에 저장한다.
3. head 노드를 현재 head 노드의 다음 노드로 변경한다.
4. 1에서 저장한 노드의 데이터를 출력한다.

큐가 비어있는 경우 리턴할 데이터가 없기 때문에 큐가 비어있다는 정보를 리턴하도록 설정했다.
링크드리스트의 특징을 활용해 head를 변경하여 기존 head 노드의 데이터를 링크드리스트에서 제거하고 리턴하도록 구현했다.

peek

    def peek(self):
        if self.is_empty():
            return "Queue is empty"
        return self.head.data

큐의 head노드의 데이터를 확인하는 메서드이다.

1. 큐가 비어있는지 확인한다.
2. head 노드의 데이터를 리턴한다.

dequeue와 마찬가지로 비어있는 경우 값을 확인할 수 없기 때문에 큐가 비어있다는 정보를 리턴하도록 설정했다.