큐 (Queue)

큐 (Queue)

• FIFO(First In First Out) 을 기준으로 만들어진 자료구조다. ( 먼저 들어온 데이터가 먼저 나간다 )
• 데이터의 삽입하는 부분은 rear 삭제하는 부분을 fornt 라 부른다.
• 큐의 종류는 선형 큐(Linear Queue), 원형 큐(Circular Queue) 등이 있다.
• 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있다.
• 큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로 많이 사용한다.
• 자바스크립트에서 push, shift로 구현이 가능하나 shift의 시간 복잡도는 최대 O(n)이니 주의하자.

const arr = [];

//enqueue

arr.push('test1');
arr.push('test2');
arr.push('test3');

console.log(arr) // ['test1','test2','test3']

//dequeue

arr.shift();

console.log(arr) ['test2','test3']

 

선형 큐 (Linear Queue)

• 가장 기본이 되는 큐의 형태다.
• 막대 모양의 큐로 크기가 제한되어 있고 빈 공간을 사용하려면 자료를 모두 꺼내거나 자료를 한칸 씩 옮겨야 한다.
• 이런 선형큐에는 문제가 있는데 enqueue 와 dequeue 를 반복하다 보면 rear가 max-size에 도달하면 데이터를 더 추가할 수 없다. (가능은 하나 비효율적) 그런 점의 대안으로 나온 것이 원형 큐 이다.

 

원형 큐 (Circular Queue)

• 선형 큐의 단점의 대안으로 나온것이 원형 큐이다.
• front 와 rear 가 같은 위치에서 시작한다.
• 원형 큐는 데이터를 가져오는 방향이 없는 구조이다. 대신 큐의 크기가 지정되어 있어야 하고 front와 rear의 위치를 계산해 하나의 빈공간을 남겨야 한다. ( size가 6이면 실제 사용할 수 있는 공간은 5다. )
• enqueue는 rear = (rear + 1 ) % size 이다. 큐 size의 나머지를 연산함으로 계속 돌아갈 수 있도록 한다.
• dequeue는 front = (front + 1 ) % size 이다. 큐 size의 나머지를 연산함으로 계속 돌아갈 수 있도록 한다.
• 큐와 스택은 자바스크립트의 동작원리와 관계가 있는데 스택까지 공부하고 자바스크립트의 동작을 따로 정리할 예정이다.