챕터2-2. 자료구조 | 큐(Queue)

큐의 개념

# 큐는 무엇인가

- 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조

- 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out(FIFO) 라고도 한다.

- push와 pop을 진행하다보면 begin변수의 값은 계속 증가만 하기 때문에 배열이 꽉 차지 않은 상황임에도
   더이상 데이터를 집어넣을 수 없는 상황이 발생한다.
   이를 보완한 방법으로 '순환큐'라는 게 존재하는데 이는 심화과정이므로 나중에 공부하고 일단 아래 부분들만 알아두자.

 

# 직접 구현하기 위해 필요한 요소

- 데이터를 저장할 '배열' (링크드리스트로 구현할 수도 있다고 함)

- pop하면 나올 위치를 가리키는 'begin 변수'

- push가면 들어갈 위치를 가리키는 'end 변수'

 

# 큐의 연산

- push() : 큐에 자료를 넣는 연산(back의 위치에서 일어남)

- pop() : 큐에서 자료를 빼는 연산(front의 위치에서 일어남)

- front() : 큐의 가장 앞에 있는 자료를 보는 연산

- back() : 큐의 가장 뒤에 있는 자료를 보는 연산

- empty() : 큐가 비어있는지 아닌지를 알아보는 연산

- size() : 큐에 저장되어 있는 자료의 개수를 알아보는 연산

@  push 연산의 예시

queue[end] = val
end += 1

 

@  pop 연산의 예시

queue[begin] = 0        // 생략해도 될듯하다. 어차피 나중에 덮어쓰면 되므로
begin += 1

 

@  size 연산의 예시

size = end - begin

 

@  empty 연산의 예시

empty = (begin == end)

 

1) 초기화된 초기상태

 

2) push(3) 을 수행한 결과

3) push(6) 을 수행한 결과

4) pop() 을 수행한 결과

큐를 적용한 문제풀이

# 큐를 구현하는 문제

- https://www.acmicpc.net/problem/10845

@ 직접구현(C++) : 배열이용

@ C++의 경우에는 STL의 queue을 사용함

@ Java의 경우에는 java.util.Queue 사용함

@ python의 경우에는 Queue 모듈을 사용함

 

# 조세퍼스 문제

- https://www.acmicpc.net/problem/1158

- N = 7, K= 2 일 때 1개의 숫자를 제거하는데 필요한 횟수 : pop push pop (2pop 1push)

- N = 7, K= 3 일 때 1개의 숫자를 제거하는데 필요한 횟수 : pop push pop push pop (3pop, 2push)

- N = 7, K= 4 일 때 1개의 숫자를 제거하는데 필요한 횟수 : pop push pop push pop push pop (4pop, 3push)

- 따라서 N, K 가 주어지면 1개의 숫자를 제거하는게 필요한 횟수는 (Mpop, M-1push) 가 되고 이를 N개의 숫자에 대해 수행하면
   전체 시간복잡도는 O(N*(K+K-1)) = O(N*(2K-1)) = O(NK) 이다.
   1<=K<=N<=5000 이므로 최대 반복횟수는 5000^2 = 25000000 이고 이는 1억을 넘지 않으므로 
   큐를 이용한 방법을 사용해서 풀 수 있는 것이다.

N = 8, K = 3 일때의 예시

 

N= 8, K= 3 일때의 큐를 활용한 예시