큐(Queue)란?
: "대기열"
: 스택과 마찬가지로 데이터를 일시적으로 저장하기 위한 자료구조
:
큐의 출력 순서
: 선입선출(FIFO, Fisrt In First Out), 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다.
인큐(enqueue): 큐에 데이터를 넣는 작업
디큐(dequeue): 큐에 데이터를 꺼내는 작업
배열을 통한 인큐 디큐 복잡도
데이터를 꺼낼때마다 효율이 떨어진다.
링 버퍼 구조를 통한 디큐 복잡도 향상
링 버퍼 구성도
프런트(front): 맨 처음 요소의 인덱스
리어(rear): 맨 끝 요소 하나 뒤의 인덱스(= 인큐 위치)
인큐와 디큐 수행시, 프런트와 리어 값을 업데이트하면 앞서 발생한 요소 이동 문제를 해결하고 복잡도를 O(1)이 된다.
+ 오래된 데이터를 버리는 용도
