4. Queue(큐)

큐란?

- 스택과 유사하게 데이터를 일시적으로 쌓아 두기 위한 자료구조, 선입선출(FIFO)형식이다.

 

**enQueue(인큐)와 deQueue(디큐)

- enQueue : 큐에 데이터를 넣는 작업을 말한다.(rear에서 넣음) - 시간복잡도 O(1)

- deQueue : 큐에서 데이터를 꺼내는 작업을 말한다.(front에서 꺼냄) - 시간복잡도 O(n), 중간의 데이터가 수정될 경우 모든 요소를 한 칸씩 앞으로 옮기는 작업을 하게 되기 때문에 시간 복잡도가 상대적으로 높다.

 

**링 버퍼

- deQueue의 시간 복잡도를 줄이기 위해서 배열 요소를 앞쪽으로 옮기지 않고 배열의 처음이 끝과 연결되었다고 보는 자료 구조. 시간 복잡도는 O(1)이다.

 

이렇게 배열의 처음과 끝을 연결해서 데이터가 수정되어도 해당 자리에서 자리가 수정되지는 않아 시간 복잡도에서 효율적인 자료 구조이다. 인덱스 max가 10인데 데이터가 12개 들어오게 되는 경우 a[0], a[1]이 자동으로 덮어써지면서 맨 뒤 2개의 값을 받아들인다. a[2],a[3],a[4], ... a[9],a[0],a[1] 이런식으로 큐가 구성되게 된다.

 

큐 함수

IntQueue.h(헤더 파일)

1. Initialize : 큐를 구현하기 위한 배열의 메모리 공간 확보 등의 준비 작업을 하는 함수. 큐를 처음 만들면 큐는 비어 있다.

2. Enque : 큐에 데이터를 인큐하는 함수. 뒤에 추가 되므로 rear값을 ++시켜서 증가시켜 준다. 인덱스 개수도 증가한다. Enque 함수를 수행할 때 max값과 추가된 데이터의 인덱스가 같아지는 경우가 발생하는데, 이것을 방지하기 위해 마지막에 q->rear = 0으로 rear를 변경시켜 준다.

3. Deque : 큐에서 데이터를 디큐하는 함수. 앞에서 인덱스가 빠지게 되므로 front값을 ++시켜서 front 인덱스를 증가시켜준다. 인덱스 개수는 데이터가 빠지기 때문에 감소한다. 인큐와 마찬가지로 데이터 초과 문제가 발생하는데, 디큐하기 전의 front값이 배열 끝이라면 front값이 max와 같아져 배열 마지막 요소의 인덱스를 초과하게 된다. 이것을 방지하기 위해 마지막에 q->front = 0으로 front값을 배열의 처음인 0으로 변경해야 한다.

4. Peek : 맨 앞의 데이터를 몰래 엿보는 함수로 데이터값은 변하지 않고 que[front]값을 출력만함.

5. Clear : 현재 큐의 모든 데이터를 삭제하는 함수.

6. Capacity : 큐의 최대 용량을 반환하는 함수.

7. Size : 현재 큐의 데이터 개수를 반환하는 함수.

8. IsEmpty : 큐가 비어 있는지 판단하는 함수.

9. IsFull : 큐가 가득 찼는지 판단하는 함수.

10. Search : 큐의 배열에서 x와 같은 데이터가 저장되어 있는 인덱스를 반환하는 함수. 현재 검색하는 위치의 인덱스를 구하는 식은 (i + q->front) % q->max 이다.

11. Print : 큐의 모든 데이터를 처음부터 끝까지 순서대로 출력하는 함수.

12. Terminate : 메모리 공간에 할당한 배열(큐)을 해제하는 함수.

 

 

IntQueue.c(소스 파일)