큐(Queue)

큐(Queue)란?

FIFO(First In First Out)의 성격을 가진 자료구조.

처음으로 들어간 데이터가 처음으로 빠져 나오는 어찌보면 당연하고 합리적인 자료구조이다.

실생활에서도 많이 접할 수 있는 자료구조 중 하나이다.

 

사용예시

• 서버 접속 대기열 큐
  • 롤에서 야 큐 돌려~ 하는것도 이 큐가 맞음
• 인쇄 대기열 큐
  • 인쇄 하나가 오류로 안되면 그 뒤에 나와야할 인쇄물도 모조리 안나오는 경험이 있을 것이다. 이 때도 큐를 쓴다.

 

큐의 대표 기능

• Peek(픽)
  • 큐의 Top(맨 앞) 데이터를 보는 것
• Enqueue(삽입)
  • 큐에 원소를 삽입하는 행위. 원소는 Rear(맨 뒤)에 들어간다. 
• Dequeue(뽑기)
  • 큐에서 원소를 뽑아오는 행위. FIFO 자료구조라 Front에 위치한 원소를 뽑아온다.

 

Peek, Enqueue, Dequeue 코드 구현

이번에도 링크드리스트를 통해 큐를 구현해보자

이 때, 큐 같은 경우는 스택과 다르게 시작과 끝의 노드를 전부 가지고 있어야 하므로

self.head와 self.tail을 가지고 시작한다. 

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

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

    def enqueue(self, value):
        new_node = Node(value)
        if self.head is None or self.tail is None:
            self.head = new_node
            self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        # tail에 데이터가 추가되고 있으니 head에서 반환을 하는게 옳다.
        if self.head is None:
            return None
        # stack에서와 마찬가지로 print()를 하는거보다 None으로 반환한 후 queue.dequeue를 호출하는곳에서
        # 처리하게 해주는 방법을 쓰자.
        deleted_head = self.head
        self.head = self.head.next
        return deleted_head.data

    def peek(self):
        if self.head is None:
            return None
        return self.head.data


queue = Queue()
queue.enqueue(3)
print('peek: ', queue.peek())       # peek:  3
queue.enqueue(4)
print('peek: ', queue.peek())       # peek:  3
queue.enqueue(5)
print('peek: ', queue.peek())       # peek:  3

print('dequeue: ', queue.dequeue()) # dequeue:  3
print('peek: ', queue.peek())       # peek:  4

 

정리

이렇게 링크드리스트를 통해 큐를 구현해봤다.

스택, 큐가 삽입/삭제가 빈번하게 발생하는 자료구조이기 때문에 링크드리스트를 썼다는 사실을 이해하고 넘어가도록 하자