[자료구조] 4. 큐

01. 큐의 개념 및 추상 자료형

 

✅ 큐

• 일상 생활에서의 큐 
  • 택시를 타기 위해 서 있는 행렬
  • 병원의 접수대
  • 은행의 예금 인출기
  • 백화점의 계산대 위에 놓인 상품들
• 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄(First-in-First-out) → 운영체제에서 사용하는 방법
• 한쪽에서는 삽입 연산만 발생 가능하고, 다른 한쪽에서는 삭제 연산만 발생 가능한 양쪽이 모두 터진 관

📌삽입/삭제가 다른 곳에서 발생한다는 것을 프로그래밍에서는 어떻게 표현할까?

A.
데이터에 접근하는 변수를 다르게 사용
예) 큐의 front(삭제)와 rear(삽입)

( ↔ 삽입/삭제가 같은 곳에서 발생 == 데이터에 접근할 때 같은 변수를 사용)

• 한쪽에서는 삽입 연산: 서비스를 받기 위한 기다림
• 다른 한쪽에서는 삭제 연산: 서비스를 받는 중

 

 

 

 

 

🔸큐의 추상 자료형

 ▪️ 큐의 삽입(Add_q) 연산

 

 

 

 ▪️ 큐의 삭제(Delete_q) 연산

 

 

 

▪️ 빈 큐 검사(IsEmpty_q) 연산

• 데이터 삭제 전에 확인!

 

 

 

▪️ 큐의 만원 검사(IsFull_q) 연산

• 데이터 삽입 전에 확인!

 

 

 

 

 

🔸Add/Delete 연산의 실행

① Create_q(4);
② Add_q(queue, 'A');
③ Add_q(queue, 'B');
④ Add_q(queue, 'C');
⑤ Delete_q(queue);
⑥ Delete_q(queue);
⑦ Delete_q(queue);
⑧ Add_q(queue, 'D');

 

 

 

 

 

 

 

---

02. 큐의 응용

 

✅ CPU의 관리 방법

FCFS

• FCFS(First-Come First-Served) 스케줄링(FIFO 스케줄링) 기법: 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당 받도록 해주는 기법

 

• RR(Roud Robin) 스케줄링 기법: 대화형 시스템에 사용되는 스케줄링 방식

 

 

 

 

 

 

 

---

03. 배열을 이용한 큐의 구현

 

🔸큐의 구현

▪️ 큐의 생성

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

 

 

 

예제 큐의 현재 상태: 삭제는 한번도 일어나지 않고( front가 -1이기 때문), 데이터 삽입이 3번 된 상태

 

 

▪️ 큐의 삽입

• 삽입 연산이 발생하면 rear 변수만 오른쪽으로 이동하고, 삭제 연산이 발생하면 front 변수만 오른쪽으로 이동함

 

 

▪️ 큐의 삭제

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

 

 

 

 

 

 

 

---

04. 원형 큐

 

🔸큐의 만원 상태

0번째에 데이터를 넣을 수 있음에도 만원 상태가 발생

 

 

 

✅ 원형 큐

• 배열의 문제점(일반 큐의 메모리 낭비 문제점)을 해결하기 위해 제안 됨
• 파이프의 입구와 출구 부분을 연결 시킨 형태

 

 

 

원형 큐의 상태 변화

원형 큐의 삽입 연산 결

📌 추상 자료형 연산에서는 front와 rear 값이 같으면 해당 큐는 empty 상태라고 판단하는게 일반적이고 기본적
구현자 입장에서 메모리를 효율적으로 쓰기 위해 제안한 원형 큐의 경우, 해당 큐가 다 찬 건지 빈 것인지 구분이 안 되기 때문에 추가 구현이 필요

➡️ 원형 큐는 메모리 영역을 더 효율적으로 쓸 수 있지만, 만원 상태와 빈 상태를 구분해주는 프로그램 기법이 조금 더 필요함