큐잉 이론(Queueing Theory)
- 서버의 수 : 2대
- 각 서버의 수행 시간 : 1분
- 객체의 유입량 : 30명 / 1시간
* 평균 고객 수, 기다리는 고객 수 예상
1. 추상 큐(Abstract Queue)
1) 구성 및 삽입과 삭제 방법
▪ 선형 정렬을 이용
▪ 삽입과 삭제가 개별적으로 실행
▪ 삽입(Push Into)에 어떤 객체든 제한이 없으며, 그 객체는 큐의 Back
▪ 큐의 처음 객체는 Front
▪ 삭제(Pop From)는 큐의 현재 Front에서 실행
2) 선입 선출(Firtst-In-First-Out, FIFO) 자료구조
3) 4가지 연산
* 2가지 예외 상황
▪ 빈 큐에서 삭제(Pop) 연산 혹은 첫 객체(Front) 참조 시 정의되지 않음
2. 응용 분야
1) 손님-제공자 모델
▪ 둘 이상의 손님이 하나 혹은 그 이상의 서비스를 요구
▪ 제공자가 바쁠 때 몇 몇 손님은 기다려야 함
▪ 이러한 손님은 큐에서 대기하고 도착 순서에 따라 서비스를 차례로 제공 받음
ex) 웹 서버에서 자료를 내려 받을 때 요구가 즉시 시행되지 않은 파일들은?
3. 구현 방법
1) 2가지 구현 방법
▪ 단일 연결 리스트
▪ 순환 배열
요구조건 : 모든 큐 연산은 O(1) 시간 복잡도를 가져야 함
2) 삽입 삭제 시 시간 복잡도
▪ 삭제는 반드시 Front에서 O(1) 시간 복잡도로 시행
▪ 삭제는 반드시 Front에서 O(1) 시간 복잡도로 시행
▪ 추상 큐의 바람직한 동작은 큐의 Back에서 삽입이 시행되면서 재생성
큐의 구현
1. 연결 리스트 큐
1) 리스트 큐 클래스
▪ 단일 연결 리스트를 사용하는 큐 클래스로서 하나의 Private 멤버 변수 List를 가짐
template <typename Type>
class Queue{
private:
Single_list<Type> list;
public: // 멤버함수들의 원형 선언
bool empty() const; // 리스트가 비어 있는지?
Type front() const; // 제일 처음 원소 반환
void push( Type const & ); //원소를 리스트에 추가(list 클래스의 push_back 멤버함수를 이용)
Type pop(); //원소를 리스트에서 삭제 & 반환 (list 클래스의 pop_front 멤버함수를 이용)
};▪ 리스트 스택과 유사하게 구현
template <typename Type>
bool Queue<Type>::empty() const {
return list.empty();
} // 리스트가 비어 있는지를 검사하여 비어 있으면 true 아니면 false를 리턴
template <typename Type>
void Queue<Type>::push( Type const &obj ) {
list.push_back( obj ); //원소를 리스트에 추가 (list 클래스의 push_back 멤버함수를 이용)
}template <typename Type>
Type Queue<Type>::front() const {
if ( empty() ) {
throw underflow();
} // 리스트가 비어있으면 리턴해 줄 첫 원소가 없으므로 underflow 에러로 예외 처리
return list.front();
}template <typename Type>
Type Queue<Type>::pop() {
if ( empty() ) {
throw underflow();
} // 리스트가 비어있으면 삭제 반환할 원소가 없으므로 underflow 에러로 예외 처리
return list.pop_front();
} // 원소를 리스트에서 삭제 & 반환 (list 클래스의pop_front 멤버함수를 이용)2. 배열 큐(Array Queue)
1) 시간 복잡도
▪ 단출입구 배열로는 모든 연산이 O(1) 시간 복잡도를 만족하지 못함
▪ 양출입구 배열로 O(1) 시간 복잡도를 만족함
* 배열을 저장
▪ C++에서 큐 배열의 처음 주소를 저장
ex) Type *array;
* 추가적 정보
▪ 큐 내 객체의 수, Front, Back의 위치(Index)
ex) int queue_size;
int ifront; // index of the front entry
int iback; // index of the back entry
int array_capacity;
2) 배열 큐 클래스
template <typename Type>
class Queue{
private:
int queue_size;
int ifront;
int iback;
int array_capacity;
Type *array;
public:
Queue( int = 10 );
~Queue();
bool empty() const;
Type front() const;
void push( Type const & );
Type pop();
};3. 순환 큐 (Circular Queue)
1) 필요성
▪ 배열 크기가 16, 16 Push와 5 Pop을 시행했을 때 큐 크기는 11로 줄어듦
▪ 이러한 경우 더 이상의 객체를 배열 큐에 삽입할 수 없음
(아래의 순환적 배열 구조로 해결)
2) 구성
▪ 순환적 배열 구조
큐의 응용
1. 너비 우선 트리 탐색
1) 정의
▪ 가로 방향 즉 너비를 우선하여 트리 구조를 탐색
2) 탐색 방법
▪ 가로 방향 즉 너비를 우선하여 트리 구조를 탐색
▪ 루트 노드를 큐에 저장
▪ 큐에 객체가 존재하는 동안 아래 연산을 반복
(1) Front에서 삭제(Pop)
(2) 모든 아래 노드를 큐에 삽입
2. STL(Standard Template Library)
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue <int> iqueue;
iqueue.push( 13 );
iqueue.push( 42 );
cout << "Head: " << iqueue.front() << endl;
iqueue.pop(); // no return value
cout << "Head: " << iqueue.front() << endl;
cout << "Size: " << iqueue.size() << endl;
return 0;
}▪ STL (Standard Template Library) 중 queue 라이브러리에 대한 테스트 코드임 (13을 큐에 넣고 그 다음 42를 큐에 넣고 Head를 출력하면 13이 출력되고, pop을 하면 헤드인 13 원소가 삭제되고 그 다음 헤드를 출력하면 42가 출력됨. 마지막에 Size를 출력하개 되면 1이 출력됨. )