[핵심 답변]
queue는 선입선출 FIFO(First In First Out)의 자료구조입니다. 시간복잡도는 enqueue , dequeue 입니다. 활용 예시는 Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등이있습니다.
[면접 
TIP]
TIP] 기초적인 자료구조로 면접에서 간단한 질문으로 종종 나오는 문제입니다. LIFO인 stack과 다르게 FIFO자료구조임을 잘 기억하시고 계시면 됩니다. 또한 활용 예시들과 Circular Queue 자료구조를 잘 알고 계시면 면접에서 충분한 답을 하실 수 있습니다.
FIFO
queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조입니다.
enqueue & dequeue
queue에서 데이터를 추가하는 것을 enqueue라고 합니다.
queue에서 데이터를 추출 하는 것은 dequeue라고 합니다.
enqueue의 경우 queue의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1) 입니다. 이와 비슷하게 dequeue의 경우 맨 앞의 데이터를 삭제하면 완료 되기 때문에 동일하게 O(1)의 시간복잡도를 갖습니다.
구현 방식
•
Array-Based queue: enqueue와 dequeue 과정에서 남는 메모리가 생깁니다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue형식으로 구현을 합니다.
•
List-Based: 재할당이나 메모리 낭비의 걱정을 할 필요가 없어집니다.
원형큐(circular queue)
확장 & 활용
queue의 개념에서 조금 확장한 자료구조들로는 양쪽에서 enqueue와 dequeue가 가능한 deque(double-ended queue)와 시간순서가 아닌 우선순위가 높은 순서로 dequeue할 수 있는 priority queue가 있습니다.
활용 예시로는 하나의 자원을 공유하는 프린터나, CPU task scheduling, Cache구현, 너비우선탐색(BFS) 등이있습니다.
[꼬꼬무 문답]
Q. Array-Base 와 List-Base의 경우 어떤 차이가 있나요?