[자료구조] Queue에 대해 알아보고 구현해보기 (Swift)

Queue란?

Queue 자료구조는 선입선출(First In First Out)FIFO의 특성을 갖는 자료구조 입니다.
즉, 먼저 들어온 것이 가장 먼저 나가는 구조입니다.

맛집에 먼저 줄을 섰던 사람이 먼저 들어가는 것과 동일합니다.

예를 들어 1, 2, 3이란 원소가 Queue에 들어온다면?

Queue에 요소들이 이러한 식으로 들어와져 있을 것입니다.

pop을 하게 된다면?

1이 가장 먼저 들어왔기 때문에 1이 먼저 나가겠죠?

시간 복잡도

• 삽입 : $O(1)$
• 삭제 : $O(1)$
• 검색 : $O(n)$

구현

Queue를 어떻게 구현할 수 있을까요?

Stack을 구현했던 것과 동일하게 Array을 사용해서 구현하려고 해요.

삽입 연산은 Swift의 Array의 append 메서드를 사용할 수 있겠죠?
append는 시간 복잡도가 $O(1)$ 때문에 삽입 연산과 동일합니다.

그렇다면 삭제는 removeFirst로 가장 앞의 요소를 제거해주면 되지 않을까요?

허허.. removeFirst()는 시간복잡도가 $O(n)$이므로 삭제 연산에 적합하지 않겠네요..

그렇다면 삭제 연산을 $O(1)$로 구현할 수 있는 방법이 없을까요?

저는 요소를 가리키는 index를 하나를 두고,
삭제 연산을 할 때, 가리키고 있는 index의 요소를 반환하고 index의 값에 1을 더해주는 방식으로 구현하였습니다.

초기에는 0번을 가리키고 있겠죠?

pop을 하게되면

0번 index의 요소를 리턴해주고, 가리키고 있는 index에 1을 더해줍니다.

이러한 방식으로 구현한다면 삭제 연산을 $O(1)$로 구현할 수 있습니다.

그렇지만...
실제로는 삭제된 것이 아니고 array에 남아있기 때문에 메모리 측면에서 비효율적일 것입니다.

아직까지는 코딩테스트 문제를 풀면서 메모리와 관련되서 오답을 맞은 적이 없지만 그러한 경우를 대비해서
삭제연산을 한 10,000번 했다면 시간적 비용은 더 들겠지만 배열을 비워주는 작업을 거치거나, 유연하게 구현을 해야할 것 같아요.

이런 방식으로 삭제 연산을 구현했다면, Queue의 size는 어떻게 구할 수 있을까요?
array.count - index 로 구할 수 있겠네요!

제네릭을 사용해서 구현해주면 자료형에 의존하지 않고 범용적으로 사용할 수 있기 때문에 제네릭을 사용했습니다.
top, isEmpty, count, push, pop 정도의 메서드만 구현해보았습니다.

후기

Stack보다 구현하는 것이 약간 까다로웠습니다.
원칙적으로는 연결리스트를 구현하여 Queue를 구현하는게 더 맞는것 같은데,
코딩테스트시에는 시간이 부족할 것 같아서 약간 편법을 써서 구현하였습니다..
(연결리스트로도 구현해 볼 예정!)