Week03_Queue

1. 큐란?

 

1) 개념

- 사전적 의미 : 무엇인가를 기다리는 줄

- 자료구조에서의 의미 : 무언가를 처리하기 위해 대기 중인 자료의 줄, 대기행렬이라고도 함

2) 특성

- FIFO(First-In First-Out) : 선입선출, 가장 먼저 들어간 데이터가 가장 먼저 나옴

3) 사용 예

- 선입선출 특성이 필요한 현실 세계의 다양한 시스템들을 나타낼 때 사용

- ex) 운영체제의 프린터 스풀러 (먼저 처리한 것부터 실행)

4) 구조

- 데이터를 차례대로 저장하는 선형 자료구조

- 새로운 데이터를 맨 뒤인 리어에 추가

- 리어(rear) : 큐에서 맨 나중에 추가한 데이터

         - 맨 앞인 프런트에서 자료를 제거하여 반환

- 프런트(front) : 맨 먼저 추가한 데이터

- 인큐(enqueue) : 새로운 데이터를 추가하는 연산

         - 큐의 크기 : 저장할 수 있는 최대 데이터의 개수 → 오버플로우 방지하기 위해 동적 메모리 사용을 권장

- 디큐(dequeue) : 기존 데이터를 반환하는 연산

         - 프런트가 가리키고 있는 데이터 제거

- 피크(peek) : 가장 오래된 데이터 반환 (데이터 제거 X)

 

 

2. 추상 자료형 큐

 

이름	기능	입력	출력	설명
createQueue()	큐 생성	큐의 크기 n	큐 q	빈 큐 q 생성
deleteQueue()	큐 삭제	큐 q	N/A	큐 메모리 해제
isFull()	자료 추가 가능 여부 판단	큐 q	True/False	큐에 인큐를 수행할 수 있는지 반환, 배열 큐인 경우에만 의미 있음
isEmpty()	빈 큐인지 판단	큐 q	True/False	빈 큐인지 반환
enqueue()	인큐	큐 q	성공/실패 여부	큐의 맨 뒤에 새로운 자료 추가
dequeue()	디큐	데이터 data	데이터	큐의 맨 앞에 있는 자료 제거 후 반환
peek()	피크	큐 q	데이터	큐의 맨 앞에 있는 자료 반환 (큐에서 제거 X)

 

 

 

3. 배열 선형 큐

 

1) 개념

- 배열로 구현한 선형 큐

2) 단점

- 미리 크기를 지정해야 함

- 배열의 앞부분부터 사용할 수 없는 빈 곳이 생김 (메모리 낭비)

         → 배열 원형 큐를 사용하거나 포인터로 구현한 연결 큐를 사용할 것을 권장

3) 구조

 

 

① enqueue()

- 조건식 1 : rear == maxCount – 1 (배열 선형 큐가 가득 찬 상태)

- 조건식 2 : currentCount == maxCount

② isFull()

- 현재 노드 개수 pQueue->currentCount가 최대 노드 개수 pQueue->maxCount와 같다면 배열 선형 큐가 가득 찬 상태

- 조건식 : pQueue->rear == pQueue->maxCount - 1

③ dequeue()

- pReturn->data = pQueue->pData[pQueue->front].data

④ isEmpty()

- 멤버 변수 currentCount의 값이 0이면 현재 큐가 비어 있는 상태

⑤ peek()

- 값을 삭제하지 않는다는 점이 dequeue와 다름

 

 

4. 배열 원형 큐

 

1) 개념

- 빈 노드가 있지만 인큐 연산이 불가능한 배열 선형 큐의 단점 보완

- 조건식 1 : rear = (rear+1) % maxCount