큐 (Queue)

특징

• FIFO (First in, First out)규칙의 순차적 자료구조
• enqueue, dequeue로 데이터의 입출력을 한다.
• front, rear 각 맨 앞, 맨 뒤를 가리킨다.

Queue 활용 예시

1. Josephus Problem

n, k가 주어질 때 리스트 n에서 k번째 순서일 때 마다 dequeue 최종적으로 남은 값을 반환한다

ex)
n = 6, k = 2 1을 기준으로
1. 1 2 3 4 5 6 / 1, 3, 5 dequeue 후 enqueue 2, 4, 6 dequeue
2. 1 3 5 / 1 dequeue 후 enqueue 3 dequeue
3. 5 1 / 5 dequeue 후 enqueue, 1 dequeue

Stack + Queue = Dequeue ; python -> class deque

출처 : 신찬수 한국외대 교수님