[C 자료구조] 큐(Queue)

큐의 의미

큐의 사전적 의미를 살펴보면 무엇인가를 기다리는 줄이다.

사전적 의미를 보면 특성을 바로 알 수 있는데, 맛집을 기다리는 사람들의 줄을 생각해보자.

당연히 먼저 선 사람이 나중에 선 사람보다 음식점에 먼저 들어갈 것이다. 

이처럼 큐는 FIFO(First-In First-Out) 선입 선출의 특성을 가지고 있다.

 

자료구조에서 큐는 사전적 의미와 마찬가지로 무언가를 처리하기 위해 대기 중인 자료의 줄이라고 생각하면 된다.

이는 대기행렬(waiting line)이라고도 한다.

 

그러면 큐는 어떨 때 사용될까?

실제 현실 세계를 정확히 표현하기 위해 사용된다.

선입선출이 큐의 특성이기 때문에 현실세계에서 선입선출 특성을 가진 다양한 시스템들을 나타낼 때 큐를 사용한다.

ex) 운영체제의 프린터 스풀러

 

큐란?

그럼 이제 큐의 구조에 대해서 더 살펴보자

큐는 데이터를 차례대로 저장하는 선형 자료구조이다.

https://cloudstudying.kr/lectures/142

위 그림을 보면 양 옆에 뚤려있는 걸 볼 수 있는데 그렇기 때문에 먼저 들어간 것이 먼저 나올 수 있다.

 

맨 처음 추가된 데이터를 front라고 하고, 맨 나중에 추가된 데이터를 rear라고 한다.

큐의 크기는 저장할 수 있는 최대 데이터의 개수를 말한다.

enqueue는 새로운 데이터를 추가하는 연산이고, dequeue는 기존 데이터를 반환하는 연산이다. 추가로 dequeue는 데이터를 삭제하면서 반환하고, peek는 삭제하지는 않고 값을 반환만 하는 연산이다.

 

enqueue	dequeue	peek
새로운 데이터 추가 rear를 오른쪽으로 한 칸 이동시킨 후 데이터 추가	데이터 제거 및 반환 front가 가리키는 데이터를 제거 이때 front는 한 칸 오른쪽으로 이동시킴	데이터 반환 가장 오래된(먼저 추가된) 데이터 반환 이때 데이터는 제거하지 않음

 

배열 선형 큐

배열로 구현한 큐

큐는 배열이나 포인터로 구현할 수 있다.

배열로 구현하는 것이 포인터로 구현하는 것 보다 편리하다.

 

그러나 단점들이 있는데,

첫 번째 미리 크기를 지정해야 하는 제약 사항 - 1차원 배열을 사용하다보니 어쩔 수 없이 크기를 지정해야 한다는 제약이 있다.

두 번째 배열의 앞부분부터 사용할 수 없는 빈 곳이 생김 - dequeue 연산할 때 front 위치를 한 칸 오른쪽으로 이동시키기 때문에 그 전의 칸은 사용할 수 없어 자원낭비라는 치명적인 단점이 생긴다.

https://hsc-tech.tistory.com/1

 

그래서 배열 선형 큐 보다는 배열 원형 큐를 사용하거나 포인터로 구현한 연결 큐를 사용하는 것이 좋다.

 

배열 원형 큐

 

https://hsc-tech.tistory.com/1

 

배열 선형 큐의 단점을 해결한 큐

배열 원형 큐도 이름에 배열이 들어간 것을 보아 배열을 사용한 큐임을 알 수 있다, 

단지 개념상으로 원형으로 배열의 인덱스를 변화시켜주는 것이다.