[자료구조] 큐(Queue)

큐(Queue)

• 한쪽에서는 삽입연산만 발생 가능하고, 다른 한쪽에서는 삭제연산만 발생 가능한 양쪽이 모두 터진 관
• 한쪽에서는 삽입연산: 서비스를 받기 위한 기다림
• 다른 한쪽에서는 삭제연산: 서비스를 받는 중
• 선입선출(First-In-First-Out, FIFO), 선착 순 서브(First-Come-First-Serve, FCFS)알고리즘과 함께 사용됨
  반면에 스택은 후입선출/선입후출

rear에서 삽입: rear의 위치를 증가시킨 후 원소를 삽입
front에서 삭제

연산

큐의 응용

• CPU 관리 방법에서의 큐

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

큐의 삽입/삭제 연산

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

• 큐의 삽입 연산

void Add_q(element item) {
	if (rear == QUEUE_SIZE-1) { //큐가 가득찬 경우
    	printf("Queue is full");
        return; }
    queue[++rear] = item;
    return;
}
// queue(++rear) → rear에 1 증가시킨 후, 해당 위치에 새로운 원소 삽입

• 큐의 삭제 연산

element Delete_q() {
	if (front ==rear) { // 큐가 비어있는 경우 
    	printf("Queue is empty")
       	return; }
    return(queue[++(front)]);
    // front 값을 1증가 시키고, 해당 위치의 원소 반환
}

원형큐(Circular Queue)

rear가 QueueSize -1 과 같으면 full 만원이다.
그러나 만원 상태에서 다음과 같은 케이스는 어떻게 할 것인가?
: 배열로 구현한 큐의 경우 큐의 원소의 개수가 n-1이 아니더라도 큐가 full이 될 수 있음

• 원형 큐의 초기 상태
  - 배열로 구현한 큐의 문제점을 해결하기 위해 원형 큐가 제안됨
  - 원형 큐는 파이프의 입구와 출구 부분을 연결시킨 형태
  
  

mod 연산자를 사용

• rear = (rear + 1) % MAX_SIZE: 새로운 원소를 추가할 때 rear을 다음 위치로 이동. 만약 rear이 MAX_SIZE - 1에 도달하면, 다음 위치는 0
• front = (front + 1) % MAX_SIZE: 원소를 제거할 때 front를 다음 위치로 이동. 만약 front가 MAX_SIZE - 1에 도달하면, 다음 위치는 0