큐 (Queue)

큐 자료 구조 (Queue Data Structure)

큐는 FIFO(First In, First Out) 구조를 따르는 자료 구조이다. 즉, 먼저 삽입된 데이터가 먼저 제거된다. 큐는 일상 생활에서 쉽게 찾을 수 있다. 예를 들어, 은행의 대기 줄이나 프린터 작업 대기열이 큐의 예이다. 큐는 한쪽 끝에서 삽입 연산이 이루어지고 반대쪽 끝에서 제거 연산이 이루어지는 특성을 갖는다.

큐의 주요 연산

1. Enqueue: 큐의 끝(뒤쪽)에 새로운 요소를 추가한다.
2. Dequeue: 큐의 앞(앞쪽)에 있는 요소를 제거하고 반환한다.
3. Peek/Front: 큐의 앞에 있는 요소를 제거하지 않고 반환한다.
4. isEmpty: 큐가 비어 있는지 확인한다.
5. Size: 큐의 크기를 반환한다.

큐의 동작

• Enqueue 연산: 큐의 끝에 새로운 요소를 추가한다. 만약 큐가 배열로 구현되어 있고 이미 가득 차 있는 경우, 오버플로우(Overflow)가 발생할 수 있다.
• Dequeue 연산: 큐의 앞에 있는 요소를 제거하고 반환한다. 만약 큐가 비어 있는 경우, 언더플로우(Underflow)가 발생할 수 있다.
• Peek 연산: 큐의 앞에 있는 요소를 확인한다. 요소를 제거하지 않기 때문에 큐의 상태는 변하지 않는다.
• isEmpty 연산: 큐가 비어 있는지 확인한다. 큐가 비어 있으면 True를 반환하고, 그렇지 않으면 **False**를 반환한다.
• Size 연산: 큐의 크기를 반환한다. 즉, 큐에 있는 요소의 개수를 반환한다.

배열 기반 큐

• 장점: 구현이 간단하고, 인덱스를 통해 요소에 빠르게 접근할 수 있다.
• 단점: 크기가 고정되어 있어, 크기를 초과하면 오버플로우가 발생할 수 있다. 또한, 요소를 제거할 때마다 배열을 이동시켜야 하기 때문에 효율성이 떨어질 수 있다.

큐의 시각적 예시

Queue (Front at left, Rear at right):

Enqueue 1:
| 1 |

Enqueue 2:
| 1 | 2 |

Enqueue 3:
| 1 | 2 | 3 |

Dequeue:
| 2 | 3 | (returns 1)

Peek:
| 2 | 3 | (returns 2)

큐의 사용 예

1. 프린터 대기열: 인쇄 작업을 큐에 저장하고, 순서대로 처리한다.
2. 프로세스 관리: 운영 체제에서 여러 프로세스가 실행 대기열에 저장되고, 순서대로 CPU에 할당된다.
3. 메시지 큐: 여러 프로세스 간의 통신을 위해 메시지를 저장하고, 순서대로 처리한다.
4. 폭넓은 그래프 탐색 (BFS): 너비 우선 탐색(BFS) 알고리즘에서 큐를 사용하여 그래프를 탐색한다.
5. 이벤트 처리 시스템: 이벤트를 큐에 저장하고, 순서대로 처리한다.

class Queue:
    def __init__(self):
        self._values = []

    def enqueue(self, value):
        self._values.append(value)

    def dequeue(self):
        if self.isEmpty():
            return None
        else:
            return self._values.pop(0)

    def front(self):
        if self.isEmpty():
            return None
        else:
            return self._values[0]

    def isEmpty(self) -> bool:
        if len(self._values) == 0:
            return True
        else:
            return False

    def size(self) -> int:
        return len(self._values)

    def __str__(self) -> str:
        return f"Queue: {self._values}"

queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue)  # Queue: [1, 2, 3]
print(queue.dequeue())  # 1
print(queue.front())  # 2
print(queue.isEmpty())  # False
print(queue.size())  # 2

 

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

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