[자료구조] 큐와 원형 큐 (Queue, Circular Queue)

Queue

class Queue:
    def __init__(self):
        self.container = list()
        
    def is_empty(self):
        if not self.container:
            return True
        else:
            return False
        
    def enqueue(self, data):
        self.container.append(data)
        
    
    # O(n)
    def dequeue(self):
        return self.container.pop(0)
    
    
    def peek(self):
        return self.container[0]

 

큐의 주요 특징 : FIFO (First In First Out)

enqueue() 연산은 배열의 마지막에 원소를 추가하므로 시간복잡도가 O(1)인 반면, dequeue() 연산은 동적 배열의 첫 번째 데이터를 삭제한 후 모든 데이터를 한 번씩 옮겨야 하므로 O(n)이 된다. 

---

Circular Queue

class CircularQueue:
    MAXSIZE = 10
    
    def __init__(self):
        self.container = [None for _ in range(CircularQueue.MAXSIZE)]
        self.front = 0 
        self.rear = 0
        
        
    def is_empty(self):
        if self.front == self.rear:
            return True
        return False
    
    
    def __step_forward(self, x):
        x += 1
        if x >= CircularQueue.MAXSIZE:
            x = 0
        return x
    
    
    def is_full(self):
        next = self.__step_forward(self.rear)
        if next == self.front:
            return True
        return False
    
    
    def enqueue(self, data):
        if self.is_full():
            raise Exception("The queue is full")
        self.container[self.rear] = data
        self.rear = self.__step_forward(self.rear)
        
        
    def dequeue(self):
        if self.is_empty():
            raise Exception("The queue is empty")
            
        ret = self.container[self.front]
        self.front = self.__step_forward(self.front)
        return ret
    
    
    def peek(self):
        if self.is_empty():
            raise Exception("The queue is empty")
            
        return self.container[self.front]
        
        


cq = CircularQueue()

for i in range(8):
    cq.enqueue(i)

for i in range(5):
    print(cq.dequeue(), end=' ')

for i in range(8, 14):
    cq.enqueue(i)
    
while not cq.is_empty():
    print(cq.dequeue(), end=' ')

print()
for i in range(10):
    print(cq.container[i], end= ' ')
    
print()




# 결과
#
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13
# 10 11 12 13 4 5 6 7 8 9

Queue()는 dequeue 연산마다 모든 데이터를 한 번씩 이동시켰는데, CircularQueue는 데이터를 모두 이동시키는 것이 아니라 front를 뒤로 한 번만 이동시킨다.

 

 

큐는 어디에 쓰이는가?

OS는 태스크 큐를 이용하여 스케쥴링을 한다. 컴퓨터는 동시에 여러 프로그램을 실행할 수 있는데 실제로 작업을 수행하는 CPU는 제한적이다. 이 때 OS는 프로그램에서 작업을 요청받아 이를 큐에 담은 후 정해진 알고리즘에 따라 큐에서 태스크를 꺼내 실행한다. 이렇게 실행할 작업 순서를 정하는 것을 스케줄링이라고 한다.