큐
- FIFO(First In First Out) : 먼저 들어온 데이터가 먼저 나가는 자료구조
- 동작
삽입(enqueue): 큐의 후단(rear)삭제(dequeue): 큐의 전단(front)
- ADT
- 객체 : 0 개 이상의 요소들로 구성된 선형 리스트
- 연산
create(max_size)::= 최대 크기가 max_size인 공백큐로 생성한다.init()::= 큐를 초기화한다.is_empty()::= 큐가 비어있는지 검사한다.is_full()::= 큐가 가득 찼는가를 검사한다.enqueue(e)::= 큐의 뒤에 요소를 추가한다dequeue()::= 큐의 앞에 있는 요소를 반환한 다음 삭제한다.peek()::= 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.
- 객체 : 0 개 이상의 요소들로 구성된 선형 리스트
- 큐의 활용
- 은행에서의 대기열
- 컴퓨터 통신에서 데이터 송수신 : 데이터 패킷들의 모델링에 이용
- 프린터와 컴퓨터 사이의 차이를 극복 : 버퍼링
선형큐
- 배열을 선형으로 사용하여 큐를 구현
- 삽입을 계속하기 위해서는 요소를 이동시켜야 함
- 문제점이 많아 사용되지 않음
원형큐
- 배열을 원형으로 사용하여 큐를 구현
- 큐의 전단과 후단을 관리하기 위한 2개의 변수 필요
front: 첫 번째 요소 하나 앞의 인덱스rear: 마지막 요소의 인덱스
- 동작 방식
- 삽입 : rear + 1
- 삭제 : front + 1
- front가 rear을 쫓아가는 형태
→ front == rear 이면 공백상태
하나의 공간을 항상 비워두는 이유
- 공백상태와 포화상태를 구별하기 위함
공백상태: front == rear포화상태: front == (rear + 1) % M- front가 한 칸 앞이면 포화상태
구현
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_QUEUE 100
//큐 데이터 구조체 선언
typedef struct{
int data[MAX_QUEUE];
int front,rear;
}Queue;
void error(const char* msg){
printf("%s\n",msg);
exit(1);
}
// 큐 초기화 함수
void init(Queue* q){
q ->front = 0;
q ->rear = 0;
//front 와 rear 초기값 0
}
//포화상태 체크
int isFull(Queue* q){
return q -> front == ((q -> rear) + 1)%MAX_QUEUE;
}
//공백상태 체크
int isEmpty(Queue* q){
return q -> front == q -> rear;
}
//큐 요소 개수 확인
int size(Queue* q){
return (((q->rear)-(q->front))+MAX_QUEUE)%MAX_QUEUE;
}
//큐 삽입
int enqueue(Queue* q,int item){
if(isFull(q)) error("큐 가득참");
// rear + 1 해주고 그 위치에 item 삽입
q -> rear = ((q -> rear) +1) % MAX_QUEUE; // 원형 큐니까 %MAX_QUEUE
q -> data[q -> rear] = item;
}
int dequeue(Queue* q){
if(isEmpty(q)) error("큐 빔");
//front는 첫번째 요소 하나 앞의 인덱스이므로 첫번째 요소를 얻으려면 +1
q -> front = ((q -> front) +1) % MAX_QUEUE;
return q->data[q->front];
}
int main(){
Queue q;
init(&q);
enqueue(&q,1);
enqueue(&q,2);
enqueue(&q,3);
printf("%d\n",dequeue(&q));
printf("%d\n",dequeue(&q));
printf("%d\n",dequeue(&q));
}
덱(deque)
- 큐의 front와 rear에서 모두 삽입과 삭제가 가능
- ADT
- 객체 : n개의 element형의 요소들의 순서 있는 모임
- 연산
create()::= 덱을 생성 → 큐와 동일init(dq)::= 덱 초기화 → 큐와 동일is_empty(dq)::= 덱이 공백상태인지 검사 → 큐와 동일is_full(dq)::= 덱이 포화상태인지 검사 → 큐와 동일add_front(dq, e)::= 덱의 앞에 요소를 추가add_rear(de, e)::= 덱의 뒤에 요소를 추가 → enqueue()delete_front(dq)::= 덱의 앞에 있는 요소를 반환한 다음 삭제 → dequeue()delete_rear(dq)::= 덱의 뒤에 있는 요소를 반환한 다음 삭제get_front(dq)::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환 → peek()get_rear(dq)::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소 반환
덱에서 추가된 연산
- 반대 방향의 회전이 필요
- front ← (front-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE
- rear ← (rear-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE
구현
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_DEQUE 100
typedef struct{
int data[MAX_DEQUE];
int front,rear;
}Deque;
void error(const char* msg){
printf("%s\n",msg);
exit(1);
}
//큐와 동일
void init(Deque* q){
q ->front = 0;
q ->rear = 0;
}
//큐와 동일
int isFull(Deque* q){
return q -> front == ((q -> rear) + 1)%MAX_DEQUE;
}
//큐와 동일
int isEmpty(Deque* q){
return q -> front == q -> rear;
}
//큐와 동일
int size(Deque* q){
return (((q->rear)-(q->front))+MAX_DEQUE)%MAX_DEQUE;
}
//front에 삽입하는 함수
int add_front(Deque* q, int item){
if(isFull(q)) error("큐 가득참");
//front는 첫번째 요소 하나 앞이기 때문에 front가 가리키는 곳에는 값이 없다.
//그러니 front가 가리키는 곳에 값을 넣어준다.
q -> data[q->front] = item;
q -> front = (((q -> front) - 1) + MAX_DEQUE) % MAX_DEQUE;
}
//큐와 동일
int add_rear(Deque* q,int item){
if(isFull(q)) error("큐 가득참");
q -> rear = ((q -> rear) +1) % MAX_DEQUE;
q -> data[q -> rear] = item;
}
//큐와 동일
int delete_front(Deque* q){
if(isEmpty(q)) error("큐 빔");
q -> front = ((q -> front) +1) % MAX_DEQUE;
return q->data[q->front];
}
//뒤에 요소를 삭제하는 함수
int delete_rear(Deque* q){
if(isEmpty(q)) error("큐 빔");
// rear 인덱스에는 값이 들어있기 때문에 해당 요소의 값을 반환한다.
int ret = q->data[q->rear];
q -> rear = (((q->rear)-1)+MAX_DEQUE)%MAX_DEQUE;
return ret;
}
int main(){
Deque q;
init(&q);
add_front(&q,1);
add_rear(&q,4);
add_rear(&q,2);
add_rear(&q,3);
add_front(&q,2);
add_front(&q,3);
printf("%d\n",delete_front(&q));
printf("%d\n",delete_rear(&q));
printf("%d\n",delete_front(&q));
printf("%d\n",delete_rear(&q));
printf("%d\n",delete_front(&q));
printf("%d\n",delete_rear(&q));
}
큐 응용 : 큐잉모델
- 고객에 대한 서비스를 수행하는 서버와 서비를 받는 고객들로 이루어짐
- 고객들이 기다리는 평균 시간 계산
구현
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_QUEUE 100
typedef struct{
int id;
int arrival_time;
int service_time;
}element;
//큐 데이터 구조체 선언
typedef struct{
element data[MAX_QUEUE];
int front,rear;
}Queue;
void error(const char* msg){
printf("%s\n",msg);
exit(1);
}
// 큐 초기화 함수
void init(Queue* q){
q ->front = 0;
q ->rear = 0;
//front 와 rear 초기값 0
}
//포화상태 체크
int isFull(Queue* q){
return q -> front == ((q -> rear) + 1)%MAX_QUEUE;
}
//공백상태 체크
int isEmpty(Queue* q){
return q -> front == q -> rear;
}
//큐 요소 개수 확인
int size(Queue* q){
return (((q->rear)-(q->front))+MAX_QUEUE)%MAX_QUEUE;
}
//큐 삽입
int enqueue(Queue* q,element item){
if(isFull(q)) error("큐 가득참");
// rear + 1 해주고 그 위치에 item 삽입
q -> rear = ((q -> rear) +1) % MAX_QUEUE; // 원형 큐니까 %MAX_QUEUE
q -> data[q -> rear] = item;
}
element dequeue(Queue* q){
if(isEmpty(q)) error("큐 빔");
//front는 첫번째 요소 하나 앞의 인덱스이므로 첫번째 요소를 얻으려면 +1
q -> front = ((q -> front) +1) % MAX_QUEUE;
return q->data[q->front];
}
int main(){
int minutes = 60;
int total_wait = 0;
int total_customers = 0;
int service_time = 0;
int service_customer;
Queue q;
init(&q);
srand(time(NULL));
for(int clock = 0; clock <= minutes; clock++){
printf("현재시각 : %d\n",clock);
if((rand()%10) < 3){
element customer;
customer.arrival_time = clock;
customer.id = total_customers++;
customer.service_time = rand()%3 + 1;
enqueue(&q,customer);
}
if(service_time > 0){
printf("고객 %d의 업무 처리중\n",service_customer);
service_time--;
}
else{
if(!isEmpty(&q)){
element customer = dequeue(&q);
service_customer = customer.id;
service_time = customer.service_time;
printf("고객 %d의 서비스 %d분에 시작, 대기 시간 %d분\n",service_customer,clock,clock-customer.arrival_time);
total_wait += clock-customer.arrival_time;
}
}
}
printf("전체 대기시간 %d\n",total_wait);
}직접 실행해 보길 바람