큐(Queue) in Python

목차

머리말

들어가기 전에

학습 목표

선형 자료구조에서 두 번째로 알아볼 것은 큐(queue)이다.

큐의 정의와 특징에 대해 살펴보고, 파이썬으로 구현해 보자.

이전 포스팅 - 스택

스택(stack) in Python

 

큐는 무엇을 기다리는 대상으로 이루어진 '줄'이다

 

큐(Queue)

정의

큐를 사전에서 찾아보면 (무엇을 기다리는 사람, 자동차 등의) 줄이라는 뜻의 단어이다.

위의 사진처럼 기다리는 사람의 줄이 대표적인 큐이다.

큐(queue)는 "뒤"라고도 불리는 한쪽 끝에서 새 요소가 추가되고, 흔히 "앞"이라고도 불리는 다른 쪽 끝에서 이미 있는 요소가 제거되는 선형 자료 구조이다.

A queue is a linear data structure where the first element is inserted from one end, called the "rear", and existing element is deleted from the other end, called the "front".

 

특징

선입선출(FIFO)

앞의 정의에서 "한쪽 끝에서 새 요소가 추가되고, 다른 쪽 끝에서 이미 있는 요소가 제거되는" 특징

• 새 요소가 추가되는 위치를 뒤(Back or Rear)라 하고 이미 있는 요소가 추가되는 위치를 앞(Front)이라 한다.
• 큐에서 추가/삭제는 각각 Enqueue, Dequeue라 한다.

큐의 대표적인 특징인 Enqueue와 Dequeue

 

실습

정의 코드

스택을 다뤘을 때처럼, 파이썬의 기본 자료구조에서 리스트를 활용하면 쉽게 구현할 수 있다.

# 큐 클래스 정의
class Queue:
    def __init__(self):
        self.items = [] # 초깃값은 파이썬의 빈 리스트로 할당

    def enqueue(self, item):
        self.items.insert(0, item) # enqueue는 파이썬 리스트의 기본 메서드인 insert를 활용하여 추가

    def dequeue(self):
        if self.is_empty(): # 큐가 비어 있을 경우, 비어 있다는 에러 메시지 출력
            raise Exception("queue is empty.")
        self.items.pop() # dequeue 파이썬 리스트의 기본 메서드인 pop를 활용하여 추가

    def size(self):
        return len(self.items) # size는 큐의 크기를 반환

    def is_empty(self):
        return not self.items # not을 활용하여 부울 자료형으로 반환. 비어 있을 경우 True, 그렇지 않으면 False를 반환

    def __len__(self):
        return len(self.items) # 매직 메서드를 활용하여 클래스에 'len() 함수' 적용 가능

    def __str__(self):
        return f"{self.items}" # 매직 메서드를 활용하여 결괏값을 문자열 형태로 출력

테스트 코드

# 테스트 코드
if __name__ == "__main__":
    # 1. queue 할당
    print("------ #1. initialize queue ------")
    queue = Queue()
    print(f"queue : {queue}")
    print(f"size of queue : {queue.size()}")
    print(f"is queue empty? : {queue.is_empty()}")
    print()

    # 2. enqueue()
    print("------ #2. enqueue()  ------")
    queue.enqueue(1)
    print(f"enqueue 1 : {queue}")
    queue.enqueue(7)
    print(f"enqueue 7 : {queue}")
    queue.enqueue(4)
    print(f"enqueue 4 : {queue}")
    print(f"size of queue : {queue.size()}")
    print(f"is queue empty? : {queue.is_empty()}")
    print()

    # 3. dequeue()
    print("------ #3. dequeue()  ------")
    queue.dequeue()
    print(f"dequeue : {queue}")
    print(f"size of queue : {queue.size()}")
    queue.dequeue()
    print(f"dequeue : {queue}")
    print(f"size of queue : {queue.size()}")
    queue.dequeue()
    print(f"dequeue : {queue}")
    print(f"size of queue : {queue.size()}")
    print(f"is queue empty? : {queue.is_empty()}")

테스트 결과

------ #1. initialize queue ------
queue : []
size of queue : 0
is queue empty? : True

------ #2. enqueue()  ------
enqueue 1 : [1]
enqueue 7 : [7, 1]
enqueue 4 : [4, 7, 1]
size of queue : 3
is queue empty? : False

------ #3. dequeue()  ------
dequeue : [4, 7]
size of queue : 2
dequeue : [4]
size of queue : 1
dequeue : []
size of queue : 0
is queue empty? : True