Queue

FIFO : First in, First out

 

Operations

<Observers>

- IsEmpty

- IsFull

 

<Transformers>

- MakeEmpty

- Enqueue

- Dequeue

 

class QueType

 

Circular Queue를 만들었을 때 문제점

큐가 비어있을 때 : front == rear +1

큐가 꽉 찼을 때 : front == rear +1

라서 분간이 안된다.

 

해결 : front를 진짜 맨 앞보다 하나 앞 공간을 가리키게 한다. (reserved area)

큐가 비어있을 때 : front == rear

큐가 꽉 찼을 때 : front == rear+1 

 

Queue 오퍼레이션의 시간 복잡도