큐(Queue)는 FIFO(First In, First Out) 구조를 가지는 자료 구조로, 먼저 삽입된 요소가 먼저 제거됩니다. 큐는 배열(Array) 또는 연결 리스트(Linked List)로 구현할 수 있습니다. 연결 리스트 기반 큐는 큐의 요소를 노드(Node)로 관리하여 동적으로 메모리를 할당합니다. 이 방법은 큐의 크기가 가변적이어서 메모리 사용이 효율적입니다.
연결 리스트 기반 큐의 구조
- 노드 (Node): 큐의 각 요소를 나타내는 기본 단위로, 데이터와 다음 노드를 가리키는 포인터를 포함합니다.
- 데이터 (Data): 노드가 저장하는 값.
- 다음 (Next): 다음 노드를 가리키는 포인터.
- 큐 (Queue): 연결 리스트의 헤드(Front)와 테일(Rear) 노드를 가리키는 포인터를 포함합니다.
- 프론트 (Front): 큐의 첫 번째 노드를 가리키는 포인터.
- 리어 (Rear): 큐의 마지막 노드를 가리키는 포인터.
주요 연산
- 삽입 (Enqueue): 큐의 마지막에 새로운 노드를 추가합니다.
- 삭제 (Dequeue): 큐의 첫 번째 노드를 제거하고 그 노드의 데이터를 반환합니다.
- 프론트 (Front): 큐의 첫 번째 노드의 데이터를 반환합니다. 노드를 제거하지 않습니다.
- 리어 (Rear): 큐의 마지막 노드의 데이터를 반환합니다. 노드를 제거하지 않습니다.
- 비어 있는지 확인 (IsEmpty): 큐가 비어 있는지 확인합니다.
- 크기 확인 (Size): 큐에 있는 노드의 개수를 반환합니다.
연결 리스트 기반 큐의 장단점
장점:
- 동적 크기 조정: 큐의 크기를 동적으로 조정할 수 있어 메모리 사용이 효율적입니다.
- 빠른 삽입과 삭제: 새로운 노드를 추가하거나 제거하는 연산이 O(1) 시간 복잡도를 가집니다.
단점:
- 추가 메모리 사용: 각 노드가 데이터 외에도 다음 노드를 가리키는 포인터를 저장해야 하므로 추가 메모리를 사용합니다.
- 임의 접근 불가: 배열 기반 큐에 비해 임의의 인덱스로 접근하는 것이 불가능합니다.
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
주요 연산 설명
- enqueue: 새로운 노드를 생성하여 큐의 마지막에 추가합니다. rear가 새로운 노드를 가리키도록 업데이트하고, 큐의 크기를 증가시킵니다.
- dequeue: 큐의 첫 번째 노드를 제거하고 그 노드의 데이터를 반환합니다. front를 다음 노드로 업데이트하고, 큐의 크기를 감소시킵니다. 큐가 비어 있으면 rear를 None으로 설정합니다.
- peek_front: 큐의 첫 번째 노드의 데이터를 반환합니다. 큐가 비어 있으면 None을 반환합니다.
- peek_rear: 큐의 마지막 노드의 데이터를 반환합니다. 큐가 비어 있으면 None을 반환합니다.
- is_empty: 큐가 비어 있는지 확인합니다. 큐의 크기가 0인지 확인하여 반환합니다.
- get_size: 큐의 크기를 반환합니다.
- display: 현재 노드가 None이 될 때까지 리스트를 순회하면서 각 노드의 데이터를 출력합니다. 마지막에 "None"을 출력합니다.
모든 코드는 github에 저장되어 있습니다.
https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms
728x90
'Data structure & Algorithms study' 카테고리의 다른 글
이진 탐색 트리 (Binary Search Tree) (0) | 2024.07.27 |
---|---|
이진 트리 (Binary Tree) (0) | 2024.07.06 |
연결 리스트 기반 스택 (Linked List-based Stack) (0) | 2024.06.30 |
원형 연결 리스트 (Circular Linked List) (0) | 2024.06.29 |
이중 연결 리스트 (Doubly Linked List) (0) | 2024.06.11 |