자료구조 큐

개념

큐의 의미

택시를 타기위해 서 있는 행렬, 병원의 접수대 등 

한쪽에서만 삽입 연산만 발생 가능하고 다른 한쪽에서는 삭제 연산만 발생 가능한 양쪽이 모두 터진 관

한쪽에서는 삽입 연산 = 서비스를 받기 위한 기다림

다른 한쪽에서는 삭제 연산 = 서비스를 받는 중

선입 선출(first-in-first-out, FIFO) 또는 선착 순 서브(first-come-first-serce, FCFS) 알고리즘과 함께 사용됨

 

추상 자료형

큐의 추상자료형

큐 객체 : 0개 이상의 원소를 갖는 유한 순서 리스트

rear = 삽입

front = 출력 후 삭제

 

응용

cpu 관리 방법 FCFS(First-Come First=Served) 스케줄링 (FIFO 스케줄링이라고도 함)

기법은 작업(프로그램)이 준비 큐에 도착한 순서대로 CPU를 할당 받고 작업이 완료 될때까지 CPU를 사용하는 기법

 

RR(Round Robin) 스케줄링 기법은 대화형 시스템에 적합하며, 일정 시간 (time slice)만 CPU를 사용하는 스케줄링 방식

 

배열을 이용한 큐의 구현

 

 

원형 큐

초기상태

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

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

 

원형 큐의 삽입 연산 결과

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

 

 

1. 큐는 한쪽에서는 삽입이 발생하고 다른 한쪽에서는 삭제가 발생하도록 정의되었으며, 먼저 삽입된 원소가 먼저 삭제되므로 선입 선출(First-In-First-Out : FIFO) 또는 선착순 서브(First-Come-First-Serve : FCFS) 알고리즘을 갖는 순서 리스트라고 합니다. 교재에서는 ‘알고리즘과 함께 사용됩니다’로 되어 있습니다. 원형큐의 경우도 있어서, 순서 리스트라는 표현보다는 자료구조라는 표현이 더욱 정확하지 않을까 싶습니다.
2. 큐에서는 원소의 삭제 연산이 이루어지는 곳을 앞(front)이라 하고 삽입 연산이 이루어지는 끝을 뒤(rear)라고 합니다.
3. 큐 생성 함수(Create_q(maxQueueSize))를 호출하기만 하면 프로그래머가 지정한 크기의 새로운 큐를 생성할 수 있습니다. Create_q(maxQueueSize) 함수의 매개변수인 maxQueue는 큐가 저장할 수 있는 최대 개수의 원소(element)를 의미합니다.
4. Boolean IsFull_q(queue, maxQueueSize) 연산은 큐가 가득 찼는지를 확인합니다. 즉, 큐에 저장된 원소(element)의 개수가 maxQueueSize와 같다면, 그 큐는 가득 찼으며 큐에 자료(원소)를 더 이상 저장시킬 수 없다는 것을 의미합니다.
5. Queue Add_q(queue, item) 연산은 큐에 새로운 원소를 삽입합니다. 만일 큐가 가득 찼다(Full)면 더 이상의 원소를 큐에 삽입할 수 없으며, ‘queueFull’ 메시지를 출력합니다.
6. Boolean IsEmpty(queue) 연산은 큐 상태가 빈 상태인지를 확인합니다. 만일 큐가 빈 상태이면 ‘TRUE’ 값을 반환하고, 큐에 하나 이상의 원소라도 있다면 ‘FALSE’ 값을 반환합니다.
7. Element Delete_q(queue) 연산자는 큐가 빈 상태라면 삭제할 원소가 없으므로 ‘queueEmpty’를 출력합니다. 하지만, 빈 상태가 아니라면 삭제할 원소가 있으므로, 큐의 front가 가리키는 원소를 삭제하고 그 원소를 반환합니다.
8. 큐의 추상 자료형에서 정의된 연산은 시스템 개발자에 따라 다르게 정의되고 구현될 수도 있고, 컴파일러 설계자에 따라 프로그래밍 언어에서 다르게 제공될 수도 있습니다.
9. 원형큐는 파이프의 입구와 출구 부분을 연결시킨 형태입니다. 연결된 부분의 데이터 공간을 연속적으로 사용하기 위해 ‘나머지 연산자’를 사용합니다.