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

※ 방송통신대학교 컴퓨터공학과의 '자료구조' 강의 내용 기반으로 작성되었음

 

 

[1] 큐의 개념

🔑 큐의 의미

• 택시를 타기 위해 서있는 행렬
• 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄
• 한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관
• 한쪽에서는 삽입연산 : 서비스를 받기 위한 기다림
• 다른 한쪽에서는 삭제연산 : 서비스를 받는 중
• 선입선출(First-In-First-Out, FIFO) 또는 선착순 서브(First-Come-First-Serve, FCFS) 알고리즘과 함께 사용됨

 

 

---

 

[2] 큐의 추상 자료형

🔑 큐의 객체 정의

• 큐 객체 : 0개 이상의 원소를 갖는 유한 순서 리스트

 

🔑 큐의 연산

• queue는 0개 이상의 원소를 갖는 큐
• item은 큐에 삽입되는 원수
• maxQueueSIze는 큐의 최대 크기를 정의하는 원소

 

🔑 큐의 삽입(Add-q) 연산

• Queue Add_q(queue, item)
  : queue가 Full 이라면 'queueFull'을 출력하고, 아니라면 큐의 rear에서 item을 삽입하고 큐를 반환한다.

 

 

🔑 큐의 삭제(Delete_q) 연산

• Element Delete-q(queue)
  : queue가 Empty라면 'queueEmpty'를 출력하고, 아니라면 큐의 front에 있는 원소를 삭제하고 반환한다

 

 

 

 

---

 

[3] 큐의 응용

🔑 CPU의 관리방법

• FCFS(First-COme First-Served) 스케줄링(또는 FIFO 스케줄링이라고도 함) 기법은 작업(프로그램)이 준비 큐에 도착하는 순서대로 CPU를 할당받고 작업이 완료될 때까지 CPU를 사용하는 기법
• RR(Round Robin) 스케줄링 기법은 대화형 시스템에 적합하며, 일정 시간(time slice)만 CPU를 사용하는 방식

 

 

---

 

[4] 배열을 이용한 큐의 구현

🔑 큐의 생성

• 변수  front와 rear의 초기값은 큐의 공백 상태를 나타내는 '-1'로 시작함

 

🔑 큐의 삽입 연산

• 삽입 연산이 발생하면 rear 변수만 오른쪽으로 이동(++)
• 삭제 연산이 발생하면 front 변수만 오른쪽으로 이동(++)

 

 

 

 

🔑 큐의 삭제 연산

• 삭제 연산의 수행 결과로 삭제된 원소를 Delete-q 연산자의 호출 프로그램에게 반환해줌

 

 

 

 

---

 

 

[5] 원형 큐 ✅

🔑 큐의 만원 상태

rear와 front가 같은 위치에 있다면 해당 queue 는 Empty 상태이다.

rear와 front가 같은 위치가 아니고, rear가 MaxQueueSize의 위치라면 queue는 만원상태이다.

그러나, rear와 front가 같은 위치가 아니고 rear가 maxQueueSize의 위치이지만 front의 위치가 -1이 아니라면? 

 

 

🔑 원형 큐의 초기 상태

배열로 구현한 큐의 문제점을 해결하기 위해 원형 큐가 제안됨

원형 큐는 파이프의 입구와 출구 부분을 연결시킨 형태

 

 

 

🔑 원형 큐의 삽입 연산 결과

• 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 '나머지 연산자'를 활용함