[기술 면접] 4. Queue는 어떤 자료구조인가요?

저번 시간에 이어, 이번엔 Queue라는 자료구조에 대해 알아보겠습니다. Queue가 무엇인지와 그에 대한 특성, 그리고 다른 자료구조와의 비교까지 설명할 수 있어야 합니다.

Q: Queue는 어떤 자료구조인가요?

선입선출 FIFO(First In First Out)의 자료구조입니다. 시간복잡도는 enqueue, dequeue 모두 O(1)이며 활용 예시로는 Cache, 프로세스 관리, 너비우선탐색(BFS) 등이 있습니다.

• Array-Based Queue : enqueue와 dequeue과정에서 남는 메모리가 발생하는 이유로, 낭비를 줄이기 위해 Circular queue 형식으로 구현합니다.
• List-Based Queue: 재 할당이나 메모리 낭비 걱정을 할 필요가 없습니다.
• Deque(Double Ended Queue) : 양 방향으로 enqueue/dequeue가 가능합니다.
• Priority queue : 삽입 순이 아닌 우선순위로 enqueue/dequeue가 가능합니다.

Q: Queue 구현 시 Array-Base와 List-Base에 어떤 차이가 있나요?

Array-Base는 메모리 낭비를 줄이기 위해 Circular queue로 구현하는 것이 일반적입니다. fixed size를 넘어간 상태에서 enqueue가 발생하면, Dynamic Array와 같은 방법으로 Array size를 확장시켜야 하지만, 시간복잡도는 amortized O(1)을 유지할 수 있습니다.

List-Base는 보통 singly-linked list로 구현합니다. enqueue는 단순히 singly-linked list에서 append 하는 것으로 구현되며 dequeue는 맨 앞의 원소를 제거하고 first head를 변경하면 되기 문에 모두 O(1)로 가능합니다.

두 방법 모두 O(1)의 시간복잡도를 갖습니다. Array-Base의 경우 전반적으로 performance가 더 좋지만, worst case의 경우 resize로 인해 더욱 느릴 수 있습니다. List-Base는 enqueue 발생 시 마다 meomory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있습니다.

Q: Queue와 Priority Queue를 비교하여 설명해 주세요.

Queue는 FIFO구조이며 Priority Queue는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나옵니다. Queue의 시간복잡도는 enqueue/dequeue 모두 O(1)이며, Priority queue는 Heap 자료구조로 O(log n)입니다.

Q: Heap이 어떤 자료구조인지 설명해 주실래요?

Heap은 그 자체로 우선순위큐 구현과 일치합니다. 완전이진트리 구조로 Max Heap과 Min Heap으로 구분됩니다. Max힙을 예로 들자면, 각 child node의 값은 parent node보다 작아야 하며 root node에 저장된 값이 가장 큰 값이 됩니다.

Q: Heap의 삭제 과정을 설명해주세요.

우선, 루트 노드를 삭제하고, 마지막 노드를 루트 노드 자리로 이동합니다. 그리고 자식 노드와 비교하며 Swap과정을 거칩니다.

Q: 우선 순위 큐를 배열이나 연결리스트로 구현하지 않는 이유가무엇인가요?

배열이나 연결 리스트가 삭제 시에는 시간 복잡도의 우위를 점할지라도, 삽입의 시간 복잡도는 힙이 월등하기 때문에, 편차가 심한 배열과 연결리스트보다는 힙으로 구현합니다.

마치며

이번 시간엔 Queue에 대해서 알아보았습니다. 다양항 특성과 실제 사용되는 상황, 그리고 다른 자료구조와의 비교방법가지 알아보았습니다. 기초적인 개념이지만, 응용되는 곳이 많기 때문에 면접 질문으로 자주 등장합니다.
다음 시간엔 Stack 자료구조에 대해 알아보겠습니다.