컴퓨터과학 자료구조 큐

삽입과 삭제의 방향이 다르다.

작업 큐에 들어간 작업이 가장 먼저 처리가 된다.

큐의 의미 : 한 쪽에서는 삽입만, 다른 쪽에서는 삭제연산만 발생

선입선출, 선착순 서브(FCFS) 알고리즘을 갖는 순서 리스트

Queue Add_q (queue, item) : 큐의 rear 에서 item을 삽입하고 큐를 반환

Element Delete_q(queue) : 큐의 front 에 있는 원소를 삭제하고 반환

rear == front : 아무것도 없는 상태 (빈 큐)

FCFS 스케줄링 기법 : FIFO, 선입선출 기법

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

배열을 이용한 큐의 구현

큐의 삭제 연산

element Delete_q (int *front, int rear) {

 if (*front == rear) {

printf(*Queue is empty);

return; }

 return ( queue[++(*front)] ); 

}

원형 큐

배열의 문제점을 해결하기 위해 원형큐가 제안 됨

원형 큐는 파이프의 입구와 출구 부분을 연결시킨 상태

연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 나머지 연산을 활용

연습문제

1. 자료 구조의 유형 중 선형 구조에 해당하는 것은 무엇인가? 답 : 큐

2. 큐에서 노드를 삽입할 경우의 설명으로 맞는 것은 ? 답: 

3. (가)와 (나)에 알맞는 내용은? 

1. void Add_q(int *rear, element item) {

2. if ( (가) )

3.   {   printf(“Queue is full !!”);

4.       return;       }

5. queue[(나)] = item;

6. return;   }

답: *rear = QUEUE_SIZE-1, ++(*rear)