Queue・FIFO(First In First Out)

 

 

Queue 설명 

먼저 들어온 데이터가 먼저 나가는 구조이다.

선입선출(FIFO:First In First Out) 구조라고 한다.

 

Stack은 한 쪽이 막혀있어 입구와 출구가 하나라면,

Queue는 입구와 출구가 따로있다.

 

Queue는 연결 리스트(linked list)로 구현이 되는데 python에서 queue 구현을 위해 deque() 함수를 제공한다.

Import하여 쉽게 사용하면 된다.

 

 

List 자료구조가 있는데 왜 굳이 queue를 사용할까 ?

Linked list는 제일 앞의 요소를 꺼낼 때 head 노드를 두 번째 노드로 바꾸고 head 노드였던 자료는 queue에서 빠져나온다. 이는 빅오 표기법에 따라 O(1)이라는 매우 빠른 연산이 가능하다. 하지만 array list는 순서대로 배열되어 있기 때문에 0번 index를 제거할 때, 모든 index를 한 칸씩 앞으로 옮겨야 하는 O(N)이라는 연산이 발생한다. 따라서 선입선출의 방식으로 문제를 해결해야 할 때, list는 N번의 연산을 하고 queue는 1번의 연산만 하기 때문에 list를 사용하면 시간초과 문제가 발생할 수도 있다.

 

 

deque 라이브러리

from collections import deque

dq = deque() # 덱 생성

dq.append() # 가장 오른쪽에 원소 삽입
dq.appendleft() # 가장 왼쪽에 원소 삽입

dq.pop() # 가장 오른쪽 원소 반환 
dq.popleft() # 가장 왼쪽 원소 반환

dq.clear() # 모든 원소 제거

dq.copy() # 덱 복사

dq.count(x) # x와 같은 원소 개수 계산

 

---

 

문제 유형 

용배와 친구들은 '007 게임'을 하려한다. 번호표를 가진 n명의 친구들이 원탁자에 앉아서 게임을 하는데, 1번부터 시작해서 '0,0,7,빵' 소리를 외치며 4번째 친구가 빵을 외치면 그 다음 5번인 친구는 탈락하게 되고 6번부터 다시 '0,0,7,빵'을 하게 되면 10번 친구가 탈락한다.