[자료구조] 큐 (Queue)

• 스택과 마찬가지로 선형자료구조인데 차이점이라면 삽입, 삭제가 서로 다른곳에서 일어난다는 점이다.
• First-in, First-Out 선입선출 구조이다.

• 데이터삽입은 뒤쪽에서 데이터 삭제는 앞쪽에서 일어난다.
• 데이터 삽입이 일어나는 포인터변수는 rear, 삭제가 일어나는 포인터변수는 front라고 한다.
• 큐에서는 삽입변수와 삭제변수를 각각 운영한다.

empty 상태에서는 front와 rear가 같은곳을 가리킨다.

추상자료형

ADT	기능설명
Add_q()	rear 포인터를 하나 증가시킴
Delete_q()	front 포인터를 하나 감소시키고 반환함.
IsEmpty_q()	큐가 비어있으면 true, 아니면 false
IsFull_q()	큐가 꽉찼으면 true, 아니면 false

 

rear포인터와 front포인터가 배열의 경우 같은값이거나, 같은 메모리 영역을 가리키면 큐는 queueEmpty 상태가 된다.

큐의 응용

• 중앙처리장치를 할당받기 위해 프로그램들이 대기중인 상태에서 FCFS스케줄링을 활용할 때
  - FCFS스케줄링은 선입선출 방식이므로 준비큐에 도착한 순서대로 CPU를 할당받도록 해준다.
  - 단점 : 준비큐에 늦게 들어온 수행시간이 짧은 작업이 시간이 오래걸리는 작업들을 기다리거나, 중요한 프로세스가 비교적 덜 중요한 프로세스의 완료를 기다리게 될 수 있다.
• RR (Round Robin) 스케줄링 기법
  - 대화형 시스템에 사용되는데, 도착한 순서대로 CPU를 할당받지만 CPU의 시간할당량 또는 시간간격에 의해 제한 받을 수 있다.
  - 일정 시간의 할당량을 주고 그 시간동안 완료되지 않으면 준비큐의 맨뒤에 배치하여 한 작업이 CPU를 독점하지 않는다.

배열을 이용한 큐의 추상자료