파이썬으로 구현하는 자료구조! - 큐 ( Queue )

1. 큐(Queue)가 뭐야?

큐는 양쪽이 뚤려있는 기다란 통에서 한쪽은 데이터를 삽입하고 한쪽은 데이터를 삭제하는 자료구조 입니다.

스택이 후입선출 ( LIFO - Last In, First Out ) 구조였다면

큐는 먼저 들어간 데이터가 먼저 나오는 선입선출 ( FIFO - First In, First Out ) 구조입니다.

위의 그림과 같이 데이터의 앞부분을 Front 뒷부분을 Rear라고 부릅니다.

데이터는 Rear로 들어와서 Front로 나갑니다.

 

큐와 같은 구조는 우리의 일상속에서 많이 볼 수 있습니다.

 

은행에 가면 번호표를 뽑은 순서대로 창구에서 은행 업무를 보는 것과

프린터의 대기열을 예로 들면 먼저 프린트를 요청한 사람부터 먼저 프린트를 하는 것을 예로 들 수 있습니다.

2. 주요 Method

2-1. enqueue, equeue

데이터를 삽입하는 과정을 enqueue

가장 먼저 삽입한 데이터를 빼서 사용하는 과정을 dequeue라고 합니다.

dequeue를 하는 경우에 큐가 비어있는지 먼저 확인한 후에 실행합니다.

2-2. peek

peek은 Front 위치에 있는 데이터를 꺼내지 않고 어떤 값인지 return하는 method입니다.

2-3. isEmpty

isEmpty는 현재 큐가 비어있는지 확인하는 method입니다.

3. 코드로 구현하기

3-1. Python List로 구현하기

class Queue():
    def __init__(self):
        self.queue = []
        
    def enqueue(self, data):
        self.queue.append(data)
        
    def dequeue(self):
        dequeue_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            dequeue_object = self.queue[0]
            self.queue = self.queue[1:]
            
        return dequeue_object
            
    def peek(self):
        peek_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            peek_object = self.queue[0]
            
        return peek_object
            
    def isEmpty(self):
        is_empty = False
        if len(self.queue) == 0:
            is_empty = True
        return is_empty

enqueue는 list의 append를 활용하여 구현하였습니다.

 

dequeue는 queue가 비어있는지 isEmpty를 활용하여 확인하고

비어있다면 "Queue is Empty"를 출력하고 None을 return

비어있지않다면 list의 가장 첫번째값을 가져온 뒤 [1:] 을 활용하여 첫번째 값 이외의 값들만 남겨둡니다.

 

peek은 queue가 비어있는지 isEmpty를 활용하여 확인하고

비어있다면 "Queue is Empty"를 출력하고 None을 return

비어있지않다면 list의 가장 첫번째값을 가져와서 return합니다.

 

isEmpty는 queue에 값이 하나도 없을 경우 True, 값이 있을 경우 False를 return 하도록 하였습니다.

3-2. Python Singly Linked List로 구현하기

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

class LinkedListQueue():
    def __init__(self):
        self.front = None
        self.rear = None
        
    def enqueue(self, data):
        new_node = Node(data)
        
        if self.front is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = self.rear.next
        
    def dequeue(self):
        dequeue_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            dequeue_object = self.front.data
            self.front = self.front.next
            
        if self.front is None:
            self.rear = None
        return dequeue_object
    
    def peek(self):
        front_object = None
        if self.isEmpty():
            print("Queue is Empty")
        else:
            front_object = self.front.data            
        return front_object
    
    def isEmpty(self):
        is_empty = False
        if self.front is None:
            is_empty = True
        return is_empty

먼저 LinkedList를 만들기 위해 필요한 Node를 정의해줍니다.

각각의 노드는 data와 next로 이루어져 있습니다.

 

LinkedList로 만드는 Queue는 front와 rear를 먼저 None으로 init 해줍니다.

 

enqueue는 먼저 새로운 데이터를 담은 노드를 먼저 생성합니다.

만약 front가 None이면 front와 rear에 이 노드를 연결합니다.

그렇지 않으면 rear의 next에 새로운 노드를 넣어주고 이를 다시 rear에 넣어줍니다.

 

dequeue는 먼저 isEmpty를 활용하여 Queue가 비어있는지를 먼저 확인하고

비어있다면 "Queue is Empty"를 출력하고 None을 return

비어있지 않다면 front의 노드에서 데이터를 꺼내온 뒤 front에 front의 next 노드를 넣어주고 아까 꺼낸 데이터를 return 합니다.

 

peek은 먼저 isEmpty를 활용하여 Queue가 비어있는지를 먼저 확인하고

비어있다면 "Queue is Empty"를 출력하고 None을 return

비어있지 않다면 front의 노드에서 데이터를 꺼내와 return 합니다.

 

isEmpty는 front가 None일 경우 True를 None이 아닐 경우 False를 return 합니다.

 

4. 관련 문제 풀어보기

Programmers - 코딩테스트 연습 > 스택/큐

프로그래머스

BaekJoon - 단계별로 풀어보기 > 큐, 덱

큐, 덱 단계

HackerRank - Interview Praperation Kit > Stacks and Queues

Solve Stacks and Queues Interview Questions | HackerRank

LeetCode - Problems > Tags > Queue

Problems - LeetCode

5. 구현 코드 GitHub

SOMJANG/DataStructure-Algorithm-Practice

 

다른 자료구조 알아보기

파이썬으로 구현하는 자료구조! - 스택 ( Stack )

 

파이썬으로 구현하는 자료구조! - 큐 ( Queue )