Queues

Queues

FIFO : First in, First out

 

Stack은 LIFO였다면 반대로 Queues는 먼저 들어온 element가 먼저 나간다.

 

기본 Notation은 다음과 같다.

 

Enqueue : element를 Queue의 끝부분에 추가한다.

Dequeue : Queue에 있는 element들 중 가장 오래전에 추가된(가장 앞에 있는) element를 제거한다.

Front : 가장 앞에 있는 element를 반환한다.

Rear : 가장 뒤에 있는 element를 반환한다.

 

 

Array based Queue

Array를 base로하면 circular queue를 base로 한다.

그냥 단순히 Array로 Queue를 만들게 되면 element들을 추가했다 제거했다 하면서 Array의 앞부분이 비었음에도 array의 끝부분까지 element가 차게 되어 추가를 하지 못하는 상황이 발생할 수 있다.

따라서 Array의 앞부분이 남았다면 그 다음에 들어오는 element들은 Array의 앞부분에 추가를 할 수 있게 해주어야 하는데 이렇게 한 queue를 circular queue라고 한다.

 

Array based Queue

circular queue

 

Array based Stack과 마찬가지로 element를 추가할 때 Array의 공간보다 더 많은 element를 추가하게 된다면 worst case로 O(n)시간이 걸릴 수 있다.

그러나 나머지 경우는 O(1) 시간이 걸린다.

Queue by Linked List

Queue를 Linked List로 구현한 경우에는 Array based Queue와는 다르게 항상 O(1)의 시간을 자랑한다.

 

그러나 enqueue를 할 때 마다 allocation을 하므로 Array based Queue보다 느릴 수 있고, pointer를 저장하기 위한 공간이 필요하다.

 

 

 

Queue 실제 사용 사례

1. BFS algorithm에서 tree를 traversing할 때 사용이 된다.

2. scheduling을 할 때 queue가 쓰이기도 한다.(먼저 요청된 작업을 먼저 처리)

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업