[Algorithm-Basic]Queue

• 큐의 구조.

• __init__(self) : 초기화 함수 (스택과는 달리 front 를 가짐.)
• enqueue(self, val) : 삽입 함수.
• dequeue(self) : 삭제 함수. front 와 queue의 길이를 비교하여 같으면 queue는 비어있는 것.

---

• 큐의 활용 : Josephus problem

n 이라는 사람의 총 수가 주어지고,

k 라는 몇번째 사람이 죽을 것인지를 알려주면,

최종적으로 살아남는 사람을 구하는 것.

 

---

• 큐를 활용한 풀이 : n = 9, k = 3 일 때 Josephus problem

              1  2  3  4  5  6  7  8  9

              f                            r

   1회전 :          k         k         k      → k가 아닌 나머지는 dequeue 하자마자 enqueue. k는 그냥 dequeue.

 -------------------------------------------          

              1  2  4  5  7  8  

              f                 r

   2회전 :          k         k                  → k가 아닌 나머지는 dequeue 하자마자 enqueue. k는 그냥 dequeue.

 -------------------------------------------   

              1  2  5  7

              f          r     

   3회전 :          k

 -------------------------------------------  

              1  2  7

   4회전 :         k

 -------------------------------------------

              1  2

---

• Dequeue 

• Dequeue == Stack + Queue