데이터 구조2. 큐(Queue) - 파이썬에서 구현하기

오늘 알아볼 데이터 구조는 Queue입니다. 큐는 쉽게 말해서 줄을 서는 방식과 비슷한데요, 이를 구현하는 방식은 크게 LIFO와 FIFO가 있고 한국말로는 후입선출 선입선출 등으로 불리고 있습니다. 이것에 대한 개념부터 코드까지 함께 안내해드리도록 하겠습니다. 

 

 

목차

1. Queue에 대한 기본 이해

2. Queue의 종류 및 파이썬 구현 방법

3. 실전 문제 풀이 

 

 

1. Queue에 대한 기본 이해 

(1) 개념

기본적으로 Queue는 번역을 하게 되면 대기줄 혹은 줄 이라고 번역할 수 있습니다. 즉 데이터에서도 대기줄이 있고, 그게 상황에 따라서 길어질 수도 혹은 짧아질 수도 있다는 뜻이죠. 

 

실전적인 개념으로 보면, 재고 관리를 하는 데이터에 있어서 출고 완료된 데이터는 굳이 더 저장할 필요가 없을 수도 있고, 새로 들어온 주문은 다시 추가할 필요가 있고, 이에 대해서 일일이 사람이 관리하는 것보다 알고리즘을 통해 자연스럽게 관리할 수 있으면 좋겠죠.

 

쉽게 말해 "코딩을 통해 대기열/대기줄을 구현한다"라고 이해하시면 될 것 같습니다. 

 

 

(2) Queue의 종류

 

대기열을 관리할 때 가장 쉬운 방법은 선찬순이겠죠?? 하지만 먼저 예약을 했던 사람이나 일이 너무나도 중요해서 먼저 처리해야 하는 상황도 생기기 마련입니다. 이렇게 여러 상황에 대비할 수 있도록 코드로 구현할 수 있습니다. 

 

1) FIFO(First-in, First-Out) - 선찬순 관리 방식 / 선입선출

가장 일반적인 방식으로 선찬순으로 대기열을 관리하는 방식입니다. 제일 먼저 들어온 데이터를 먼저 처리한 뒤에 대기열에서 삭제하는 방식이죠. 

 

2) LIFO(Last-in, First-out) - 후입선출

LIFO 또한 굉장히 많이 쓰는 Queue 중에 하나로 후입선출 방식입니다. 나중에 들어온 데이터를 가장 먼저 처리하는 방식이죠. 

 

3) Priority Queue - 우선순위 관리 방식

개별 데이터에 우선 순위를 정하여 처리하는 방식입니다. 어떻게 보면 Queue를 활용하는 이유 중에 가장 큰 항목입니다. 데이터를 조금 더 디테일하게 관리할 수 있는 고도화된 방법이죠. 

 

 

2. Queue의 종류 및 파이썬 구현 방법

(1) FIFO

 

1) 기본 패키지 불러오기 

import queue
data = queue.Queue()

 

우선 파이썬에서는 편하게 queue라는 패키지를 import하면 자동적으로 Queue라는 데이터를 만들 수 있습니다. 

이렇게 아무런 조건 없이 Queue를 만들게 되면 자연스럽게 이것은 FIFO 방식으로 Queue 데이터 구조를 가지게 됩니다. 

 

2) 데이터 입력 및 추출 방식

 

-데이터의 입력

데이터 입력과 추출은 .put() 과 .get() 메소드로 구현할 수 있습니다. 또한 Queue의 길이를 알고 싶으시다면 .qsize() 메소드를 활용하실 수 있습니다. 

data.put("enjoy")
data.put('python')
data.put(1)
data.put(100)

자 이렇게 데이터를 넣어보았습니다. 이렇게 진행했을 때 Queue의 길이는 다음과 같이 표현될 수 있습니다. 

 

Queue 코딩의 예시

 

 

- 데이터의 출력

이제 위에서 형성한 Queue에서 순차적으로 데이터를 추출해보도록 하겠습니다. 추출하는 방식은 data.get()으로 아무런 파라미터를 받지 않습니다. 그러면 선입선출 방식으로 데이터가 추출될 것입니다. 결과를 보시겠습니다. 

 

 

