[CS 노트] : Queue에 대해서..

Queue가 무엇인가?

큐는 FIFO(선입선출)의 자료구조이다. 시간복잡도는 enqueue(데이터 넣기), dequeue(데이터 빼기) 둘 다 O(1)이다.(맨 뒤에서 데이터를 넣고, 맨 앞에서 데이터를 빼기 때문이다.) 보통 Cache 구현이나 프로세스 관리, 너비우선탐색(BFS) 등이 있다.

 

구현 방식은 Array Based queue와 List Based가 있다.

 

Array Based queue는 메모리를 넣고 빼다 보면 메모리 낭비가 발생하게 되고 이것을 방지하기 위해 Circular queue 형식으로 구현하게 된다. FIFO가 맨 뒤에서 넣고 맨 앞에서 빼내게 되는데 앞 칸에서 데이터를 빼내고 난 뒤에 당겨지지 않아 앞에 빈 메모리 공간이 생기게 된다. 이게 많아지면 결국 메모리 낭비가 되는데 Circular queue는 할당된 메모리 공간이 모두 차게 되고 배열 앞이 dequeue로 비어진 상황이라면 resize를 하지 않고 앞에서부터 숫자를 채워나간다. 그렇게 Circular queue마저 끝나 메모리가 꽉 차고 난 뒤에 더 저장할 데이터가 생기게 된다면 그제서야 resize가 일어나게 된다.(이 상황에도 resize가 일어나는 상황을 제외하면 O(1)의 시간 복잡도를 가지게 된다.)

 

List Based는 Linked List와 같아 재할당 및 메모리 낭비의 걱정이 필요 없다.

---

기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다.