큐 (Queues)

큐란?

자료를 보관할 수 있는 선형구조로, 넣을 떄에는 한 쪽 끝에서 밀어 넣어야(enqueue 인큐연산)하고, 꺼낼 떄에는 반대 쪽에서 뽑아 꺼내야(dequeue 디큐연산)하는 제약이 있다.

이처럼 먼저 넣은 것이 가장 먼저 꺼내어지는 성질 때문에 큐를 다른 말로는 선입선출(FIFO, first-in first-out) 자료 구조라고도 한다.

 

 

큐의 활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
• 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
• 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

 

큐가 지원하는 연산 목록

• size() - 현재 큐에 들어 있는 데이터 원소의 수를 구한다.
• isEmpty() - 현재 큐가 비어 있는지를 판단한다.
• enqueue(x) - 데이터 원소 x를 큐에 추가한다.
• dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거하면서 반환한다.
• peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환한다.

 

배열을 이용한 큐 파이썬 구현

class ArrayQueue:
	def __init__(self):
    	self.data = []
    
    def size(self):
    	retrun len(self.data)
    
    def isEmpty(self):
    	return self.size() == 0
        
    def enqueue(self, item):
    	self.data.append(item)
        
    def dequeue(self):
    	return self.data.pop(0)
        
    def peek(self):
    	return self.data[0]
    

Q = ArrayQueue()
Q.enqueue(5)
Q.enqueue(8)
print(Q.data) # [5, 8]

print(Q.dequeue()) # 5
print(Q.dequeue()) # 8

 

큐 라이브러리

# pythonds 라이브러리를 설치
from pythonds.basic.queue import Queue
Q = Queue()
dir(Q)

# ['__doc__', '__init__', '__module__', 'isEmpty', 'items', 'peek', 'pop', 'push', 'size']