[About 자료구조] 4.Queue(큐)

1. 큐란 무엇인가?

큐(Queue)란 가장 먼저 들어온 원소가 가장 먼저 나가는 FIFO(First In, First Out)원칙을 지키는 원소들의 집합이다.
Queue의 맨 앞을 Front , 맨 뒤를 Rear 이라고 한다.

2. 큐의 기본연산

1. Enqueue(e): e라는 원소를 Queue에 넣는다.
2. Dequeue(): Queue가 비어있지 않다면 Front에 위치한 원소를 제거 후 Return 한다.
3. isEmpty(): Queue가 비어있는지 확인하여 비어있다면 True, 아니라면 False 를 반환한다.
4. peek(): Queue의 맨 앞 원소를 보여주지만 Queue에서 삭제하지 않는다.

3. 큐의 종류

1. 선형 큐
   Array를 이용하여 만든 큐이다.
   단점은 Array를 이용하다보니 크기에 제한이 있고, Dequeue를 통해 Front에서 원소를 제거하다보면 제거한 공간을 사용하지 못하게 되어 자원 낭비가 된다

2. 원형 큐
   선형 큐의 단점을 보완한 큐이다.
   front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결 하는 방식이다.

3. Linked List를 이용한 큐
   Array를 통한 선형 큐보다는 큐보다는 크기에 제한이 없지만, 각 element마다 다음 원소의 주소값을 포함해야 하기때문에 메모리를 많이 써야 한다.