자료구조 - Queue(큐)란

 

지난 시간에는 스택을 오늘은 큐에 관해서 좀 더 집중해서 공부해보자

 

 

---

자료구조 - 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초 이해가 가능하다 ↓↓↓

JavaScript - Call By Value, Call By Reference

 

 

큐의 만원 상태(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)

순서대로 할당하긴 하지만, 시간제한(타임어택)이 걸려있다

할당받은 시간 끝나면 얄짤없이 다음 타자에게 넘어간다

(대화형 시스템에 사용)