Queue

Queue

: 선입선출의 자료구조 형태

​ 개발자들이 큐에 접근할 수 있는 방법은 front와 rear

​ rear쪽에서는 삭제, front쪽에서는 삽입 queue는 삽입과 삭제가 서로 다른 곳에서 이루어진다. (ex. 버스 줄 서기)

Queue Add_q(queue, item):: =
  if(IsFull_q(queue))
    then { print 'queueFull';}
	else { insert item in 'rear' and return queue}

Boolean IsEmpty_q(queue)::=
if (rear == front) 
then{return 'TRUE';}
else{return 'FALSE';}

참조: 지금 내가 원하는 queue에 데이터가 찼는지 안 찼느지 확인해주는 것이 IsEmpty ( delete - data가 empty이면 오류, insert - data가 full이면 오류)

QUEUE 의 응용

CPU의 관리 방법

FCFS(First-Come First-Served)

스케쥴링(FIFO Secheduling) 기법은 작업이 준비 큐에 도착한 순선대로 CPU를 할당받도록 해 주는 기법

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

-> 두 경우 다 queue의 선입선출의 방식을 사용. 전자의 경우 우선순위의 작업이 진행, 후자의 경우 우선순위 진행 후 만약 다 처리되지 못 할 경우 맨 뒷 순위로 차례 변경

queue의 생성

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

  #define QUEUE_SIZE 5
  typedef int element;
  element queue[QUEUE_SIZE];
  int front = -1;
  int rear = -1;
  

• 큐의 삽입연산

  void Add_q(int*rear, element item) {
    if (*rear == QUEUE_SIZE-1) {
      printf("Queue is full !!");
      return;
    }
    queue[++(*rear)] = item;
    return;
  }
  

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

• 큐의 삭제연산

  element Delete_q(int*front, int rear) {
    if (*front==rear) {
      printf("Queue is empty\n");
    	return;
    }
    return (queue[++(*front)]);
  }
  

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

원형 큐

본래 queue는 5개의 데이터를 넣을 수 있다면, 이미 5개가 삽입되고 5개를 삭제했을 때 그 데이터는 더 이상 사용이 불가함. (full) 이를 해결하고자 했던 문제. 재사용하자. 즉, 큐의 만원상태를 개선하고자. 일종의 회전문형태

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

문제 - 니어와 프론트값이 같아서 비었다고 생각될 수 있는데, 구현자의 입장에서는 추상의 상태에서 비었는지 차있는지 구분이 잘 안 됨.