Queue

queue

 

"매표소의 대기열"

 

큐의 구조

 

실제 구현 방식과 햇갈릴 수 있으니 이 그림은 단순 참고만 하자

큐의 특징

 

FIFO (First-In First-Out)(선입선출)

 

큐의 용도

 

직접적인 응용

- 시뮬레이션의 대기열

- 통신에서의 데이터 패킷들의 모델링

- 프린터와 컴퓨터 사이의 버퍼링

간접적인 응용

- 프로그래머의 도구로써 많은 알고리즘에 사용

 

큐 ADT

 

create(max_size)

- 최대 크기가 max_size인 공백큐 생성

init(q)

- 큐 초기화

is_empty(q)

- if (size == 0) return TRUE;

  else return FALSE;

is_full(q)

- if (size == max_size) return TRUE;

  else return FALSE;

enqueue(q, e)

- if (is_full(q)) full로 인한 오류;

  else q의 끝에 e를 추가

dequeue(q)

- if (is_empty(q)) empty로 인한 오류;

  else q의 맨 앞에 있는 e를 제거하여 return

peek(q)

- if (is_empty(q)) empty로 인한 오류;

  else q의 맨 앞에 있는 e를 읽어서 return

 

큐 동작원리

 

create(5)

init()

enqueue(7)

enqueue(3)

enqueue(2)

dequeue()

dequeue()

dequeue()

이 그림을 외우자

// front는 항상 첫번째 요소 하나 앞의 인덱스값 갖게 된다

   -> 삽입이나 삭제 둘 다 유사한 연산과정을 가지게 하기 위해

 

// empty() - front == rear

// full() - rear == MAX_SIZE - 1

   -> 어떠한 경우에도 무조껀 rear가 마지막 index 가리키면 포화상태로 간주

 

배열을 이용한 큐 실제 구현 - 1. 선형큐

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;	// 언제든 큐 data type을 손쉽게 변경해주기 위해
typedef struct {
	int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
} QueueType;

// 오류함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
    exit(1)
}

// 큐 초기화
void init_queue(QueueType *q)
{
	q->rear = -1;
    q->front = -1;
}

// 현재 큐 현황 출력 함수
void queue_print(QueueType *q)
{
	for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
    	if (i <= q->front || i > q->rear)
        	printf("  | ");
        else
        	printf("%d | ", q->data[i]);
    }
    printf("\n");
}

// 큐 포화상태 확인
int is_full(QueueType *q) 
{
	if (q->rear == MAX_QUEUE_SIZE - 1)
    	return 1;
    else
    	return 0;
}

// 큐 공백상태 확인
int is_empty(QueueType *q)
{
	if (q->front == q->rear)
    	return 1;
    else
    	return 0;
}

// 큐 데이터 추가
void enqueue(QueueType *q, int item)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 포화상태 입니다.");
        return;
    }
    q->data[++(q->rear)] = item;
    // q->rear++;
    // q->data[q->rear] = item;
}

// 큐 데이터 삭제
void enqueue(QueueType *q)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 공백상태 입니다.");
        return -1;
    }
    
    return q->data[++(q->front)];
}

// 메인 함수 사용자 사용
int main(void)
{
	int item = 0;
    QueueType q;
    
    init_queue(&q);
	
    enqueue(&q, 10); queue_print(&q);
    //...
    dequeue(&q); queue_print(&q);
    //...
    return 0;
}

// 현재 큐 현황 출력 함수에서 빈공간 출력 원리

 

선형큐의 문제점

 

빈공간 생김

앞 부분이 비어있게 되므로 효율적으로 사용하기 위해서

모든 요소들을 왼쪽으로 옮겨야 한다

-> 선형 큐의 단점을 보완 - 원형 큐

 

배열을 이용한 큐 실제 구현 - 2. 원형큐

 

 

선형큐와 다른점

- front와 rear init -> not -1 -> 0

- 포화상태 일 때 front == (rear+1) % M -> %M이 추가

- 공백상태와 포화상태를 구별하기 위해 하나의 공간은 항상 비워두며 front는 항상 제일 앞 data의 바로 앞에 있는 빈      공간을 가리킨다.

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;	// 언제든 큐 data type을 손쉽게 변경해주기 위해
typedef struct {
	int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
} QueueType;

// 오류함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
    exit(1)
}

// 큐 초기화
void init_queue(QueueType *q)
{
	q->rear = 0;		// -1 -> 0
    q->front = 0;		// -1 -> 0
}

// 현재 큐 현황 출력 함수
void queue_print(QueueType *q)
{
	if (!is_empty(q)) {		// 돌아가는건 그림 그려서 예시들어서 하면 쉬움
    	int i = q->front;
        do {
        	i = (i + 1) % MAX_QUEUE_SIZE;
            printf("%d | ", q->data[i]);
            if (i == q->rear)
            	break;
        } while(i != q->front);
    }
    printf("\n");
}

// 큐 포화상태 확인
int is_full(QueueType *q) 
{
	if (q->front == (q->rear+1) % MAX_QUEUE_SIZE)	// 선형 큐와 다름
    	return 1;
    else
    	return 0;
}

// 큐 공백상태 확인
int is_empty(QueueType *q)
{
	if (q->front == q->rear)
    	return 1;
    else
    	return 0;
}

// 큐 데이터 추가
void enqueue(QueueType *q, int item)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 포화상태 입니다.");
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;		// 추가 방법 다름
    q->data[q->rear] = item;
}

// 큐 데이터 삭제
void enqueue(QueueType *q)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 공백상태 입니다.");
        return -1;
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;		// 삭제 방법 다름
    return q->data[q->front];
}

// 메인 함수 사용자 사용
int main(void)
{
	int item = 0;
    QueueType q;
    
    init_queue(&q);
	
    enqueue(&q, 10); queue_print(&q);
    //...
    dequeue(&q); queue_print(&q);
    //...
    return 0;
}