✨Queue

선입선출 FIFO(First-in, Fisrt-out)의 자료구조이다. 시간복잡도는 enqueue(넣기) O(1), dequeue(빼기) O(1)이다.
활용 예시로근 Cache 구현, 프로세스 관리, 너비우선탐색(BFS)등이 있다.

✅ 기본 용어

• FIFO : Queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO 형식으로 데이터를 저장하는 자료구조

• Enqueue : 큐에서 데이터를 추가하는 것, 데이터를 큐의 맨 뒤에 추가하면 완료되기 때문에 시간복잡도는 O(1)

• Dequeue : 큐에서 데이터를 추출하는 것, 데이터를 큐의 맨 앞에서 추출하면 완료되기 때문에 시간복잡도는 O(1)

✅ 구현 방식

• Array-Based Queue : Array-list를 기반으로 만들어짐. enqueue와 dequeue 과정에서 남는 메모리가 생긴다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue형식으로 구현을 한다.

• List-Based Queue : Linked-list를 기반으로 만들어짐. 재할당이나 메모리의 낭비의 걱정을 할 필요가 없어진다.

❓Array-based queue와 list-based queue의 차이

: Array-based의 경우 circular queue로 구현하는 것이 일반적

• 메모리를 효율적으로 사용하기 위함
• enqueue가 계속 발생하면 fixed-size를 넘어서게 되기 때문에 dynamic array와 같은 방법으로 Array size를 resize함
• 그럼에도 enqueue의 시간복잡도는 O(1)을 유지

: List-based의 경우 singly-linked list로 구현하는 것이 일반적

• enqueue는 단순히 singly-linked list에서 append를 하는 것으로 구현
• 시간 복잡도는 O(1)
• dequeue는 맨 앞의 원소를 삭제하고 first head를 변경하면 되기 때문에 이 연산도 O(1)

: 결론

• 두 가지 종류의 자료구조 모두 O(1)의 시간 복잡도를 갖음
• Array-based의 경우 전반적으로 performance가 더 좋지만 worst case의 경우 훨씬 더 느림 (resize를 해야하기 때문)
• list-based의 경우 enqueue를 할 때마다 memory allocation을 해야하기 때문에 전반적인 runtime이 느릴 수 있음

❓Circular Queue

• Array-Based Queue는 enqueue와 dequeue를 하면 들어오고 나오는 과정에서 메모리에 빈 공간이 발생함.

• 빈 공간에 원형처럼 순환하여 enqueue를 진행

✅ 확장 & 활용

• deque(double-ended queue) : 양쪽으로 enqueue와 dequeue가 가능한 자료구조

• priority queue : 시간순서가 아닌 우선순위가 높은 순서로 dequeue를 할 수 있는 자료구조

• 활용 예시 : 하나의 자원을 공유하는 프린터, CPU task Scheduling, Cache 구현 등등