[자료구조] Queue(큐)(Python)

* 개요

Queue(큐)는 선입선출(First In First Out)의 자료구조를 뜻한다. 대기열이라고도 한다. 데이터가 들어오는 위치는 가장 뒤(rear 또는 back)에 있고, 데이터가 나가는 위치는 가장 앞(front)이다. 큐를 응용한 형태의 큐로는 원형 큐(Circular Queue), 우선순위 큐(Priority Queue) 등이 있다. 보통 배열을 사용해서 큐를 구현하면, enqueue(rear에 데이터 추가)와 dequeue(front의 데이터 삭제)를 할 때마다 계속 데이터가 앞으로 밀려나는 문제가 생기는데, 이를 해결하기 위해 원형 버퍼(원형 큐)를 사용한다. 원형 큐는 이후 포스트에서 다룰 예정이다. 

 

* 파이썬으로 구현한 큐(리스트)

큐를 리스트로 구현하였다.

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

    def enqueue(self, data):
        self.queue.append(data)

    def dequeue(self):
        dequeue_data = None
        if self.isEmpty():
            print("큐가 비어있음.")

        else:
            dequeue_data = self.queue.pop(0)

        return dequeue_data

    def peek(self):
        peek_data = None
        if self.isEmpty():
            print("큐가 비어있음.")

        else:
            peek_data = self.queue[0]

        return peek_data

    def isEmpty(self):
        is_empty = False

        if len(self.queue) == 0:
            is_empty = True

        return is_empty

    def printQueue(self):
        print(self.queue)

q = Queue()
q.enqueue(1)  # 1을 enqueue
q.enqueue(2)  # 2를 enqueue
q.enqueue(3)  # 3을 enqueue
q.dequeue()  # 1을 dequeue
print(q.peek())  # 2
q.printQueue() # [2, 3] 출력

__init__()은 큐 클래스의 초기화 부분으로써, 리스트를 선언한다.

enqueue()는 리스트에 data를 append 해준다.

dequeue()는 isEmpty()를 통해 큐가 비어있는지에 대한 여부를 판단하고, 비어있지 않다면 front의 데이터를 pop한다.

peek()는 isEmpty()를 통해 큐가 비어있는지에 대한 여부를 판단하고, 비어있지 않다면 front의 데이터를 반환한다.

isEmpty()는 len() 함수를 통해 큐가 비어있는지 확인한다. 비어있다면 True를, 비어있지 않다면 False를 반환한다.

 

* 파이썬으로 구현한 큐(연결 리스트)

큐를 연결 리스트로 구현하였다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedListQueue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        new_node = Node(data)

        if self.isEmpty():
            self.head = new_node

        else:
            self.tail.next = new_node

        self.tail = new_node

    def dequeue(self):
        dequeue_data = None

        if self.isEmpty():
            print("큐가 비어있음.")

        else:
            dequeue_data = self.head.data
            self.head = self.head.next

        return dequeue_data

    def peek(self):
        peek_data = None

        if self.isEmpty():
            print("큐가 비어있음.")

        else:
            peek_data = self.head.data

        return peek_data

    def isEmpty(self):
        is_empty = False
        if self.head is None:
            is_empty = True

        return is_empty

    def printQueue(self):
        node = self.head

        while node is not None:
            print(node.data, end=" ")
            node = node.next

lq = LinkedListQueue()
lq.enqueue(1)  # 1을 enqueue
lq.enqueue(2)  # 2를 enqueue
lq.enqueue(3)  # 3을 enqueue
lq.dequeue()  # 1을 dequeue
print(lq.peek())  # 2
lq.printQueue()  # 2 3 출력

Node 클래스는 노드 생성을 하는 클래스이다.

LinkedListQueue의 __init__()은 head와 tail을 모두 None으로 초기화 해준다.

enqueue()는 isEmpty()를 통해 큐가 비어있는지에 대한 여부를 판단하고, 비어있다면 head에 노드를 생성한다. 비어있지 않다면, 기존의 tail의 다음 노드에 새로운 노드를 넣고, 새로운 노드는 head가 된다.

dequeue()는 isEmpty()를 통해 큐가 비어있는지에 대한 여부를 판단하고, 비어있지 않다면 head의 데이터를 삭제한다.

peek()는 isEmpty()를 통해 큐가 비어있는지에 대한 여부를 판단하고, 비어있지 않다면 head의 데이터를 반환한다.

isEmpty()는 head 노드의 None 여부를 통해 큐가 비어있는지 확인한다. 비어있다면 True를, 비어있지 않다면 False를 반환한다.