🚶 큐(queue) 파이썬으로 구현하기!

큐에 대해서 알아보고 파이썬으로 구현해보기

 

큐(Queue)란?

• 선입선출(First In First Out, FIFO), 처음에 넣은게 가장 먼저 나옴
• 놀이공원 줄 서기를 생각하면 편하다
• 사용처 : 여러 작업들이 동시에(병렬적으로) 이루어져도 상관없는 경우, 의존관계 없는 경우
• 예시 : 스케쥴링 (운영체계 프로세스 관리)

 

큐의 추상 자료형(ADT)

객체 (characters)

• arr : T[], 데이터가 저장되는 배열, 리스트
• front : int, 큐의 맨 앞부분 인덱스
• rear : int, 큐의 맨 뒷부분 인덱스

 

연산 (operations)

• enqueue() : 맨 뒤에 원소를 넣음
• dequeue() : 맨 앞 원소를 뺌
• back() : 맨 뒤 원소를 확인
• front() : 맨 앞 원소를 확인
• isempty() : 큐가 비어있는지 아닌지 확인
• size() : 원소 크기를 확인

 

큐의 구현

간단하게 구현

class Queue:
    def __init__(self):
        self.arr = []

    # 값을 넣음
    def enqueue(self, element):
        return self.arr.append(element)
        
    # 값을 뺌
    def dequeue(self):
        if self.isempty(): return None

        # 파이썬에서 list의 경우 pop(0)에 O(N)의 시간복잡도가 들어서 비추
        return self.arr.pop(0)

    # 최근에 넣은 값 확인
    def back(self):
        if self.isempty(): return None
            
        return self.arr[0]

    # 나중에 넣은 값 확인
    def front(self):
        if self.isempty(): return None
            
        return self.arr[-1]
        
    # 비어있는지 확인
    def isempty(self):
        return len(self.arr) == 0

    # 크기 확인
    def size(self):
        return len(self.arr)

파이썬 리스트에서 pop 연산의 경우는 index를 입력할 경우 연산의 시간복잡도가 O(N)이 되어버린다. 따라서 위 예시는 부적절하다. 그냥 어떻게 작동하는지 참고용.

 

선형 큐 (Linear Queue)

배열이나 연결 리스트에서 큐의 앞쪽 인덱스(front)와 뒤쪽 인덱스(rear)를 저장해두고, 원소를 뺄 때 front를 한칸씩 밀어내는 방식. 앞쪽에서 뺄 때마다 빈칸이 생긴다는 단점이 있다.

class Queue:
    def __init__(self):
        self.arr = []
        self.front = 0
        self.rear = 0

    def enqueue(self, element):
        self.arr.append(element)
        self.rear += 1

    def dequeue(self):
        if self.isempty(): return None
            
        output = self.arr[self.front]
        self.arr[self.front] = 0
        self.front += 1 

        return output

    def isempty(self):
        return self.front == self.rear

 

원형 큐 (Circular Queue)

선형 큐에서 빈칸이 생긴다는 단점을 보완하기 위해 배열이나 연결 리스트를 원형처럼 생각하는 것. 대신 크기가 정해져있다. 

class Queue:
    def __init__(self, size):
        self.arr = [0] * (size + 1)
        self.size = size + 1
        self.front = 0
        self.rear = 0

    def enqueue(self, element):
        if self.isfull():
            raise Exception('큐가 꽉참')

        self.arr[self.rear] = element
        self.rear = (self.rear + 1) % self.size

    def dequeue(self):
        if self.isempty(): return None

        output = self.arr[self.front]
        self.arr[self.front] = 0
        self.front = (self.front + 1) % self.size

        return output

    def isempty(self):
        return self.rear == self.front

    def isfull(self):
        return (self.rear + 1) % self.size == self.front

위 코드는 항상 한 칸은 비워져있다. 그래서 리스트 크기를 한 칸 더 크게 만들어준다.