Queue 구현하기

큐(Queue)라는 자료구조는 기본적으로 FIFO(First-in First-out) 즉, 선입선출의 자료구조입니다. Queue를 직접구현하려고 할 때, 어떻게 구현하셨나요? 자료구조를 학습하는 책이나 강의에 따라 천차만별이겠지만 크게 두 가지방법으로 추릴 수 있을 것 같습니다.
1. 배열(Array)로 구현하거나
2. 연결 리스트(Linked List)로 구현하는 것이죠.

저는 현재 진행중인 프로젝트에서 Queuing을 해야하는 경우가 생겨 큐를 직접 구현하게 되었는데, 이때 처음으로 배열을 구현했습니다.
그 이유는 이번 프로젝트는 성능이 중요하기에 "배열이 빠르다"라는 근거로 배열을 선택하여 구현하였습니다. 그런데 "배열이 빠르다"라는 문장에 오류가 있음을 깨닫고... 배열과 연결 리스트에 대한 생각을 다시해보게 되어 그 생각을 공유하려합니다!

배열은 빠르다?

배열의 빠름을 논하기 전에 배열과 연결 리스트에 대해 간단히 알아봅시다.

배열(Array)

배열은 고정된 메모리 공간에 Sequential하게 데이터를 담을 수 있는 그릇입니다. 그 특징으로는 어떠한 위치로든 O(1)의 시간복잡도로 접근할 수 있습니다. 이 때문에 필요한 데이터의 위치를 정확히 알고 있다면 배열만큼 빠를 수는 없습니다. 하지만 그 대가로 유연성이 없습니다. 처음에 정해진 배열의 크기는 고정이며 그 크기 이상으로 줄어들 수도, 늘어날 수도 없습니다. 이런 단점을 극복하기 위해 벡터(Vector)라는 자료구조가 있는데, 이는 배열의 크기가 늘어날 때 재할당과 복사가 일어나기에 상당히 비싼 연산을 거치게 되어 성능이 중요한 프로그램에서 기용하기엔 부적절할 가능성이 높습니다. 그 늘어나는 것을 대비해여 넉넉하게 배열의 크기를 잡아놓아도 문제입니다. 너무 넉넉하게 배열의 크기를 설정하면 남는 공간이 그만큼 많아지기 때문이죠.
더하여 데이터의 순서를 보장하면서 삭제나 삽입의 비용이 크게 듭니다.
정리해보면,

• 장점: 데이터에 접근할 때, 그 위치를 정확히 알고 있는 경우 매우 빠르게 접근이 가능하다.
• 단점: 크기가 정적이며, 이를 해결하려면 많은 연산 비용을 치르거나 메모리를 낭비해야한다. 또한 데이터의 삭제나 삽입이 비교적 비싸다.

연결 리스트(Linked List)

연결 리스트는 동적으로 Sequential하게 데이터를 담을 수 있는 그릇입니다. 배열과 상반되게 하드웨어의 제약이 없다면 무한하게 데이터를 담을 수 있습니다. 그대신 데이터의 접근에 O(n)의 시간복잡도를 지닙니다. 데이터의 개수가 많지 않다면 크게 문제될 사항은 아니지만 데이터의 개수가 많다면 이때문에 성능이 많이 저하될 수 있습니다. 이런 단점을 해소하기위한 BST(Binary Search Tree) 등의 자료구조가 있습니다.
더하여 각 데이터가 하나의 노드로써 취급되고 포인터로 연결되어 삽입, 삭제가 배열에 비해 자유롭습니다.
정리해보면,

• 장점: 자료구조의 크기가 동적이기에 낭비되는 메모리 공간이 없고 하드웨어가 허락하는 한 무한하게 데이터를 담을 수 있다. 또한 데이터의 삭제나 삽입이 비교적 자유롭다.
• 단점: 데이터의 정확한 위치를 알고 있어도 접근하는데 O(n)의 시간이 소요된다.

"배열은 빠르다"가 참인 경우는

앞서 살펴보아 알 수 있듯, "배열은 빠르다"가 참인 경우 중 하나는 데이터에 접근하는 경우이고 보다 정확히 하면 "데이터의 위치를 정확히 아는 상태에서 그 위치에 접근하는 경우"입니다. 더 정확히하면 "접근하고자 하는 데이터의 위치가 불특정하면서 데이터의 위치를 정확히 알고 그 위치에 접근하고자 할 때"입니다. 제가 진행중인 프로젝트에서 큐는 반드시 맨 뒤 혹은 맨 앞의 데이터만 접근합니다. 즉, 데이터의 위치가 특정되어 있습니다. 거기에 더하여 큐에 삽입되는 데이터의 개수가 매우 동적입니다. 그렇기에 배열의 장점이 크게 발휘될 수 있는 상황이 아니었죠. 이러한 근거로 배열로 구현한 큐를 연결 리스트로 변경하게됩니다.

당연히 연결리스트로 해야하는거 아냐...?

사실 제 상황에서는 큐를 배열로 구현하느나 연결 리스트로 구현하느냐하는 질문자체가 우문일 수도 있겠습니다. 큐를 사용한다는 것 자체로부터 "데이터가 Sequential해야하고 데이터의 접근을 FIFO로 하며 데이터의 개수가 고정적이지 않다"는 전제가 깔려있습니다. 이런상황에는 크게 고민없이 연결 리스트가 적합한 구현방법이라고 밖엔... 자료구조나 알고리듬이 개발자에게 기본 상식과도 같은 지식으로 자리매김했다고 생각합니다. 공부를 하는 것도 물론 필요한 일이지만 그 지식에 대한 통찰(너무 거창하지만 특별히 표현할 말이 없네요...) 혹은 이해도를 키우는 데는 실제 프로그램에 적용시켜보는 것 만큼 좋은 방법이 없는 것 같습니다. 그래도 간접체험의 의미에서 제 글이 조금이나마 도움이 되었으면 좋겠습니다!