자료구조 <Queue> 알고리즘 이해

Queue

롤에서 개인큐라는 말처럼

순서대로 잡아준다는 소리

먼저 탐색하기 시작한 사람부터 먼저 잡아주려는 속성때문에

롤에서 말하는 솔로큐라는 말을 하는 것이다.

선입선출(first-in-first-out)구조이다.

위에서 데이터를 넣었을 때 먼저 넣은 데이터부터 아래로 꺼낼 수 있다.

큐가 실제로 응용되고 있는 대표적인 분야는 은행 번호표이다.

버튼을 누르면 구조에 해당하는 번호가 삽입되고, 순차적으로 먼저 들어간 번호부터 처리되어 창구에서 번호가 호출되게 된다.

뿐만 아니라 수강신청 대기렬도 큐 구조를 활용한 예시로 들 수 있다.

먼저 들어온 데이터를 순차적으로 처리해야 되는 다양한 상황에 활용할 수 있는 것이 ‘큐’ 구조이다.

 

큐는 들어오는 곳과 나가는 곳이 다르다.

그래서 변수는 두개 필요하다.

first(먼저)와 rear(후방)이라는 두 개의 변수가 필요하다.

큐를 생각없이 구현했을 때 뒤로 가다가 마지막 지점에 도착하면 연장할 지점이 없진다는 것이 문제이다.

 

데이터를 더 추가하기 위해서 r을 인덱스가 0인 위치로 이동시켜야 한다.

그리고 이러한 방식으로 문제를 해결한 것이 바로 “원형 큐”이다.

배열의 머리와 끝을 연결한 구조를 원의 형태로 바라본다.

전체 코드

코드 한 줄씩 해석하기