[자료구조] 2-3. 원형 큐 (Circular queue)

지난 2-2 글에서, 내가 구현한 배열을 이용한 큐는, 엄밀히 따지면 파이썬의 리스트를 이용한 것이다.

'배열'이랑 구현한 것과 다른 점은,

1. 큐의 크기를 정하지 않는다.(append하면 뒤에 새 칸을 만들고, pop하면, 칸이 줄어든다)
2. pop 했을 때, 뒤 데이터들이 빈 자리를 채우러 앞으로 당겨진다.

그래서, '배열스러운' 큐를 다시 구현해보았다.

 

큐 - '배열'을 이용한 구현(Python)

class queue():    #큐 선언
    def __init__(self, size):
        self.size = size
        self.arr = [None] * self.size
        self.first = 0
        self.last = 0
        
    def isEmpty(self):    #큐가 비어있는지 확인
        if self.first >= self.size:
            return True
        if self.arr[self.first] == None:
            return True
        else:
            return False
        
    def isFull(self):    #큐가 꽉 차있는지 확인
        return self.last == self.size
        
    def enqueue(self, data):    #큐에 data 삽입
        if self.isFull() is True:
            print("Queue is Full!")
            return None
        self.arr[self.last] = data
        self.last = self.last + 1
        
    def dequeue(self):    #큐의 맨 앞 데이터 pop
        if self.isEmpty():
            return "Queue is Empty!"
        else:
            n = self.arr[self.first]
            self.arr[self.first] = None
            self.first = self.first +1
            return n
        
    def rear(self):    #큐의 맨 뒤 데이터 반환(pop 하지는 않음)
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            return self.arr[self.last]
        
    def front(self):    #큐의 맨 앞 데이터 반환(pop하지는 않음)
        if self.isEmpty():
            print("Queue is Empty!")
        else:
            return self.arr[self.first]

True
True
Queue is Full!
4
7
2
3
True
Queue is Empty!
Queue is Full!

이전에 만든 리스트기반의 큐에서 dequeue를 하면, pop연산을 통해서 뒤의 데이터들을 모두 앞으로 끌어온다. 이러면 Front가 필요없어서 편리하겠지만, 매번 데이터를 뺄 때마다 뒤 값들을 옮겨야 하므로 시간 복잡도가 늘어나는 단점이 있다. 배열 기반의 큐에서는, Front를 움직이는 연산을 통해서 훨씬 시간을 절약한다.

 

하지만, 이 방법도 한계가 있다. 위 코드나 사진처럼, 배열의 끝에 도달해버리면 더 이상 쓸수없는 큐가 되어버린다.

이때, 우리는 "Front와 Rear를 다시 앞으로 돌릴 수는 없을까?" 라는 생각을 하게 된다.

이를 보완하기 위해서, 원형 큐를 사용하기로 한다.

 

원형 큐

Front와 Rear를 다시 앞으로 돌리기 위해서, 우리는 큐 자료구조를 원형으로 만들 것이다.

Front와 Rear를 배열의 크기만큼 나머지 연산을 하여 회전시킨다.

 

원형 큐에서 Front와 Rear가 같은 순간은 두 가지가 있다.

1. Front와 Rear가 같고, 그 값이 없을 때
2. Front와 Rear가 같고, 그 값이 있을 때

값이 없을 때에는 큐가 비어있다는 뜻이고, 값이 있을 때에는 큐가 가득 차 있다는 뜻이다.

 

구현

class circular_queue():    #큐 선언
    def __init__(self, size):
        self.size = size
        self.arr = [None] * self.size
        self.first = 0
        self.last = 0
        
    def isEmpty(self):    #큐가 비어있는지 확인
        if self.first == self.last and self.arr[self.first] == None:
            return True
        else:
            return False
 
    def isFull(self):    #큐가 꽉 차있는지 확인
        if self.first == self.last and self.arr[self.first] != None:
            return True
        else:
            return False
        
    def enqueue(self, data):    #큐에 data 삽입
        if self.isFull():
            print("Queue is Full!")
            return None
        self.arr[self.last] = data
        self.last = (self.last + 1)% self.size
        
    def dequeue(self):    #큐의 맨 앞 데이터 pop
        if self.isEmpty():
            return "Queue is Empty!"
        else:
            n = self.arr[self.first]
            self.arr[self.first] = None
            self.first = (self.first +1)% self.size
            return n
        
    def rear(self):    #큐의 맨 뒤 데이터 반환(pop하지는 않음)
        if self.isEmpty():
            return("Queue is Empty!")
        else:
            return self.arr[self.last]
        
    def front(self):    #큐의 맨 앞 데이터 반환(pop하지는 않음)
        if self.isEmpty():
            return("Queue is Empty!")
        else:
            return self.arr[self.first]

 

실행 예시

q = circular_queue(4)
 
print(q.isEmpty())    #True
 
q.enqueue(4)    #[4, None, None, None]
q.enqueue(7)    #[4, 7, None, None]
q.enqueue(2)    #[4, 7, 2, None]
q.enqueue(3)    #[4, 7, 2, 3]
 
print(q.isFull())    #True
q.enqueue(9)    #더 넣을 공간이 없음
 
print(q.dequeue())    #[None, 7, 2, 3]
print(q.dequeue())    #[None, None, 2, 3]
print(q.dequeue())    #[None, None, None, 3]
print(q.dequeue())    #[None, None, None, None]    
print(q.isEmpty())    #True
print(q.dequeue())    #더 뺄게 없음
 
q.enqueue(8)        #[8, None, None, None]
print(q.dequeue())    #[None, None, None, None]
q.enqueue(9)        #[None, 9, None, None]
q.enqueue(1)        #[None, 9, 1, None]
q.enqueue(6)        #[None, 9, 1, 6]
q.enqueue(4)        #[4, 9, 1, 6]
print(q.arr)        #[4, 9, 1, 6]
print(q.front())    #9

결과

True
Queue is Full!
4
7
2
3
True
Queue is Empty!
8
[4, 9, 1, 6]9