Queue (큐)

Queue 란?

큐는 먼저 입력된 데이터를 가장 먼저 꺼낼 수 있는 자료구조입니다. 이러한 동작 원리는 선입선출(FIFO, First In First Out)이라고 합니다.
이때 큐에 데이터를 삽입하는 연산을 인큐(enqueue), 꺼내는 연산을 디큐(dequeue)라고 합니다.

Queue의 동작 원리

1. 초기에 빈 큐가 있습니다

2. 여기에 데이터 1을 enqueue하면 현재 큐는 [1]이 됩니다

3. 데이터 2를 enqueue하면 현재 큐는 [1, 2]가 됩니다

4. 마지막으로 dequeue를 하면 처음으로 enqueue한 데이터 1이 빠져나가고 큐는 [1]이 됩니다.

Queue의 ADT

큐에는 enqueue, dequeue, isFull(가득 찼는지), isEmpty(비었는지) 같은 연산을 정의해야 합니다. 그리고 큐는 데이터가 삽입되는 뒷쪽 위치를 저장하는 rear와 데이터가 추출되는 앞쪽 위치를 저장하는 front도 있어야 합니다.

• boolean isFull() : 큐가 가득 차 있는지 확인하고 boolean값을 반환

• boolean isEmpty() : 큐에 데이터가 없는지 확인하고 boolean값을 반환

• void enqueue(ItemType item) : 큐에 데이터를 추가

• ItemType dequeue() : 큐에서 데이터를 꺼내고, 그 데이터를 반환

• int front : 큐의 첫 데이터 위치

• int rear : 큐의 마지막 데이터 위치

• ItemType data[maxsize] : 큐의 데이터를 관리하는 배열 / 최대 maxsize개의 데이터를 관리

Queue 구현

위에 정의한 큐를 구현하면 다음과 같습니다. (Python)

queue = []  # 큐 리스트 초기화
max_size = 10  # 큐의 최대 크기

def isFull(queue):
    # 큐가 가득 찼는지 확인하는 함수
    return len(queue) == max_size

def isEmpty(queue):
    # 큐가 비어 있는지 확인하는 함수
    return len(queue) == 0

def enqueue(queue, item):
    # 큐에 데이터를 추가하는 함수
    if isFull(queue):
        print("큐가 가득 찼습니다.")
    else:
        queue.append(item)
        print("데이터가 추가되었습니다.")

def dequeue(queue):
    # 큐에서 데이터를 꺼내는 함수
    if isEmpty(queue):
        print("큐가 비어 있습니다.")
        return None
    else:
        return queue.pop(0)

마무리

최근 회사에서 일이 너무 바쁘다는 핑계로... 몇일동안 알고리즘을 못했는데.. 최소한 하루에 한문제는 꼭 풀도록 노력해야겠다..!