Queue

 

큐의 정의

FIFO : Fisrt in First Out 즉, 먼저 들어온 애가 먼저 나간다

---

큐의 기본연산

enqueue : 큐에 넣는다

dequeue : 큐에서 뺀다

---

큐의 ADT

1. Init 

2. Queue is Empty

3. Queue에 Push

4. Queue에서 Pop

---

큐의 구현

큐는 1. 배열 2. 연결리스트 형태로 구현할 수 있다.

---

배열기반 큐

1. 일반 배열 형태의 큐

큐에 A,B,C라는 원소가 들어있다고 하자. 이 때 Pop을 한 번 하면 큐의 Head가 앞으로 이동하는데,

Head가 이동한 공간만큼은 메모리를 못쓰게 되므로 비효율적이다.

2. 원형큐

앞서 언급한 메모리 문제를 해결하기 위해 원형큐를 사용한다.

하지만 이 때도 문제가 발생하는데, Queue가 꽉 찼을 때와 , Queue가 비었을 때의 Head 와 Tail의 위치가 동일하여, 두 상태에서 Head 와 Tail의 관계가 동일하게 유지된다.

 이러한 문제를 해결하기 위해, 원형 큐를 구현할 때, 큐에서 적어도 한 개의 빈 공간이 유지되도록 하여, 큐가 비었을 때와 큐가 꽉 찼을 때의 상태를 다르게 Head와 Tail의 위치로 구분할 수 있다.

---

Deque

Double Ended Queue의 줄임말로서, 

앞 혹은 뒤에서 모두 Push와 Pop 연산이 가능한 자료구조이다.