[자료구조 이론]Queue에 대해서

Queue란?

큐는 스택과 동일하게 데이터를 임시 보관하는 자료구조이다. 다만 스택과 달리 선입선출(FIFO, First In Frist Out)구조를 가지고 있다. 큐에서 가지는 기본적인 작업은 아래 두개가 있습니다

• 인큐(Enqueue) : 데이터를 추가하는 작업
• 디큐(Dequeue) : 데이터를 빼내는 작업

그리고 스택의 구조에 쓰이는 용어도 두가지가 있습니다.

• 프런트(Front) : 데이터를 꺼내는 쪽
• 리어(Rear) : 데이터를 빼내는 쪽

Ring Buffer로 원형 큐 구현하기

일반적으로 배열형태로 큐를 구현하게 되면, 만약 디큐를 하게 되면 그 뒤 원소들을 모두 앞쪽으로 땡겨주어야합니다. 이 작업에서는 시간복잡도 O(n)이 추가적으로 들어가게 됩니다.디큐의 시간복잡도가 O(1)인데 이 작업으로 인해 O(n)이 되기 때문에, 효율성 면에서도 좋지 않습니다. 이를 방지할 수 있는 방법이 바로 링 버퍼를 이용해서 원형큐를 구현하는 것입니다. 원형큐 구현시 어디가 데이터를 꺼내는쪽이고 넣는쪽인지를 판별하는 변수가 바로 front 와 rear입니다. front, rear모두 시간복잡도는 O(1)만 가지게 됩니다. 고정된 원형큐를 구현하면 아래와 같습니다.

from typing import Any

class FixedQue(object):

    class Empty(Exception):
        def __init__(self):
            self.msg = "Queue is Empty"

        def __str__(self):
            return self.msg

    class Full(Exception):
        def __init__(self):
            self.msg = "Queue is Full"
        
        def __str__(self):
            return self.msg
    
    def __init__(self, capacity : int) -> None:
        self.no = 0 # Data count
        self.front = 0 # front index number
        self.rear = 0 # rear index number
        self.capacity = capacity # Capacity of Queue
        self.que = [None] * self.capacity # Queue
    
    # return total amount of data
    def __len__(self) -> int:
        return self.no
    
    # return if queue is empty
    def isEmpty(self) -> bool:
        return self.no <= 0
    
    # return if queue is full
    def isFull(self) -> bool:
        return self.no >= self.capacity

    def enque(self, value) -> None:
        if self.isFull():
            raise FixedQue.Full
        else:
            self.que[self.rear] = value
            self.rear += 1
            self.no += 1
            if self.rear == self.capacity:
                self.rear = 0
    
    def deque(self) -> Any:
        if self.isEmpty():
            raise FixedQue.Empty
        else:
            rval = self.que[self.front]
            self.front += 1
            self.no -= 1
            if self.front == self.capacity:
                self.front = 0
            return rval

    def peek(self) -> Any:
        if self.isEmpty():
            raise FixedQue.isEmpty
        return self.que[self.front]

    def find(self, value) -> Any:
        for i in range(self.no):
            ind = (self.front + i) % self.capacity
            if self.que[ind] == value:
                return ind
        return -1

    def count(self, value) -> int:
        count = 0
        for i in range(self.no):
            ind = (self.front + i) % self.capacity
            if self.que[ind] == value:
                count += 1
        return count
    
    def __contains__(self,value: Any) -> bool:
        return self.count(value)
    
    def clar(self) -> None:
        self.no = self.front = 0
    
    def dump(self) -> None:
        if self.isEmpty():
            raise FixedQue.Empty
        else:
            for i in range(self.no):
                print(self.que[(self.front + i) % self.capacity])
            print()

if __name__ == "__main__":
    from random import randint
    q = FixedQue(20)
    for _ in range(14):
        q.enque(randint(1,10))
    print(len(q))
    print(7 in q)
    q.dump()
    print()

    for _ in range(10):
        print(q.deque())

