[자료구조] 큐(Queue)

큐(Queue) 구조에 대해서 포스팅하겠습니다. 

 

큐의 기본구조는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조를 뜻합니다.

예를 들어,

만약 그림처럼 알파벳을 순서대로 넣는다고 하면 

순서대로 데이터를 넣고 데이터를 꺼낼때 순서대로 나오게 됩니다. 

그림에선 데이터를 처음 꺼내면 A가 나오게 되고 A는 꺼냈으니깐 데이터 내에 없고 

다시 데이터를 꺼내면 B가 다음 순서로 나오게 됩니다.

이를 FIFO(First-In, First-Out) 또는 LILO(Last-In,Last-Out) 라 합니다.

 

제가 그림에 Enqueue, Dequeue를 써 넣었는데 큐 구조에서 쓰이는 용어로 의미는 아래와 같습니다.

• Enqueue : 큐에 데이터를 넣는 기능(Put)
• Dequeue : 큐에서 데이터를 꺼내는 기능(Get)

 

파이썬으로 큐(Queue) 구현하기

큐(Queue) 구조를 파이썬으로 구현해보겠습니다.

일반적인 파이썬 언어로 구현할 수도 있지만

파이썬에는 queue 라이브러리가 있어서 간편하게 구현할 수 있는데

Queue(),LifoQueue(),Priority() 세가지 큐 구조를 제공하고 있습니다.

• Queue() : 가장 일반적인 큐 자료 구조
• LifoQueue() : Last-In , First-Out 구조(나중에 입력된 데이터가 먼저 출력되는 구조)
• PriorityQueue() : 우선수위가 높은 순으로 데이터 출력

 

Queue()

기본구조인 FIFO를 구현해보겠습니다. FIFO는 Queue() 함수를 사용합니다.

import queue
data = queue.Queue() #FIFO(First-In,First-Out)

#Enqueue
data.put('A')
data.put('B')
data.put('C')
data.put('D')
data.put('E')

#Size
data.qsize()
>>> 5

#Dequeue
data.get()
>>> 'A'

data.qsize()   # 'A' 는 데이터에서 나감
>>> 4
type(data.qsize())   
>>> int

for i in range(data.qsize()):
    print(data.get())
>>> B
>>> C
>>> D
>>> E

데이터가 나오는 순서가 정해져 있으므로 get() 괄호 안에 넣을것이 없습니다.

 

 

LifoQueue()

가장 나중에 넣은 데이터가 가장 먼저 나오는 구조입니다.

data = queue.LifoQueue()

data.put('A')
data.put('B')
data.put('C')
data.put('D')
data.put('E')

data.get()
>>> 'E'

 

PriorityQueue()

우선순위 순서대로 나옵니다. 우선순위를 정해야 하기 때문에 튜플로 데이터를 넣게 됩니다.

data = queue.PriorityQueue()

data.put((8,'A'))   #튜플 (우선순위,데이터)
data.put((10,'B'))
data.put((3,'C'))
data.put((1,'D'))
data.put((15,'E'))

data.get()    #튜플구조로 나옴
>>> (1,'D')
type(data.get())
>>> tuple

data.get()[1]  # 데이터만 원한다면 인덱스를 덧붙여야 한다.
>>> 'A'

 

리스트로 큐 구현

라이브러리를 쓰지 않고도 큐를 구현할 수 있습니다.

queue_list = []

# enqueue, dequeue 필요

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

#Example
data_list = ['A','B','C','D','E']
for idx in data_list:
    enqueue(idx)

len(queue_list)
>>> 5

dequeue()
>>> 'A'

 

많은 일을 하는 컴퓨터에게 일의 순서를 주고 싶다면 큐를 사용해보면 좋을 것 같습니다.

이상으로 포스팅을 마치겠습니다.