자료구조 큐 (Queue)

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록
https://www.youtube.com/watch?v=nqCNk_DmPio&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=11

앞서 배운 스택이 후입선출의 구조였다면, 큐는 선입선출(First-in First-Out)의 구조이다.
먼저 들어온 것이 먼저 나간다. 그래서 선착순 자료구조라고도 한다.

파이썬 리스트로 큐 구현하기 1

• enqueue(value): 큐의 가장 오른쪽 끝에 값을 삽입
• dequeue(): 큐의 가장 왼쪽 값을 삭제 후 리턴
• front(): 큐의 가장 왼쪽 값을 리턴
• len(): 큐의 저장된 값의 개수
• isEmpty(): 큐가 비었는지 알려줌

class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self, val):
        self.items.append(val)
    def dequeue(self):
        try:
            return self.items.pop(0)
        except IndexError:
            print("Queue is Empty")
    def front(self):
        try:
            return self.items[0]
        except:
            print("Queue is Empty")
    def __len__(self):
        return len(self.items)
    def isEmpty(self):
        return len(self)

파이썬 리스트로 큐 구현하기 2 (front_index)

1번의 방법에서 dequeue 연산을 제외한 모든 연산은 상수시간 O(1)에 수행된다.
파이썬의 리스트는 굉장히 유동적이기 때문에 리스트에 담긴 값의 개수가 변하면 원소의 인덱스도 자동으로 변한다.
dequeue는 가장 왼쪽에 있던 값을 지운다. 따라서 dequeue가 실행되면 가장 왼쪽에 있던 값의 빈자리를 메꾸기 위해 오른쪽에 있던 값들이 왼쪽으로 한 칸씩 이동하는 시간이 필요하다.
모든 연산이 상수시간에 수행되도록 하려면, dequeue 연산을 실제로 수행하는 것이 아니라 현재 큐에서 가장 왼쪽에 저장된 값의 인덱스를 front_index라는 변수에 따로 저장하여 관리해주면 된다.
dequeue 연산을 수행할 때마다 front_index에 1씩 더해주면 된다. (값은 여전히 큐에 남아있는 상태임)

class Queue:
    def __init__(self):
        self.items = []
        self.front_index = 0

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

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

    def front(self):
        if len(self.items) == 0 or self.front_index == len(self.items):
            print("Queue is empty")
        else:
            return self.items[self.front_index]

    def __len__(self):
        return len(self.items) - self.front_index

    def isEmpty(self):
        return len(self)

큐 활용 예: Josephus Problem

n과 k가 주어졌을 때 최종적으로 살아남는 사람의 번호는 몇 번인가
Josephus(n, k) 함수를 만들어 최종 생존자의 번호를 리턴하도록 작성.

1번부터 차례대로 큐에 enqueue
k-1개를 dequeue하고 dequeue하자마자 다시 enqueue
k번째 값은 그냥 dequeue
큐에 남아있는 값이 하나가 될 때까지 계속 수행

# 클래스로 Queue를 이미 구현했다고 가정

def Josephus(n, k):
    Q = Queue()

    for v in range(1, n + 1):  # 1번부터 차례대로 enqueue
        Q.enqueue(v)

    while len(Q) > 1:
        for i in range(1, k):  # k-1개를 dequeue하는 즉시 다시 enqueue
            Q.enqueue(Q.dequeue())
        Q.dequeue()  # k번째 값은 사라짐

    return Q.dequeue()  # 마지막에 남은 값 = 최종 생존자 리턴

관련 문제들 (차차 추가 예정)

(내가 풀어본 것 위주)
백준

문제 링크	풀이 링크
10845번 큐	바로가기