[바킹독의 실전 알고리즘] 0x06강 - 큐

정의와 성질

큐는 선입선출이다 먼저 들어간게 먼저 나오는 FIFO(First In First Out)

1. 원소의 추가가 O(1)
2. 원소의 제거가 O(1)
3. 제일 앞/뒤의 원소 확인이 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

원형 큐

그냥 선형배열에서 만든 큐는 삭제가 될 때마다 쓸모없는 공간이 계속 생기게 된다. 무슨말이냐면 배열이 8칸인 상태에서 push를 하게 되면 8번째 인덱스를 사용해야하는데 없기때문이다 그래서 원형 큐를 구현하게 된다
이렇게 되면 head/tail 이 7인 상태에서 다시 0번지로 오도록 할 수 있으며, 이렇게 되면 0번지부터 다시 추가하거나 삭제 할 수 있어 쓸모없는 공간이 생기는 선형 큐의 단점을 보완할 수 있다.

** JS에서는 shift,unshift 메소드를 활용해서 맨 앞 원소를 추가/제거 할수 있는데, 시간 복잡도는 O(N)이다. pop, push는 O(1) 이에 비해 성능이 떨어진다. 코테를 볼 때 제한시간에 유의하면서 사용하면 좋다

JS 알고리즘 구현: 큐(Queue) 구현 vs Array 메서드(shift, splice) 사용했을때 속도 비교