큐(Queue)

FIFO 구조를 가진 순차적 자료구조

class Queue:
    def __init__(self):
        self.items = []
        self.frontIndex = 0
    
    def __str__(self):
        return str(self.items)

    def enqueue(self,val):
        self.items.append(val)

    def dequeue(self):
        if self.frontIndex == len(self.items):
            print("Queue is empty")
            return None
        else:
            x = self.items[self.frontIndex]
            self.frontIndex += 1
            return x

주요 메서드

• enqueue : 파이썬 list의 append와 동일하게 활용

• dequeue : 스택과 다르게 먼저 들어간 데이터가 먼저 삭제되어야 하므로, items 리스트의 맨 앞 인덱스에 해당하는 데이터를 삭제해야 한다. 위 코드는 리스트의 데이터를 직접 삭제하지 않고, frontIndex를 한칸 뒤로 옮기는 방식으로 구현

• str : str(인스턴스)를 호출하면 리스트 객체인 인스턴스.item가 문자열로 변환되어 출력되는 특수메서드

수행시간

스택과 마찬가지로 enqueue/dequeue 모두 O(1)

Misc::

append/pop, appendleft/popleft가 모두 가능한 stack + queue 개념의 deque(double-ended queue)가 있다. 파이썬에서는 collections.deque에서 지원

큐를 활용한 Josephus 문제

n명이 원형으로 서있을 때, 원을 돌면서 매 k번째 사람이 죽으며, 마지막 사람이 남을 때까지 반복한다.

def Josephus(n,k):
    a = Queue()
    for i in range(n):
        a.enqueue(i+1)		# 알아보기 쉽게 0이 아닌 1부터 큐에 삽입
    for i,each in enumerate(a.items):
        if (i+1) % k != 0:	# k번째 사람이 아니면, 큐에서 빼고 바로 큐의 맨 뒤로 보낸다
            a.dequeue()
            a.enqueue(each)
        else:
            a.dequeue()		# k번째 사람이면 큐에서 완전히 뺀다
    return print(a.items[a.frontIndex-1])
    
 Josephus(6,2) # 5   -> 5번째 사람이 살아남는다