여기서 주목할 것은 find와 count메소드에 있는

ind = (self.front + i) % self.capacity

문이다. 이는 현재 검사중인 인덱스를 저장하는 변수인데, 왜 이렇게 할까? 그 이유는 원형 큐 같은 경우 Front가 항상 0부터 시작하지 않는다 그렇기 때문에, 인덱스를 Front의 값에다가 현재 Front 기준 몇번째 뒤를 검사하고 있는지를 더하고 그 값에 대해 capacity로 나눈 나머지 값을 인덱스로 하여 구하는 것이다.

collections.deque로 Queue구현하기

스택에서 우리는 일반 Sequence타입을 이용해서 Fixed Stack을 구현하였다. 그리고 collections.deque를 이용해서 스택을 구현하였다. 일반적인 구현식 원형 큐, 배열 유형의 큐와 스택같은 경우에는 시간복잡도가 O(1)을 초과하는 경우가 종종 생긴다. 예를 들자면 큐를 구현할때 일반적인 리스트를 활용해서 구현하게되면, 스택은 후입선출이므로 list().pop()메소드가 O(1)의 시간복잡도를 가지게 되지만, 큐의 경우는 list().pop(0)를 해야한다. 이연산의 경우는 O(n)에 해당하는 연산을 하게 되는것이다. 그렇기 때문에, 스택 정리편에서 말했듯이 collections.deque를 큐 구현에 더 적합하다고 한 이유이다.(퍼포먼스 차이가 얼마나 나는지는 이 링크를 들어가서 보면 좋다 https://frhyme.github.io/python-lib/python_deque_is_faster_than_lst/) collections.deque를 활용해서 구현한 이유는 collections.deque는 내부적으로 Linked List로 구현되어있어, O(1)에 최대한 맞추는 연산을 하기 때문에, 더 빠른 연산이 가능하기 때문이다. 스택에서 이야기할때도 말했지만, 다시 말하자면 Linked List로 구현된 만큼, 중간에 데이터를 삽입해야하는 알고리즘에 있어서는 좋은 선택지는 아니다.

파이썬 공식 시간복잡도 레퍼런스는 이 링크로 가면 볼 수 있다. https://wiki.python.org/moin/TimeComplexity

from collections import deque
from typing import Any

class Queue(object):
    
    class Empty(Exception):
        def __init__(self):
            self.msg = "Queue is Empty"
        
        def __str__(self):
            return self.msg
    
    class Full(Exception):
        def __init__(self):
            self.msg = "Queue is Full"

        def __str__(self):
            return self.msg

    def __init__(self, capacity: int = 20):
        self.capacity = capacity
        self.que = deque([],self.capacity)

    def __len__(self):
        return len(self.que)
    
    def isfull(self):
        return len(self.que) >= self.capacity
    
    def isempty(self):
        return len(self.que) <= 0
    
    def enque(self, value):
        if self.isfull():
            raise Queue.Full
        else:
            self.que.append(value)
    
    def deque(self):
        if self.isempty():
            raise Queue.Empty
        else:
            return self.que.popleft()
    
    def peek(self):
        if self.isempty():
            raise Queue.Empty
        else:
            return self.que[0]
    
    def count(self,value):
        if self.isempty():
            raise Queue.Empty
        else:
            return self.que.count(value)
    
    def __contains__(self,value):
        return self.count(value)
    
    def clear(self):
        self.que.clear()
        # Re-define after clear queue
        self.que = deque([],self.capacity)
    
    def dump(self):
        print(*list(self.que), end='    ')

if __name__ == "__main__":
    q = Queue()
    from random import randint
    for _ in range(14):
        q.enque(randint(1,10))
    
    q.dump()
    print()
    print(6 in q)
    print(len(q))

    # Exception
    for _ in range(10):
        q.enque(randint(1,10))