Queue

queue는 먼저 집어넣은 데이터가 먼저 나오는 First In First Out 구조로 되어있다.

나중에 집어넣은 데이터가 먼저 나오는 stack과 반대되는 개념이다.

queue는 놀이공원에서 서는 줄과 같이 작동한다.

사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는 것과 같다.

 

 

 

queue의 메서드에는 enqueue, dequeue, size 가있다.

enqueue는 queue에 맨 뒤에 요소를 추가해주고

dequeue은 queue의 맨 앞의 요소를 꺼내고 이를 반환해준다.(return값이 있다.)

size는 queue의 데이터 개수를 반환해준다.

let queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue();   // 1
queue.size(); // 1

 

시간 복잡도

queue에서 추가하기와 삭제하기의 경우의 시간 복잡도는 O(1)이다.

queue의 가장 위에서 추가하고 가장 아래에서 삭제하기 때문에 일일이 찾아낼 필요가 없다.

하지만 가져오기의 경우 stack과 마찬가지로 

마지막부터 처음까지 다 탐색해야 하는 경우가 있기 때문에 시간 복잡도는 O(n)이 된다.