[자료구조] Queue

Queue

오늘은 큐에 대해 공부했다. 큐의 구현 방식에는 Linear Queue, Circular Queue, Double Ended Queue 등 다양한 방식이 있는데, 오늘은 Circular Queue의 구현을 집중적으로 다뤄볼 예정이다.  

큐는 후입선출 구조인 스택과는 다르게, 선입선출 구조를  가진 자료구조이다. 

선입선출 구조란?

영어로는 First In First Out, 줄여서 FIFO라고 부르기도 하며, 자료구조에 먼저 삽입된 데이터가 먼저 빠져나온다는 의미이다. 우리가 맛집 웨이팅을 할 때 대기줄이 먼저 온 사람부터 들어가는 구조와 같다! 

가장 기본적인 큐 자료구조는 리스트를 활용하여 구현한다. 리스트의 맨 앞부터 원소를 하나하나 쌓아나가고, 큐에서 원소를 삭제하면 가장 앞에 있는 원소부터 빠져나갈텐데, 삭제 연산을 진행할 때마다 맨 앞 원소를 실제로 지워버리면 매번 \(O(n)\) 만큼의 연산이 발생하기 때문에 오버헤드가 커진다. 이를 방지하기 위해 큐 자료구조는 큐의 맨 앞 위치를 나타내는 front와 맨 뒤 위치를 나타내는 rear 라는 변수를 두어 연산을 진행한다. 

큐의 기본적인 연산은 아래와 같다. 

• insert : 큐의 맨 뒤에 원소를 추가하는 연산. rear가 가리키는 위치에 원소를 삽입한다. 삽입 후에는 rear를 뒤로 이동시켜야 한다.
• delete : 큐의 맨 앞 원소를 삭제하는 연산.  실제로 원소가 삭제되지는 않고 front를 뒤로 한 칸 이동시켜 큐의 맨 앞 위치를 바꿔주는 식으로 구현한다. 
• peek : 큐의 맨 앞 원소를 출력한다. front가 가리키는 위치의 원소를 출력하는 것이다. 

원형 큐를 구현하기 전에 선형 큐의 동작 방식에 대해서 알아보자.

 

Linear Queue

 

먼저 선형 큐의 초기 상태는 위의 그림과 같다. 큐에는 아무 원소도 들어가 있지 않고, 현재 front와 rear가 같은 위치에 있는 것을 볼 수 있다. 여기에 원소 3을 삽입해 보자.

 

 

새로운 원소를 삽입하면 그림과 같이 rear가 있던 위치에 원소가 삽입되고, rear는 한 칸 뒤로 밀리게 된다. 

 

그림과 같이 몇 개의 원소를 더 삽입해 보았다. 이제 원소를 삭제해 보자. 가장 앞에 있는 원소인 3인 삭제가 될 것이고, front는 한 칸 뒤로 밀릴 것이다.

 

큐에서 원소의 삭제는 실제로 원소가 리스트에서 지워지는 것이 아니라, 큐의 front 값을 1 증가시킴으로써 큐의 맨 앞부분을 다음 원소로 바꿔주는 것이다. 

그림과 같이 Linear Queue의 형태로 구현을 하면 아주 큰 단점이 존재한다. 바로 삭제 연산을 진행하여 front가 뒤로 밀리게 되면, front의 앞부분은 더미 데이터를 그대로 저장하고 있어 메모리 효율이 떨어진다는 점이다. 후술 할 Circular Queue에서는 이러한 점을 보완하여 구현을 진행한다. 

 

Circular Queue

원형 큐 또한 기본적인 구현은 선형 큐와 같이 리스트를 활용한다. 다만 front와 rear 값을 모듈러 연산을 추가로 진행하여 front가 이미 지나갔던 인덱스의 값도 다시 활용할 수 있게끔 한다.

모듈러 연산이란?

모듈러 연산이란 나머지 연산을 말한다. a mod b는 a % b와 같다. 

Circular Queue를 그림으로 나타내면 아래와 같다. 

