지난 시간에는 스택을 오늘은 큐에 관해서 좀 더 집중해서 공부해보자
자료구조 - Queue(큐)란
스택은 입구와 출구가 같았다. 하지만 큐는 입구와 출구가 다르다.
스택을 프링글스에 비유하고 큐는 은행대기순번에 비유하곤 한다.
스택은 한쪽에서 삽입과 삭제를 한꺼번에 진행하는데, 요 부분을 top 이라고 한다
큐는 끝과 끝에서 각각 삽입과 삭제 연산을 진행한다. 삭제되는 부분을 "front" 삽입되는 부분을 "rear" 이라고 한다.
큐의 추상 자료형
객체의 정의(큐생성)과 연산자(삽입/삭제/꽉찬/텅빈)로 구성된다
// 큐 생성
Queue Create_q(maxSize) ::=
큐의 크기가 maxSize인 빈 큐를 생성하고 반환
// 꽉찬 큐 확인
Boolean IsFull_q(queue, maxSize) ::=
if(queue의 element 갯수 === maxSize){
then { 'TRUE'값을 반환 }
else { 'FALSE'값을 반환 }
}
// 빈 큐 환인
Boolean IsEmpty_q(queue) ::=
if(rear === front){
then { 'TRUE'값을 반환 }
else { 'FALSE'값을 반환 }
}
// 원소 삽입
Queue Add_q(queue, item) ::=
if(IsFull_q(queue){
then { 'queue is full' 출력 }
else { 큐의 rear 에서 item 을 삽입하고 큐를 반환 }
}
// 원소 삭제
Queue Delete_q(queue) ::=
if(IsEmpty_q(queue)){
then { 'queue is empty' 를 출력한다 }
else { 큐의 front에 있는 원소를 삭제 후 반환 }
}
배열을 이용한 큐의 연산
- 삽입
rear 값을 올려서 뒤에 한공간 더 확보한다
그리고 그 공간에 item 을 저 - 장(할 - 당)
// 선언부
#define QUEUE_SIZE 5 // 큐 사이즈는 5
typedef int element; // 엘레멘트는 숫자형
element queue[QUEUE_SIZE]; // 사이즈가 5인 큐를 생성
int front = -1; // 첫째는 -1 로 초기화
int rear = -1; // 막내는 -1 로 초기화
** front 와 rear 를 인덱스값으로 사용할 것이다
// 삽입 함수
void Add_q(int *rear, element item){ // 꼴지, 추가할 값
if(*rear == QUEUE_SIZE - 1) // 맨끝의 인덱스가 꽉 찼으면?
printf('Queue is full'); // 예외 처리하고 리턴
return;
}
queue[++(*rear)] = item; // 정상적 경우에는 ++인덱스 해주고 리턴
return;
}
- 삭제
삭제니까 맨 앞(front) 값을 지운다 (how? ++인덱스를 올려서)
삭제한 값을 리턴
element Delete_q(int *front, int rear) { // 첫째 인덱스, 꼴지 인덱스
if(*front == rear) { //
printf('queue is empty');
return;
}
return queue[++(*front)];
}
** 매개변수 int *front, int rear 왜 하나만 포인터이고, 하나는 그냥 변수 자체를 넣었을가 🤔
→ 그 차이는 함수 내부에서 변경하는 값이냐 아니냐의 차이다! AHA
→ 함수 바깥에서 선언한 변수를 함수 내부에서 값을 조작하려면 직접 그 주소에 접근해야한다 (*front 요러케)
→ 반면 rear 는 readonly 용도이기 때문에 int rear로 선언! (굳이 주소로 접근할 필요 x)
이 개념을 알면 5초 이해가 가능하다 ↓↓↓
큐의 만원 상태(full)
배열로 큐를 구현했을 때, 앞쪽이 비어도 마지막 인덱스 자리가 차있으면 full 이라고 판단한다
→ 그래서 원형 큐가 등 - 장
원형 큐
원형 큐는 쉽게 말해 1자 모양의 배열을 원형으로 구부린 모양이다
맨마지막 인덱스 다음이 첫번째 인덱스를 바라보고 있어,
뺑뺑이 돌면서 순회하다가 값이 빈 곳을 발견하면 추가한다
할당된 배열의 크기를 넘어가면 나머지 연산자(modular index) 를 통해 다음 인덱스를 확인 가능하다
int getLastIndex(int front, int size) {
return (front + size - 1) % size; // 1,2,3,4,5,1,2,3,4,5 ... 이런식으로 반복된다
}
큐의 사용처
여러 프로그램들을 실행할 때, 시스템 큐에 프로그램을 순서대로 등록하고 CPU가 할당되기를 기다린다
✅ FCFS 스케쥴링 기법 (First-Come First-Served / FIFO)
정직하게 순. 서. 대. 로. CPU 할당을 해준다 (유도리가 없다)
긴 작업이 끝날 때까지 나머지 작업들은 기다려야 한다
✅ RR 스케쥴링 기법 (Round Robin)
순서대로 할당하긴 하지만, 시간제한(타임어택)이 걸려있다
할당받은 시간 끝나면 얄짤없이 다음 타자에게 넘어간다
(대화형 시스템에 사용)
'OS & Network' 카테고리의 다른 글
자료구조 - 연결 리스트란 (1) | 2023.11.29 |
---|---|
자료구조 - Array(배열)이란 (1) | 2023.11.26 |
자료구조 - Stack이란 (3) | 2023.11.23 |
안드로이드 - ADB 로 웹뷰 디버깅하기(WIFI 연결) (1) | 2023.10.11 |
안드로이드 - 안드로이드 스튜디오 설치하기 (0) | 2023.10.10 |
댓글