study/CS
Queue와 Stack
Queue Queue는 FIFO(first in first out) 선입선출 구조의 자료구조이다. enqueue O(1), dequeue O(1)의 시간복잡도를 가지고 있다. 주로 Cache구현, 프로세스 관리, BFS 등에 활용된다. 데이터의 추가는 enqueue, 데이터의 추출은 dequeue 각각 추가는 가장 뒤에 추가하면 완료이기 때문에 O(1), 삭제의 경우 가장 앞의 데이터를 삭제하면 완료이기 때문에 O(1)의 시간복잡도를 가진다. Array-base queue size가 정해진 배열에서 queue형태로 활용하는것으로 삭제(pop)가 일어날 경우 앞쪽 부분의 메모리 공간은 비어있는 채로 남기 때문에 메모리 낭비가 발생할 수 있다. Circular queue 마찬가지의 배열 기반 queue지만 ..
