<코딩테스트 Level1> 9일차 - 큐

📌 큐

스택과 함께 기본적인 자료구조를 담당하는 큐를 알아보자.

일반적으로 큐는 스택과 함께 묶어서 학습한다. 왜일까 ❓

지난 번에 스택이 후입선출이라고 배웠었다.
큐는 이와 반대로 선입선출의 특성을 갖는 자료구조이다.

즉, 데이터를 삽입한 순서대로 데이터를 추출한다.

📌 큐 구현

큐 또한 스택과 마찬가지로 데이터 삽입과 데이터 추출 두 가지 변수가 필요하다.
데이터 삽입은 큐가 가득 찼는지 확인해야 하고, 데이터 추출은 큐가 비어있는지 확인해야 한다.

다만, 큐와 스택은 세부적인 코드 내용에서 조금 차이를 보인다.
스택에선 마지막 입력된 데이터의 이치를 나타내는 top 변수를 사용했었지만, 큐는 최근 삽입된 데이터 위치와 가장 오래된 데이터 위치를 기억해야 한다.

삽입은 최근 삽입된 데이터 위치가 필요하고,
추출은 가장 오래된 데이터의 위치가 필요하다.

MAX_QUEUE_SIZE = 5

class Queue:
    def __init__(self):
        self.arr = [None] * MAX_QUEUE_SIZE
        # head : 가장 오래된 데이터의 위치
        # tail : 가장 최근 추가된 데이터의 위치
        self.head = -1
        self.tail = -1

    def is_empty(self):
        if self.head == self.tail:
            return True
        return False

    def is_full(self):
        if self.tail >= MAX_QUEUE_SIZE - 1:
            return True
        return False

    def enqueue(self, item):
        if self.is_full():
            print("큐에 더이상 데이터를 넣을 수 없습니다.")
        else:
            self.tail += 1
            self.arr[self.tail] = item

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어있습니다.")
            return None;
        else:
            self.head += 1
            return self.arr[self.head]

queue = Queue()
queue.enqueue("data 1")
queue.enqueue("data 2")
queue.enqueue("data 3")

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

--

📌 선형 큐의 문제점

👉 실행 코드

enqueue(1);
enqueue(2);
enqueue(3);
enqueue(4);
enqueue(5);

dequeue();
dequeue();
dequeue();
dequeue();
dequeue();

enqueue(1);
enqueue(2);
enqueue(3);

👉 실행 결과

큐에 더이상 데이터를 넣을 수 없습니다.
큐에 더이상 데이터를 넣을 수 없습니다.
큐에 더이상 데이터를 넣을 수 없습니다.

분명 enqueue를 5번, dequeue를 5번 실행해서 큐가 비어있는 상태이지만 enuqueue를 다시 실행하면 큐에 데이터를 더 이상 넣을 수 없다는 문구가 출력된다.

큐를 원형으로 제작하게 되면 데이터를 아무리 삽입하더라도 다시 제자리로 돌아오기 때문에, 큐가 가득 차지 않는 이상 데이터를 계속해서 삽입할 수 있다.

이렇게 원형으로 구성된 큐를 원형 큐라고 한다.

📌 원형 큐

원형 큐는 큐를 원형으로 제작한 자료구조이다.

head, tail이 배열의 마지막 인덱스에 도착한다면 다시 배열의 첫 부분으로 돌려주어 마치 큐가 원형으로 구성된 것처럼 보인다.

얘룰 둘오 큐의 크기가 5라고 가정하자.
그럼, tail과 head의 값이 4가 넘어가면 오류가 발생한다.
큐를 구성하는 배열은 0부터 4까지의 인덱스만 존재하기 때문이다.

그럼 **tail이 0부터 4일 땐 그대로 값을 유지하고, 5일 땐 0으로 되돌려 줘야 한다.

모듈 연산자 (%)를 사용한다.
trail, head를 큐의 크기로 나눈 나머지로 변경해주는 것이다.

📌 원형 큐 구현

MAX_QUEUE_SIZE = 5

class Queue:
    def __init__(self):
        self.arr = [None] * MAX_QUEUE_SIZE
        # head : 가장 오래된 데이터의 위치
        # tail : 가장 최근 추가된 데이터의 위치
        self.head = 0
        self.tail = 0

    def is_empty(self):
        if self.head == self.tail:
            return True
        return False

    def is_full(self):
        if (self.tail + 1) % MAX_QUEUE_SIZE == self.head:
            return True
        return False

    def enqueue(self, item):
        if self.is_full():
            print("큐에 더이상 데이터를 넣을 수 없습니다.")
        else:
            self.tail = (self.tail + 1) % MAX_QUEUE_SIZE
            self.arr[self.tail] = item

    def dequeue(self):
        if self.is_empty():
            print("큐가 비어있습니다.")
        else:
            self.head = (self.head + 1) % MAX_QUEUE_SIZE
            return self.arr[self.head]

queue = Queue()
queue.enqueue("data 1")
queue.enqueue("data 2")
queue.enqueue("data 3")

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

queue.enqueue("data 4")
queue.enqueue("data 5")
queue.enqueue("data 6")

print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

이제 tail과 head를 다시 배열의 첫 인덱스로 이동 시키기 때문에 공간만 충분하다면 계속해서 데이터를 넣을 수 있다.

📌 큐 사용

큐는 실제로 어디에 사용될까 ❓

BFS, 너비 우선 탐색에서 처리할 노드 리스트를 저장하는 용도로 큐를 사용한다.

다만 큐 자체는 구현하기 쉽기 때문에 알고리즘에서 큐를 단독으로 사용하는 문제는 잘 출제되지 않는다.