초기에는 선형 큐와 같이 front와 rear가 같은 값을 가지는 것을 볼 수 있다. 이제 본격적으로 Circular Queue를 구현하는 부분과 함께 살펴보자.

class CircleQueue:
    
    rear = 0
    front = 0
    capacity = 8
    queue = list()
    
    def __init__(self):
        self.rear = 0
        self.front = 0
        self.queue = [0 for _ in range(self.capacity)]
        
    def is_empty(self):
        return self.rear == self.front
    
    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front
        
    def peek(self):
        if self.is_empty():
            print("Empty")
            return
        return self.queue[self.front]

먼저 CircleQueue 클래스는 rear와 front, 큐의 크기를 나타내는 capacity, 원소를 담고 있는 리스트인 queue를 가지고 있다. capacity는 기본적으로 8로 설정해 주었으며, 큐가 꽉 차서 확장이 불가능한 경우 expand를 진행해 준다. 

 

위의 is_empty와 is_full 함수는 각각 큐가 비어있는지, 큐가 꽉 차있는지의 여부를 반환하는 함수이다. 만약 front와 rear가 가리키는 위치가 같다면 큐가 비어있는 것이고, rear를 시계방향으로 한 칸 옮겼을 때 front와 같아진다면 큐가 가득 찬 것이 될 것이다. 

 

이제 몇 가지 원소를 삽입해 보자. 원소를 총 여섯 개 삽입해서 결과가 다음과 같이 나왔다. 

rear는 여전히 다음 원소가 삽입될 위치를 가리키고 있다.

# class CircleQueue

    def delete(self):
        if self.is_empty():
            print("Empty")
            return
        elem = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        return elem

이제 데이터를 세 개 정도 삭제해 보자. 삭제한 후의 그림은 다음과 같다.

 

Linear Queue와 같이 실제 원소가 삭제되는 것이 아니라 front의 위치만 바뀌는 것을 볼 수 있다. 

이제 앞의 Linear Queue와 가장 큰 차이점을 보이는 부분인데, 여기서 원소를 네 번 더 삽입하는 과정을 생각해 보자. 

 

네 개의 원소를  다 삽입하기 전에 두 개의 원소를 삽입하면 rear가 큐의 마지막 인덱스까지 가게 된다. 이때 rear를 한 칸 더 옮겨줘야 하는데, 여기서 모듈러 연산이 활용된다. 일단 코드로 먼저 살펴보자. 

# class CircleQueue

    def insert(self, x):
        self.queue[self.rear] = x
        if self.is_full():
            self._expand()
        self.rear = (self.rear + 1) % self.capacity

rear 위치에 x를 먼저 삽입하고, rear를 시계방향으로 옮겨주는 연산에 capacity로 나눈 나머지를 활용하는 것을 볼 수 있다. 이를 통해 rear+1의 값이 리스트의 인덱스 범위를 벗어나도 이후 모듈러 연산을 통해 리스트의 맨 앞부분으로 옮겨줄 수 있게 된다. 이를 통해 Linear Queue에서 front가 이미 지나간 부분을 다시 활용하지 못하는 단점을 보완할 수 있다!

 

이 모듈러 연산 때문에 현재 큐에 들어있는 원소의 수를 계산하는 방법이 Linear Queue 보다 살짝 복잡해진다. Linear Queue에서 큐에 들어있는 원소의 개수를 확인하기 위해서는 rear에서 front를 빼기만 하면 구할 수 있었다. 반면에 Circular Queue의 경우에는 rear가 front보다 작아질 수도 있으므로 Linear Queue와 같은 방식으로 원소의 개수를 구하는 것이 힘들다.

# class CircleQueue
    
    def size(self):
        if self.rear < self.front:
            return self.rear - self.front + self.capacity
        else:
            return self.rear - self.f

