1. 큐 란?
먼저 들어온게 먼저 나가는 선입선출(FIFO) 형태를 띄고 있다.
FIFO 순서만 지키면 큐의 역할을 수행할 수 있으나, 이때 시간복잡도와 관련해서 문제가 생길 수 있다.
대표적으로 자바스크립트 배열에서 사용할 수 있는 큐와 비슷한 기능의 shift()가 있다.
shift()는 배열 앞에서 부터 정보를 제거하는 기능을 수행하며,배열의 원소를 제거했을때 메모리에 해당 값이 0으로 대체되며, 나머지 배열 원소에 대한 재정렬이 이루어져야 하기 때문 O(n) 시간이 발생하게 된다!
가장 많은 예시로 은행 접수 대기 순번을 꼽을 수 있다.
먼저 온 사람부터 우선적으로 업무를 처리해주는것과 같은 맥락
2. 큐 핵심 용어 & 함수
front : 큐에서 가장 처음의 원소 값(혹은 위치)
rear : 큐에서 가장 뒤의 원소 값 (혹은 위치)
enqueue(x) : 요소 x를 큐의 맨 뒤에 추가
dequeue() : 큐의 맨 앞의 요소를 삭제하고 반환
peek() : 큐의 맨 앞의 요소를 삭제하지 않고 반환
isEmpty() : 큐가 비어있으면 true 아니면 false 반환
isFull() : 큐가 가득 차 있으면 true 아니면 false 반환
size() : 큐 내의 모든 요소 개수를 반환
display() : 큐 내의 모든 요소 출력
3. 활용할 수 있는 곳
대부분의 서비스
피보나치 수열 , 우선순위 구하기 , BFS
4. 시간복잡도
(시간 복잡도는 데이터의 개수가 증가함에 따라 알고리즘 규모가 얼마나 커지는지 알려준다.)
삽입 O(1)
삭제 O(1)
탐색 O(n)
참고자료
기록하는 개발자가 되자!