파이썬과 컴퓨터 사이언스(데이터 구조) - 대표적인 데이터 구조4: 큐 (Queue)

5. 대표적인 데이터 구조4: 큐 (Queue)

  • 줄을 서는 행위와 유사
  • 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
    • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
    • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

알아둘 용어

  • Enqueue: 큐에 데이터를 넣는 기능
  • Dequeue: 큐에서 데이터를 꺼내는 기능
  • Visualgo 사이트에서 시연해보며 이해하기 (enqueue/dequeue 만 클릭해보며): https://visualgo.net/en/list

파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기

  • queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
  • 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
    • Queue(): 가장 일반적인 큐 자료 구조
    • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택과 유사 방식)
    • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

Queue()로 큐 만들기 (가장 일반적인 큐, FIFO(First-In, First-Out))

In [123]:
# 큐 만들기
import queue
data_queue = queue.Queue()
In [124]:
# 데이터 넣기
data_queue.put("korea")
data_queue.put(1)
In [125]:
# 큐 사이즈 확인하기
data_queue.qsize()
Out[125]:
2
In [126]:
# 데이터 꺼내기
data_queue.get()
Out[126]:
'korea'
In [127]:
# 데이터 꺼내지면 큐 사이즈도 줄어듬
data_queue.qsize()
Out[127]:
1


In [128]:
data_queue.get()
Out[128]:
1

LifoQueue()로 큐 만들기 (LILO(Last-In, Last-Out))

In [129]:
# LifoQueue 만들기
import queue
data_queue = queue.LifoQueue()
In [130]:
# 데이터 넣기
data_queue.put("korea")
data_queue.put(1)
In [131]:
# 데이터 꺼내기
data_queue.get()
Out[131]:
1

PriorityQueue()로 큐 만들기

In [132]:
# LifoQueue 만들기
import queue
data_queue = queue.PriorityQueue()
In [133]:
# 데이터 넣기
data_queue.put((10, "korea"))           # <-- (우선순위, 데이터) 형식의 튜플로 넣어야 함
data_queue.put((5, 1))                  # <-- (우선순위, 데이터) 형식의 튜플로 넣어야 함 
data_queue.put((15, "china"))           # <-- (우선순위, 데이터) 형식의 튜플로 넣어야 함


In [134]:
# 데이터 꺼내기 
data_queue.get()                        # <-- 우선순위값이 가장 낮은 데이터 순으로 출력 (1순위가 2순위보다 우선순위가 높죠!)
Out[134]:
(5, 1)
In [135]:
# 데이터 꺼내기
data_queue.get()
Out[135]:
(10, 'korea')
프로그래밍 연습
다음 추상 클래스를 상속받아서 리스트변수로 큐(FIFO) 클래스 만들어보기
  
# 추상 클래스 만들기
from abc import *

class AbstractQueue(metaclass=ABCMeta):

    @abstractmethod
    def enqueue(self, data):              # 데이터의 추가
        raise NotImplemented

    @abstractmethod    
    def dequeue(self):                     # 데이터의 꺼내오기
        raise NotImplemented
프로그래밍 연습
위 코드에서 큐 타입에 따라 FIFO, LILO 큐를 만들 수 있는 클래스 만들어보기
In [136]:
from abc import *

class AbstractQueue(metaclass=ABCMeta):

    @abstractmethod
    def enqueue(self, data):              # 데이터의 추가
        raise NotImplemented

    @abstractmethod
    def dequeue(self):                     # 데이터의 꺼내오기
        raise NotImplemented
In [137]:
class DaveQueue(AbstractQueue):
    def __init__(self):
        self.items = list()
    
    def enqueue(self, data):
        self.items.append(data)
    
    def dequeue(self):
        data = self.items[0]
        del self.items[0]
        return data

dave_queue = DaveQueue()
for num in range(10):
    dave_queue.enqueue(num)
print (dave_queue.dequeue())
0
프로그래밍 연습
객체 생성시 큐 타입을 FIFO, LILO로 지정할 수 있는클래스로 만들어보기 (클래스로 스택 구현해보기 참고하기)
프로그래밍 연습
객체 생성시 큐 타입을 FIFO, LILO, PriorityQueue까지 지정할 수 있는 클래스로 만들어보기 (클래스로 스택 구현해보기 참고하기)


In [139]:
from abc import *

class AbstractQueue(metaclass=ABCMeta):
    
    @abstractmethod
    def enqueue(self, data):              # 데이터의 추가
        raise NotImplemented

    @abstractmethod    
    def dequeue(self):                     # 데이터의 꺼내오기
        raise NotImplemented

import queue
class QueueSet(AbstractQueue):

    def __init__(self, type):
        if type == 1:
            self.data_queue = queue.Queue()
        elif type == 2:
            self.data_queue = queue.LifoQueue()
        else:
            self.data_queue = queue.PriorityQueue()
        
    def enqueue(self, data):
        self.data_queue.put(data)
    
    def dequeue(self):
        return self.data_queue.get()

fifo_queue = QueueSet(1)
for num in range(10):
    fifo_queue.enqueue(num)

for index in range(10):
    print (fifo_queue.dequeue())

lilo_queue = QueueSet(2)
for num in range(10):
    lilo_queue.enqueue(num)

for index in range(10):
    print (lilo_queue.dequeue())
    
priority_queue = QueueSet(3)
for num in range(10):
    priority_queue.enqueue((1, num))

for index in range(10):
    print (priority_queue.dequeue())
0
1
2
3
4
5
6
7
8
9
9
8
7
6
5
4
3
2
1
0
(1, 0)
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(1, 6)
(1, 7)
(1, 8)
(1, 9)