Python으로 구현하는 자료구조 : Queue (1) Queue

이번 포스팅에서는 자료구조 큐(Queue)에 대한 특징을 살펴보고

파이썬으로 큐에 원소를 삽입, 삭제, 조회하는 코드를 짜보도록 하겠습니다.

---

# Queue란?

큐란 목록 한쪽 끝에서만 자료를 넣고 다른 한쪽 긑에서만 자료를 빼낼 수 있는 자료구조 입니다. 먼저 집어넣은 데이터가 먼저 나오는 (FIFO : First in, First out) 구조로 데이터를 저장합니다. 데이터가 입력한 순서대로 처리되어야 할 경우에 사용합니다. 큐에 새로운 데이터가 들어오면 큐의 끝에 데이터가 추가되며(enqueue), 반대로 삭제될 때는 첫번째 위치의 데이터가 삭제됩니다(dequeue).

# Queue의 종류는?

선형큐, 환형큐, 우선순위큐가 있습니다. 여기서는 기본적인 큐의 형태만 살펴보고 그 외의 큐는 다른 포스팅에서 다루도록 하겠습니다.

# 선형 Queue의 문제점

일반적인 선형 큐는 배열의 마지막 index를 가리키는 변수가 있고, dequeue가 일어날때마다 비어 있는 공간이 생기면서 이를 활용할 수 없게 된다. 이 방식을 해결하기 위해 front를 고정시킨 채 뒤에 남아있는 데이터를 앞으로 한 칸 씩 떙길 수 밖에 없습니다. 이에 대한 대안으로 사용하는것이 원형큐입니다.

 

#Queue 구현하기

Queue는 리스트로 구현하는 것도 가능하지만 효율적이지 않습니다. 리스트는 끝에 원소를 덧붙이거나, 끝에서 꺼내는(pop()) 작업은 빠르지만 리스트의 맨 처음에 원소를 추가하거나 빼는 것은 느립니다. (다른 원소들을 모두 한 칸씩 이동시켜야 하기 때문) Queue를 구현하려면, 양 끝에서 덧붙이기와 꺼내기가 빠르도록 설계된 collections.deque를 사용하거나, 파이썬에서 제공하는 Queue 모듈을 이용해 큐를 구현하는 것이 좋습니다. 아니면 원소를 추가, 삭제하는데 효율적인 linked list를 활용할 수도 있습니다. 여기서는 모든 방법을 활용해서 큐를 구현해보도록 하겠습니다.

# 파이썬 코드 - 리스트를 사용

리스트를 사용했을 경우에는 enqueue(추가)의 시간복잡도는 O(1)이며, dequeue(삭제)는 O(N)입니다. 추가의 경우에는 큐의 맨 끝에서만 일어나지만, 큐의 첫번째 원소를 삭제할 경우에는 두번째 원소부터 맨 마지막 원소까지 모든 원소들의 위치를 왼쪽으로 한 칸씩 옮겨주어야 하기 때문입니다.

class ListQueue(object):
    def __init__(self):
        self.queue = []
 
    def dequeue(self):
        if len(self.queue) == 0:
            return -1
        return self.queue.pop(0)
 
    def enqueue(self, n):
        self.queue.append(n)
        pass
 
    def printQueue(self):
        print(self.queue)
 
 
if __name__ == "__main__":
    lq = ListQueue()
    lq.enqueue(1)
    lq.enqueue(2)
    lq.enqueue(3)
    lq.enqueue(4)
    lq.enqueue(5)
    lq.printQueue()
    print(lq.dequeue())
    print(lq.dequeue())
    print(lq.dequeue())
    print(lq.dequeue())
    print(lq.dequeue())
    lq.printQueue()
 

# 파이썬 코드 - collections.deque 사용

deque(데크)는 double-ended queue의 줄임말로, 앞과 뒤 양방향에서 데이터를 처리할 수 있는 자료구조를 의미합니다. Python의 list와 유사하지만 Collection.deque의 시간복잡도를 확인해보면 앞뒤에서 데이터를 처리하는 속도가 O(1)로 매우 빠른 것을 알수 있습니다. 이는 내부적으로 doubly 링크드 리스트로 구현되어 있기 때문입니다.

from collections import deque
 
# deque 선언
dq = deque([])
 
# deque에 데이터 추가
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
print(dq)  # deque([1,2,3,4])
 
# deque의 첫번째 원소 제거
print(dq.popleft()) # 1
print(dq.popleft()) # 2
print(dq.popleft()) # 3
print(dq.popleft()) # 4
print(dq)# deque([])

# 파이썬 코드 - Queue 모듈 사용

파이썬의 Queue 모듈에서는 큐(Queue), 우선순위큐(PriorityQueue), 스택(LifoQueue)를 제공하고 있습니다. 특히 큐 모듈은 스레드 환경을 고려하여 작성되어 있기 때문에 여러 스레드들이 동시에  큐(Queue), 우선순위큐(PriorityQueue), 스택(LifoQueue)과 같은 객체에 접근하여 작업을 수행하여도 정상적으로 동작하는 것을 보장합니다. 여기선 기본적인 Queue를 사용하여 쉽게 Queue를 활용해 보도록 하겠습니다.

import queue
 
# Queue 선언
q = queue.Queue()
 
# q에 데이터 추가
q.put(1)
q.put(2)
q.put(3)
q.put(4)
 
# q에서 첫번째 원소 제거
print(q.get()) # 1
print(q.get()) # 2
print(q.get()) # 3
print(q.get()) # 4

from collections import deque
 
class Queue(deque):
 
    def enqueue(self, x):
        super().append(x)
 
    def dequeue(self):
        super().popleft()
 
    def display(self):
        for node in self.__iter__():
            print(node)

# 파이썬 코드 -  Linked list 사용

기존에 구현해둔 Linked list에 tail을 추가하여 맨 마지막 원소를 기억함으로써 원소를 추가하는데 쉽게 만들 수 있습니다. 또한 Linked list로 Queue를 구현함으로써 리스트로 Queue를 구현하였을 때 삭제하고 난 이후의 모든 원소들을 이동시켜야 했던 한계점을 극복할 수 있습니다.

# Node
class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
# Singly linked list
class SinglyLinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None
 
    # Add new node at the end of the linked list
    def enqueue(self, node):
        if self.head == None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = self.tail.next
 
    def dequeue(self):
        if self.head == None:
            return -1
 
        v = self.head.data
        self.head = self.head.next
 
        if self.head == None:
            self.tail = None
        return v
 
    # 출력
    def print(self):
        curn = self.head
        string = ""
        while curn:
            string += str(curn.data)
            if curn.next:
                string += "->"
            curn = curn.next
        print(string)
 
 
if __name__ == "__main__":
    s = SinglyLinkedList()
    # 원소 추가
    s.enqueue(Node(1))
    s.enqueue(Node(2))
    s.enqueue(Node(3))
    s.enqueue(Node(4))
    s.print() # 1->2->3->4
 
    # 원소 삭제
    print(s.dequeue()) # 1
    print(s.dequeue()) # 2
    s.print()  # 3->4
    print(s.dequeue()) # 3
    print(s.dequeue()) # 4