[자료구조] 큐(Queue) 개념 이해하기

큐(Queue)란 무엇인가?

큐는 먼저 입력된 자료가 먼저 출력되고 늦게 입력된 자료는 나중에 출력되는 선입선출(First In First Out: FIFO), 후입후출(Last In Last Out: LILO) 형태의 순차 자료구조이다. 순차 구조이기 때문에 논리적 구조가 순서를 가진 한줄로 표현할 수 있고 한쪽에서는 입력만 반대쪽에서는 출력만 되는 특징이 있다.

#그림으로 설명

 

순차 리스트 또는 연결 리스트로 구현할 수 있는데, 각 종류의 리스트로 구현된 큐를 순차 큐, 연결 큐라고 하고 순차 큐는 다시 운영 방식에 따라 선형 큐, 이동 큐, 원형 큐로 구분된다.

#표로 구분

 

선형 큐

리스트의 시작부터 끝까지 차례로 데이터를 추가하고 마지막 원소가 리스트의 끝에 도달하면 포화 상태라고 판단한다.

추가 연산 시 마지막으로 삽입된 자료의 다음 자리, 즉 리스트의 끝에 가장 가까운 자료의 뒤에 추가한다.

삭제 연사 시 리스트의 시작에 가장 가까운 자료를 삭제하고 자료의 이동은 일어나지 않는다. 즉 자료가 삭제됨에 따라 리스트의 앞쪽엔 빈자리가 늘어간다.

#사진 삽입

 

이동 큐

리스트의 시작부터 끝까지 차례로 데이터를 추가하고 마지막 원소가 리스트의 끝에 도달한 것만으로는 포화 상태라고 판단하지 않는다. 

추가 연산 시 마지막으로 삽입된 자료의 다음 자리, 즉 리스트의 끝에 가장 가까운 자료의 뒤에 추가한다.

삭제 연사 시 리스트의 시작에 가장 가까운 자료를 삭제하고 자료의 이동은 일어나지 않는다. 즉 자료가 삭제됨에 따라 리스트의 앞쪽엔 빈자리가 늘어간다. 그러나 마지막 원소가 리스트의 끝에 도달했음에도 리스트의 시작부분에 자료가 삭제되어 빈자리가 있다면 리스트에 존재하는 자료 전체를 순서를 지킨채 맨 처음 자료가 리스트의 맨 앞부분에 존재하도록 앞으로 이동시켜준다. 그 후에는 다시 자료를 받고 삭제하는 과정에 걸쳐 자료가 리스트의 처음부터 끝까지 모두 존재한다면 포화상태라고 판정한다. 

삭제 연산이 빈번하다면 포화상태로 판정을 내리기 위해서 많은 이동이 요구되고 이를 해결하기 위해 원형 큐를 사용한다.

#사진 삽입

 

원형 큐

마지막에 추가된 자료의 뒤에 데이터를 추가하고 마지막 원소가 리스트의 끝에 도달하고 처음 원소가 리스트의 앞에 존재한다고 해서 포화 상태라고 판정하지 않는다. 원형 큐는 빈자리 없이 모든 공간에 자료가 차있어야 포화상태로 판단한다. 특이한 점은 리스트에 자료에 저장할 때 논리적인 순서와 물리적인 순서가 일치하지 않을 수도 있다. 그 이유는 원형 큐에서는 마지막으로 입력받은 원소가 리스트의 끝에 도달했는데 리스트의 앞부분에는 자료의 삭제(출력)으로 인해 빈자리가 있을 경우 이후에 입력받는 자료들을 자료의 시작부분부터 다시 저장한다. 비유를 하자면 점점 길이가 길어지는 뱀이 있는데, 그 뱀을 입구와 출구가 각각 하나인 통에 넣어 보관하되 꼬리가 통보다 길어져 통에 더 이상 보관할 수 없을 때 통의 맨 앞부분이 머리로 막혀있다면 포화, 그렇지 않다면 꼬리를 돌려 다시 통의 앞부분으로 밀어넣어 꼬리와 머리가 맞닿게 하는 방식과 같다. 

추가 연산 시 마지막으로 입력한 원소가 리스트의 끝에 도달했다면 리스트의 앞 공간이 남는지 보고 남아있다면 리스트의 앞부분부터 다시 원소를 입력하고 그렇지 않다면 포화상태라고 판단해 더 이상 원소를 추가하지 않는다.

추가 연산 시 마지막으로 입력한 원소가 리스트의 끝에 도달하지 않았다면 마지막 원소의 뒤에 원소를 추가한다.

삭제 연산 시 가장 오래전에 입력받은 원소를 삭제합니다

 

 

 

연결 큐