연결 리스트 기반 큐 (Linked List-based Queue)

큐(Queue)는 FIFO(First In, First Out) 구조를 가지는 자료 구조로, 먼저 삽입된 요소가 먼저 제거됩니다. 큐는 배열(Array) 또는 연결 리스트(Linked List)로 구현할 수 있습니다. 연결 리스트 기반 큐는 큐의 요소를 노드(Node)로 관리하여 동적으로 메모리를 할당합니다. 이 방법은 큐의 크기가 가변적이어서 메모리 사용이 효율적입니다.

연결 리스트 기반 큐의 구조

1. 노드 (Node): 큐의 각 요소를 나타내는 기본 단위로, 데이터와 다음 노드를 가리키는 포인터를 포함합니다.
   • 데이터 (Data): 노드가 저장하는 값.
   • 다음 (Next): 다음 노드를 가리키는 포인터.
2. 큐 (Queue): 연결 리스트의 헤드(Front)와 테일(Rear) 노드를 가리키는 포인터를 포함합니다.
   • 프론트 (Front): 큐의 첫 번째 노드를 가리키는 포인터.
   • 리어 (Rear): 큐의 마지막 노드를 가리키는 포인터.

주요 연산

1. 삽입 (Enqueue): 큐의 마지막에 새로운 노드를 추가합니다.
2. 삭제 (Dequeue): 큐의 첫 번째 노드를 제거하고 그 노드의 데이터를 반환합니다.
3. 프론트 (Front): 큐의 첫 번째 노드의 데이터를 반환합니다. 노드를 제거하지 않습니다.
4. 리어 (Rear): 큐의 마지막 노드의 데이터를 반환합니다. 노드를 제거하지 않습니다.
5. 비어 있는지 확인 (IsEmpty): 큐가 비어 있는지 확인합니다.
6. 크기 확인 (Size): 큐에 있는 노드의 개수를 반환합니다.

연결 리스트 기반 큐의 장단점

장점:

1. 동적 크기 조정: 큐의 크기를 동적으로 조정할 수 있어 메모리 사용이 효율적입니다.
2. 빠른 삽입과 삭제: 새로운 노드를 추가하거나 제거하는 연산이 O(1) 시간 복잡도를 가집니다.

단점:

1. 추가 메모리 사용: 각 노드가 데이터 외에도 다음 노드를 가리키는 포인터를 저장해야 하므로 추가 메모리를 사용합니다.
2. 임의 접근 불가: 배열 기반 큐에 비해 임의의 인덱스로 접근하는 것이 불가능합니다.

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

class LinkedListBasedQueue:
    def __init__(self) -> None:
        self.front = None
        self.rear = None
        self.size = 0

    def enqueue(self, data) -> None:
        new_node = Node(data)
        if self.is_empty():
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self.size += 1

    def dequeue(self):
        if self.is_empty():
            return None

        delete_data = self.front
        self.front = self.front.next
        if self.front is None:
            self.rear = None

        self.size -= 1

        return delete_data.data

    def peek_front(self):
        return self.front.data

    def peek_rear(self):
        return self.rear.data

    def is_empty(self) -> bool:
        return self.size == 0

    def get_size(self) -> int:
        return self.size

    def display(self) -> None:
        if self.is_empty():
            print("Queue is empty")
            return
        cur = self.front
        while cur:
            print(cur.data, "->", end=" ")
            cur = cur.next
        print("None")

queue = LinkedListBasedQueue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.display()  # Output: 10 -> 20 -> 30 -> None
print(queue.dequeue())  # Output: 10
print(queue.peek_front())  # Output: 20
print(queue.peek_rear())  # Output: 30
print(queue.is_empty())  # Output: False
print(queue.get_size())  # Output: 2
queue.display()  # Output: 20 -> 30 -> None

주요 연산 설명

1. enqueue: 새로운 노드를 생성하여 큐의 마지막에 추가합니다. rear가 새로운 노드를 가리키도록 업데이트하고, 큐의 크기를 증가시킵니다.
2. dequeue: 큐의 첫 번째 노드를 제거하고 그 노드의 데이터를 반환합니다. front를 다음 노드로 업데이트하고, 큐의 크기를 감소시킵니다. 큐가 비어 있으면 rear를 None으로 설정합니다.
3. peek_front: 큐의 첫 번째 노드의 데이터를 반환합니다. 큐가 비어 있으면 None을 반환합니다.
4. peek_rear: 큐의 마지막 노드의 데이터를 반환합니다. 큐가 비어 있으면 None을 반환합니다.
5. is_empty: 큐가 비어 있는지 확인합니다. 큐의 크기가 0인지 확인하여 반환합니다.
6. get_size: 큐의 크기를 반환합니다.
7. display: 현재 노드가 None이 될 때까지 리스트를 순회하면서 각 노드의 데이터를 출력합니다. 마지막에 "None"을 출력합니다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms