Queues

큐는 FIFO (first-in first-out)이다.

 

큐의 Operation

enqueue : 큐에 요소를 맨뒤에 넣는다. 성공 여부 리턴

dequeue : 큐에서 맨 앞의 요소를 꺼낸다. (큐안에서 요소가 삭제 )요소 리턴

isEmpty : 큐안에 비었는지 체크

peek : 큐 맨앞에 요소를 가져온다. (삭제되진 않는다) 

 

큐는 항상 맨 앞과 맨 뒤의 요소만 고려하면 된다. 중간의 요소에 대해서는 생각하지 않아도 된다.

 

큐를 만드는 총 4가지 방법을 알아볼 예정입니다.

1. array 사용하기

2. doubly 링크드 리스트 사용하기

3. ring buffer

4. two stacks 

 

1. array 로 사용하기

queue의 프로토콜을 계승하여 array변수값을 선언 후 en큐는 array append 하고

de큐는 array 맨앞에서 데이터를 빼고  이런식으로 array 변수를 가지고 큐를 만든다.

 

array로 이용하면서 array로 사용했을 때단점을 고스란히 queue가 가져가게 된다.

enqueue를 할때는 어레이가 가득차게 되면 크기를 조정해야 되어 다시 메모리를 재조정? 해야하는 최악의

케이스가나오고 dequeue할때는 비어있는 메모리가 생기기 떄문에 낭비가 될수있다.

 

2. doubly linked list

 

링크드리스트는 기본적으로 head와 tail를 가지고 있으므로 모두 O(1)의 시간복잡도를 가진다.

시간 복잡도는 빠르지만 각 노드에 참조를 위한 스토리지를 만들어야 하므로 공간복잡도는 높다. 

공간복잡도 측면에서는 array가 낫다.  liskedlist는 새로운 요소를 추가할때마다 노드라는 새로은

요소를 생성해야한다.

 

3. ring buffer (circular buffer)

링버퍼는 고정된 사이즈의 array이다.

링크드리스트와 똑같은 성능을 가지지만 고정된 array로 공간복잡도가 무한으로 늘어나지 못하는게

장점이나 단점이다

 

4. double Stack

큐를 두개 가지고 있고.

꺼낼 때는 하나의 큐를 reverse 해서 꺼내주고 다시 삭제 그런식으로 한다.

차이를 말하는데 서로 stack은 데이터들이 붙어있으므로 빠른 접근이 가능하고

똑같은 O(n)시간 복잡도 이지만 빠른 O(n)시간 복잡도를 갖는다고 한다.

이런 그림을 그려놓으면서..

정말 맞는지는 모르겠다.

 

 

결론:

배열의 요소는 인접한 메모리 블록에 배치되는 반면,

리스트리스트는 캐시 누락 가능성이 더 많이 흩어져 있습니다.