큐(Queue) 개념

이번에는 큐 라는 자료구조에 대해서 알아보겠습니다.

 

큐는 FIFO(First In First Out) 라는 형태를 지니고 있습니다.

 

처음 들어간 데이터가 처음으로 나온다는 뜻입니다.

 

 

큐도 예시를 들어보겠습니다.

 

1. 맛집에 줄을 서서 기다리는 경우

2. 운영체제가 프로세스의 작업 요청을 들어온 순서대로 넣고 CPU 가 처리를 하는 경우

3. 놀이기구를 줄을 서서 기다리는 경우 

등등 큐는 일상생활에서 줄을 서서 기다리는 모든 경우에 적용이 가능합니다.

 

 

• 큐의 특징

 

이전의 스택 에서는 LinkedList 를 이용해서 head 를 기점으로 단방향 연결리스트만 생각해도 가능 했었습니다.

 

하지만 큐의 경우 head 가 아닌 head로부터 가장 먼 노드부터 제거가 되기 때문에 head 하나만으로는 O(N) 의 성능으로 

 

좋지 못한 성능이 나옵니다. 

 

head 하나인 경우

 

 

그래서 노드 끝에 tail 이라는 것을 추가하고 tail 이 가리키는 노드를 제거하게끔 하여 O(1) 의 성능이 되게끔 수정합니다.

 

하지만 이마저도 처음 끝에 노드를 제거후에는 단방향 LinkedList 이기 때문에 다시 head 를 타고 마지막 노드가 무엇인지 

 

타고가야하는 O(N) 의 성능이 되버립니다.

 

 

head 및 tail 경우

 

그래서! 큐에서는 양방향 LinkedList 를 사용하게 됩니다.

 

양방향 LinkedList

 

이렇게 되면 tail 에서 노드를 제거후에 양방향이므로 이전노드를 알 수 있어서 tail 은 이전노드를 가르키게 됩니다. 

 

그러면 O(1) 의 성능을 유지할 수 있습니다.