[자료구조] 큐 구현: 배열 이용방법(feat. enqueue, dequeue, peek 알고리즘), queue가 가지는 한계점

[큐 구현: 배열 이용방법]

 

1. 개요: 큐(Queue)는 데이터를 선입선출(FIFO, First-In-First-Out)의 원칙에 따라 처리하는 자료구조로, 배열을 이용해 구현할 수 있다. 이 보고서에서는 배열을 활용하여 큐를 구현하는 방법과 그 한계점에 대해 다룹니다.

 

2. 구현 알고리즘:

 

·       -  Enqueue (삽입):

·        큐의 끝에 새로운 원소를 추가하는 작업이다.

·        배열의 끝에 원소를 추가하고, 큐의 끝을 업데이트한다.

·        - Dequeue (삭제):

·        큐의 맨 앞에서 원소를 제거하는 작업이다. 배열의 맨 앞에서 원소를 제거하고, 큐의 시작 지점을 업데이트한다.

·        - Peek (참조):

·        큐의 맨 앞에 있는 원소를 조회하는 작업이다. 배열의 시작 부분에 위치한 원소를 반환한다.

3. 예시 코드:

 

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        else:
            return None

    def peek(self):
        if not self.is_empty():
            return self.items[0]
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

 

4. 한계점:

 

·        - 고정 크기의 배열 사용:

·        배열의 크기가 고정되어 있기 때문에, 큐의 원소 수가 배열 크기를 초과하면 오버플로우가 발생할 수 있다.

·        - 삭제 작업의 비효율성:

·        Dequeue 작업 시, 배열의 맨 앞에서 원소를 제거하는 과정에서 배열의 모든 원소를 앞으로 이동시켜야 하므로 연산           이 비효율적이다.

·        - 메모리 공간 낭비:

·        큐에 계속적으로 삽입 및 삭제 작업이 이루어질 경우, 배열의 크기를 동적으로 조절하지 않으면 메모리 공간이 낭비            될 수 있다.

 

5. 결론: 배열을 이용한 큐 구현은 간단하고 직관적이지만, 고정 크기 및 삭제 작업의 비효율성 등의 한계점이 존재한다. 실제 사용 환경에 따라 적합한 자료구조를 선택하는 것이 중요하다