Queue

큐(Queue)는 이전에 배운 스택(Stack)과는 다르게, 항목이 들어온 순서대로 접근이 가능하다. 즉, 먼저 들어온 데이터 순으로 먼저 나가는 선입선출(first in, first out, FIFO) 구조이다. 영화관에서 표를 발행할 때를 생각하면, 쉽게 이해할 수 있다. 흔히 발권기 앞에서 줄을 서서 차례대로 표를 발권하는데, 이때 먼저 줄을 선 순서대로 표를 발권한다. 큐의 동작도 이와 같다. 큐의 시간 복잡도는 O(1)이다.

• enqueue : 큐 뒤쪽에 항목을 삽입한다.
• dequeue : 큐 앞쪽의 항목을 반환하는 동시에 삭제한다.
• peek/front : 큐 앞쪽의 항목을 조회한다.
• empty : 큐가 비어있는지 확인한다.
• size : 큐의 크기를 확인한다.

Python에서 리스트를 이용하여 큐를 구현할 수 있다.

class Queue(object):
	def __init__(self):
    	self.items = []
        
	def isEmpty(self):
    	return not bool(self.items)
        
    def enqueue(self, item):
    	self.items.insert(0, item)
        
    def dequeue(self):
    	value = self.items.pop()
        if value is not None:
        	return value
        else:
        	print("Queue is empty.")
            
    def size(self):
    	return len(self.items)
        
    def peek(self):
    	if self.items:
        	return self.items[-1]
        else:
        	print("Queue is empty.")
            
    def __repr__(self):
    	return repr(self.items)

혹은 노드의 컨테이너로 큐를 구현할 수도 있다.

class Node(object):
	def __init__(self, value=None, pointer=None):
    	self.value = value
        self.pointer = pointer
        
class LinkedQueue(object):
	def __init__(self):
    	self.head = None
        self.tail = None
        self.count = 0
        
    def isEmpty(self):
    	return not bool(self.head)
        
    def dequeue(self):
    	if self.head:
        	value = self.head.value
        	self.head = self.head.pointer
            self.count -= 1
            return value
        else:
        	print("Queue is empty.")
            
    def enqueue(self, value):
    	node = Node(value)
        if not self.head:
        	self.head = node
            self.tail = node
        else:
        	if self.tail:
            	self.tail.pointer = node
            self.tail = node
        self.count += 1
        
    def size(self):
    	return self.count
        
    def peek(self):
    	return self.head.value
        
    def print(self):
    	node = self.head
        while node:
        	print(node.value, end=" ")
            node = node.pointer
        print()

큐를 구현하기 위한 코드는 복잡해 보이지만, 스택의 코드와 크게 다른 점은 없다. 스택을 구현할 수 있고, 큐는 선입선출이라는 점만 기억한다면 큐도 쉽게 구현할 수 있다. 큐는 스택과는 다르게 너비 우선 탐색(BFS)에서 유용하게 사용된다.

출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음, 최길우 옮김