[데이터 구조] 15차시 큐(Queue) | ADT와 순차표현, 배열을 이용한 Queue의 구현

1. 큐의 개념과 ADT

1) Queue Concept

 

• 정의: 한쪽 끝, rear에서는 삽입(enqueue)만, 또 다른 끝, front에서는 삭제(dequeue)만 하도록 제한되어 있는 유한 순서 리스트(finite ordered list)
• 선입 선출(First In, First Out : FIFO) 리스트
  - 제일 먼저 삽입된 원소가 제일 먼저 삭제될(=서비스를 받을) 원소가 됨
• 선착순 서버(First Come, First Serve : FCFS) 시스템
  - 서비스를 받기 위한 대기행렬로 볼 수 있음

 

f 포인터: front(삭제), r 포인터:rear(삽입). 큐의 공백상태에서는 f와 r이 -1이다.

• Queue의 응용 사례
  - 운영 체제: 작업 큐를 통한 제출 순서에 따른 작업 스케줄(job schedule)
  - 서비스를 기다리는 작업들의 대기 상태를 나타내는 상황에 적합
  - 많은 알고리즘에서 Queue 개념을 사용함

 

2) Queue 추상 데이터 타입

dequeue()와 delete() 구분 필요

 

 

 

2. 큐의 순차 표현과 구현

1) Queue의 순차 표현

(1) 1차원 배열(array)

• Queue를 표현하는 가장 간단한 방법
• 배열 q(n)을 이용한 순차 표현
  - 인덱스는 0에서부터 시작
• 순차 표현을 위한 변수
  1️⃣ n : 큐에 저장할 수 있는 최대 원소 수, 큐의 크기
  2️⃣두 인덱스 변수: front, rear
  - 초기화: front = rear = -1 (초기 공백 큐 상태)
  - Empty Queue: front = rear (운영 중 공백 큐 상태)
  - Queue Full : rear = n-1

(2) Queue의 연산자

 

(3) 순차 표현의 문제점

• rear = n-1인 경우(Full Case)
  1️⃣만원이지만, 반드시 n개의 원소가 큐에 있지는 않은 경우
  - 큐의 앞 부분 삭제로 인해, 앞 부분에 빈 공간이 있을 수 있음
  - 빈 공간을 활용하기 위해 front와 rear를 재설정(당김) 필요
  
  2️⃣ 다른 해결 방법
  - 맨 앞(front)에서 삭제가 일어날 때마다 자료 옮김
  
  3️⃣ 실제로 큐가 만원인 경우(Real Queue Full)
  - 이동이 불가능
  - 이 경우에는 배열의 크기를 물리적으로 확장해야 됨

상기 모두: 시간, 연산의 지연 문제 발생

 

(4) 원형 큐(circular queue) -> 가장 좋은 방법

• 순차 표현의 문제를 핸결하기 위해 배열 q[n]을 원형으로 운영
• 원형 큐의 구현
  - 초기화: front = rear = 0 (공백 큐, 순차 큐에서는 -1이었음)
  - 원소 삽입: rear를 먼저 하나 증가(+1)시키고, 그 위치에 원소 저장
  - Empty Queue(빈 상태의 큐): front = rear
  - Queue Full(가득찬 큐): rear를 하나 증가시켰을 때 rear = front가 되었다면, 이미 rear를 증가시키기 전 현재의 상태가 Queue Full 상태라는 것! (이때 실제로 front의 공간 하나가 공백으로 있지만, 구현의 편의를 위해 이 공간을 희생하는 것으로 한다. 즉 1개는 꼭 비워둔다 !)
  
  
• 1차원 배열을 원형으로 구현하는 방법
  - mod(modulus, 나머지 연산) 연산자 이용
  1️⃣ 삽입을 위해 먼저 rear를 증가시킬 때: rear <- (rear + 1) mod n
  : rear 값은 n-1 다음에, n이 되지 않고 다시 0으로 됨
  
  2️⃣ 삭제를 위해 front를 증가시킬 때: front <- (front + 1) mod n
  : rear와 마찬가지로, front 값은 n-1 다음에 0이 되어 원형으로 순환
  
  

 

원형 큐의 여러 상태

 

• 공백, 포화, 오류상태 비교
  - 공백(Empty) 상태: front == rear
  - 포화(Full) 상태: front % M == (rear + 1) % M
  - 공백, 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다.

 

 

원형 큐 알고리즘

 

2) 배열을 이용한 Queue의 구현

(1) Queue를 구현하기 위한 기본 함수 프로토타입