이를 위해 rear가 front 보다 작은 경우, 원소의 개수를 구할 때 capacity를 더해주는 작업을 진행하였다. rear가 front 보다 작아졌다는 것은 rear가 인덱스의 범위를 벗어나 더 커진 것이기 때문에, 사실상 rear+capacity의 인덱스를 가리키고 있다고 봐도 무방하기 때문이다. 따라서 사이즈를 계산할 때 rear가 front 보다 작다면 capacity를 더해주었다. 

 

계속해서 9와 10을 삽입하면 그림은 다음과 같아진다.

 

이제 여기서 원소 11을 추가로 삽입하게 되면, rear와 front가 같아지게 된다. 이러한 경우 _expand 함수를 통해 확장을 하도록 했다. 

# class CircleQueue

    def _expand(self):
        self.capacity *= 2
        tmp = [0 for _ in range(self.capacity)]
        ptr = self.front
        i = 0
        while ptr != self.rear:
            tmp[i] = self.queue[ptr]
            i += 1
            ptr = (ptr + 1) % (self.capacity // 2)
        tmp[i] = self.queue[ptr]
        self.front = 0
        self.rear = i
        self.queue = tmp

코드로만 보면 헷갈릴 수 있으니 아래 그림과 함께 보자! 

 

ptr 변수를 초기에 front와 같게 두고, rear와 같아질 때까지 +1씩 증가시키며 원소를 탐색한다. 이와 동시에 새로운 큐의 인덱스 i 또한 ptr과 같이 증가시키며 현재 ptr이 가리키고 있는 원소를 i가 가리키고 있는 자리에 복사한다. 

 

ptr이 리스트의 인덱스 끝 범위까지 가도 이후에 모듈러 연산을 통해 다시 맨 앞으로 보낼 수 있다. 모든 원소의 복사가 끝나고 나면 아래의 그림과 같은 결과를 얻을 수 있다.

 

이제 마지막으로 큐의 front와 rear를 새로운 리스트와 맞춰주어야 하는데, front는 리스트의 시작점인 0으로 설정하면 간단하지만 rear의 경우 마지막 i 값으로 초기화시켜줘야 한다. 이렇게 되면 rear가 다음 원소가 삽입될 위치가 아닌 마지막 원소의 위치를 가리키게 되는데, expand 연산이 insert 이후에 발생하기 때문에 expand 이후에 rear를 1만큼 더 증가시키는 연산이 추가로 존재한다. 따라서 expand 함수에서는 rear 값을 마지막 원소의 위치로 설정해 주었다. 

expand가 끝난 후 insert 함수 내에서 rear 값의 조정 이후는 다음과 같다.

 

이렇게 큐의 경우 리스트가 꽉 찼을 때 크기를 두 배씩 늘려주면서 확장을 진행한다. 물론 확장하는 방식이 이것뿐만 아니라 다양한 방법이 존재하지만 이 포스팅에서는 다루지 않았다..! CircleQueue의 전체적인 구현 코드는 아래와 같다.

 

class CircleQueue:
    
    rear = 0
    front = 0
    capacity = 8
    queue = list()
    
    def __init__(self):
        self.rear = 0
        self.front = 0
        self.queue = [0 for _ in range(self.capacity)]
        
    def is_empty(self):
        return self.rear == self.front
    
    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front
    
    def insert(self, x):
        self.queue[self.rear] = x
        if self.is_full():
            self._expand()
        self.rear = (self.rear + 1) % self.capacity

    def delete(self):
        if self.is_empty():
            print("Empty")
            return
        elem = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity
        return elem
    
    def size(self):
        if self.rear < self.front:
            return self.rear - self.front + self.capacity
        else:
            return self.rear - self.front
        
    def _expand(self):
        self.capacity *= 2
        tmp = [0 for _ in range(self.capacity)]
        ptr = self.front
        i = 0
        while ptr != self.rear:
            tmp[i] = self.queue[ptr]
            i += 1
            ptr = (ptr + 1) % (self.capacity // 2)
        tmp[i] = self.queue[ptr]
        self.front = 0
        self.rear = i
        self.queue = tmp
    
    def peek(self):
        if self.is_empty():
            print("Empty")
            return
        return self.queue[self.front]