[Data Structure] Queue (큐)

* Queue (큐)

큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다.
예를 들면 a, b, c 순서로 enqueue하고 큐에 있는 값들을 모두 dequeue하면 a, b, c 순서로 나오게 됩니다.
또한 큐에는 size, front, empty라는 함수가 있으며 size는 큐에 들어있는 값들의 수를 반환하는 함수이고, front은 큐에서 가장 먼저 삽입된 값을 반환하는 함수, empty는 큐가 비어 있는지 여부를 반환하는 함수입니다.

<그림 1> enqueue

<그림 2> dequeue

그리고 이러한 큐를 만드는 방법에는 2가지 방법이 있습니다. 하나는 배열을 이용한 방법이고, 다른 하나는 링크드 리스트를 이용한 방법입니다.

1) 배열을 이용한 방법에서는 삽입될 위치인 큐의 마지막 부분을 저장하는 변수 rear와 큐의 처음 부분을 저장하는 변수 front가 필요합니다. 또한 큐의 데이터 개수를 저장하는 변수 size를 이용하여 큐의 크기(큐에 들어있는 요소의 수)를 빠르게 알 수 있습니다. 또한 큐의 크기가 0일 경우 큐가 비어 있는 것이므로 비어 있는지 여부도 쉽게 알 수 있습니다. 따라서 배열로 구현하기 위해서는 값들을 담을 배열과 큐의 처음 위치와 마지막 위치(삽입될 위치)를 저장하는 변수가 필요합니다. 또한 enqueue과정과 dequeue과정에서 각각 rear index, front index가 점점 뒤로 밀려나기 때문에 이를 효율적으로 구성하려면 환형 배열로 구현해주어야 합니다.

<그림 3> 환형 배열로 구현한 큐의 dequeue

<그림 4> 환형 배열로 구현한 큐의 enqueue

2) 링크드 리스트를 이용한 방법에서는 값과 다음 노드의 위치를 저장하는 큐 노드들을 이용할 것이며 마지막으로 삽입된 노드의 위치를 저장하는 노드형 포인터 rear와 큐의 가장 앞 노드의 위치를 저장하는 노드형 포인터 front, 노드들의 수를 저장하는 변수 size가 필요합니다. front와 rear는 초기화시 처음에 널 값을 넣어주고, enqueue할 경우 이전에 rear의 next는 새로 삽입하는 노드가 되고, 새로 삽입되는 노드가 rear가 됩니다. dequeue할 경우 이전의 Head의 next가 Head가 되고, 이전의 head는 메모리 할당 해제 시킵니다.

<그림 5> 링크드 리스트로 구현한 queue

* 출처 & 참고 링크

Samsung CodeGround

Stack & Queue & PriorityQueue