Queue에서 데이터 추출하는 방법 .get()

 

첫 번째로 나온 것은 'enjoy'라는 string 데이터이고, 그 결과 전체 데이터 길이는 3개로 줄었습니다. 이런식으로 계속 추출하고 진행해 나가면, 결국 데이터 0일 때까지 데이터를 뽑을 수 있을 거에요.

 

 

 

(2) LIFO - 후입선출 방식

 

LIFO 같은 경우 FIFO와 거의 동일하게 구현 가능하고, 다만 사용자가 그 논리가 반대라는 것을 이해하고 있으면 쉽게 활용할 수 있습니다. 

 

LIFO의 원리는 "나중에 들어간 데이터를 먼저 추출하다"라는 논리입니다. 이것만 기억하시고 아래처럼 데이터를 활용하실 수 있습니다. 

 

 

LIFO의 데이터 논리

 

FIFO와 동일한 데이터였을지라도, LIFO로 구현된 경우 맨 나중에 데이터가 입력된 것이 먼저 추출되는 현상을 볼 수 있습니다. 이점을 기억하여 실무에서 활용하시면 될 것 같습니다. 

 

(3) Priority Queue 구현 - 우선순위 데이터 관리 방식

 

사실 Queue 데이터 구조에 있어서 가장 중요한 것이 될 것 같아요. 데이터를 관리할 때 순차적으로 관리하는 경우도 있겠지만 그렇지 않은 경우도 많거든요. 

 

그때 데이터에 중요도 혹은 우선순위를 정해서 관리를 해야만 해요. Priority Queue는 이런 고민을 한 번에 해결할 수 있는 아주 중요한 데이터 구조입니다. 

 

데이터 입력시 다른 Queue와는 다르게 우선선위 파라미터도 반드시 지정해주어야 해요. 

 

 

 

 

우선순위를 입력을 해준 것을 기반으로 데이터가 형성된 것을 볼 수 있습니다. 데이터를 입력할 때 "china"를 "US"보다 먼저 삽입하였더라도, 우선순위를 US에 12위로 지정함으로써 먼저 추출될 수 있도록 조정한 것입니다. 반대로 LIFO기반으로 Queue를 구현하면 출력되는 순서도 우선순위에 따라 반대가 되는 것으로 활용할 수도 있습니다.

 

 

3. 실전 문제 풀이- 직접 Queue 데이터 구조 함수 짜보기  

단순한 패키지를 활용하는 것이 아니라, 직접 함수로 구현해서 데이터 구조에 대한 이해도를 높여보는 시간을 갖도록 하겠습니다. 

queue_list = list()
 
def enqueue(data):
    queue_list.append(data)
    
def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

 

이전 시간에 배운 array/list 형태를 기본적으로 가져가고, 거기에 두 가지 기능을 만들어보았습니다. 하나는 데이터를 입력하는 방식이고, 다른 하나는 데이터를 추출하는 것입니다. 

 

이를 기반으로 FIFO 데이터 구조를 구현해보겠습니다. 아래의 사진 결과를 보시죠. 

 

 

FIFO Queue의 구현

 

우선 for loop를 사용하여 0부터 9까지의 데이터를 리스트에 넣었습니다. 그래서 결과를 볼 수 있듯이 [0,1,2 ~ ,8,9]까지 데이터가 입력된 것을 볼 수 있죠. 

 

이때 dequeue()라는 함수를 사용하니 0이라는 데이터가 추출되고, 리스트에서는 제거된 것을 볼 수 있습니다. 

 

그 이유는 함수에서 "del queue_list[0]"라는 논리를 삽입하였기 때문입니다. 이 부분의 코드는 LIFO 혹은 Priority Queue를 통해서 얼마든지 수정이 가능합니다. 

 

여기까지 Queue를 활용하는 방법에 대해서 알아보았습니다. 항상 정독하지 마시고, 필요한 부분만 꺼내가는 습관을 가져봐요~