[자료구조] - 큐

큐 : First-In Fisrt-Out : 처음 들어온 데이타가 처음으로 나간다.

큐에서 삽입이 일어나는 곳 : 후단(rear)
큐에서 삭제가 일어나는 곳 : 전단(front)

큐 추상 자료형

	- 객체: 0개 이상의 요소들로 구성된 선형 리스트
	- 연산: 
			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) ) queue_full 오류;
              	else q의 끝에 e를 추가한다.
            dequeue(q) ->
            	if( (is_empty(q) ) queue_empty 오류;
              	else q의 맨 앞에 있는 e를 제거하여 반환한다.
            peek(q) ->
            	if(is_empty(q) ) queue_empty 오류;
           		else q의 맨 앞(front)에 있는 e를 읽어서 반환한다.
  

선형큐

front와 rear의 초기값은 -1이다. 데이터가 증가되면 rear를 하나 증가하고 그 위치에 데이터가 저장된다. 삭제할때는 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다.

선형큐 구현

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

typedef int element
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)//큐에 data가 없을때
       		printf(" | ");
        else 	// 큐에 data가 있을때
       		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)
{
	if( is_full(q)){
		error("큐가 포화상태입니다.");
        return;
   }
   q->data[++(q->rear)] = item;
}

// 큐 출력 함수
void dequeue(QueueType *q)
{
	if( is_empty(q)){
  	 	error("큐가 공백상태입니다.");
     	return;
   }
   int item =  q->data[++(q->front)];
   return item;
}

int main(void){

	int item = 0;
   	QueueType q;
   
   init_queue(&q);
   
   enqueue(&q, 10); queue_print(&q);
   enqueue(&q, 20); queue_print(&q);
   enqueue(&q, 30); queue_print(&q);
   
   item = dequeue(&q); queue_print(&q);
   item = dequeue(&q); queue_print(&q);
   item = dequeue(&q); queue_print(&q);
   
   return 0;
}

선형큐는 이해하기 쉽지만 문제점이 잇다. front와 rear의 값이 게속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 빈 공간을 사용하지 못한다는 점이다. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야한다. 그러나 모든 데이터를 주기적으로 왼쪽으로 이동시키는것은 비효율적이며 구현하기 힘들다. 따라서 원형큐를 한번 알아보자.

원형큐

이 문제는 배열을 선형에서 원형으로 생각하면 된다.
front와 rear의 값이 배열의 끝인 MAX_QUEUE_SIZE-1에 도달하면 다음에 증가되는 값은 0이 되도록한다. 즉 배열이 원형으로 처음과 끝이 연결되는 것이다(인덱스로).

ex) 큐의 크기 : 5
0->1->2->3->4->0.... 이런식으로 변화
front = (front+1) % MAX_QUEUE_SIZE;로 구현
rear = (reart+1) % MAX_QUEUE_SIZE;로 구현

front : 초기값은 0, 항상 큐의 첫 번째 요소의 하나 앞을 가리킴.
rear : 초기값은 0, 항상 큐의 마지막 요소를 가리킴.

front == rear 이면 공백 상태
(rear+1) % MAX_QUEUE_SIZE == front 이면 포화 상태

원형큐의 구현

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

typedef int element
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;
    q->front = 0;
 }
 
 //큐 상태 출력 함수
 void queue_print(QueueType *q)
 {
 printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
 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)
 {
	return(q->rear ==  q->front);
 }
 
 // 큐 공백 확인 함수
 int is_empty(QueueType *q)
 {
	if((q->rear+1) % MAX_QUEUE_SIZE == q->front)
    	return 1;
    else
    	return 0;
}

// 큐 삽입 함수
void enqueue(QueueType *q, int item)
{
	if( is_full(q)){
		error("큐가 포화상태입니다.");
        return;
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE; // 01234012....
    q->data[(q->rear)] = item;
}

// 큐 삭제 함수
void dequeue(QueueType *q)
{
	if( is_empty(q)){
    	error("큐가 공백상태입니다.");
      	return;
    }
   q->front = (q->front+1) % MAX_QUEUE_SIZE;
   return q->data[q->front];
}

element peek(QueueType *q){
	if(is_empty(&q))
    	error("큐가 공백상태입니다.");
    return q->data[(q->front+1) % MAX_QUEUE_SIZE];
}


int main(void){

    QueueType q;
    int element;
    
    init_queue(&q);
    
    printf("--데이터 추가 단계--\n");
    while(!is_full(&queue))
    {
		printf("정수를 입력하시오: ");
        scanf("%d", &element);
        enqueue(&queue, element);
        queue_print(&queue);
    }
    printf("큐는 포화상태입니다.\n\n);
    
    printf("--데이터 삭제 단계--\n");
    while(!is_empty(&queue))
    {
		element = dequeue(&queue);
        printf("꺼내진 정수: %d \n", element);
        queue_print(&queue);
    }
    printf("큐는 공백상태입니다.\n);
    
    return 0;
}

원형큐, 선형큐는 front에서 삭제 rear에서 삽입이다. 그렇다면 front에서 삽입,삭제 rear에서도 삽입, 삭제가 가능한 자료구조를 살펴보자.

덱: 큐의 전단(front)와 후단(rear)에서 모두 삽입, 삭제가 가능한 큐

덱의 추상형 자료형

원형큐에 추가된 함수만 적겠다.

	add_front(dq, e) -> 덱의 앞에 요소를 추가한다.
    add_rear(dq, e) -> 덱의 뒤에 요소를 추가한다.
    delete_front(dq) -> 덱의 앞에 있는 요소를 반환한 다음 삭제한다.
    delege_rear(dq) -> 덱의 뒤에 있는 요소를 반환한 다음 삭제한다.
    get_front(dq) -> 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.
    get_rear(dq) -> 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.
    

add_rear는 enqueue와 같고, delete_front는 dequeue와 같고, get_front는 peek과 같다. 결국 add_front, delete_rear, get_rear함수만 추가해주면 된다.

덱의 구현

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

typedef int element
typedef struct {
	int front;
    int rear;
    element data[MAX_QUEUE_SIZE];
 } DequeType;
 
 //오류 함수
 void error(char *message)
 {
	fprintf(stderr, "%s\n", message);
    exit(1);
 }
 
 //큐 초기화 함수
 void init_queue(DequeType *q)
 {
 	q->rear = 0;
    q->front = 0;
 }
 
 //큐 상태 출력 함수
 void queue_print(DequeType *q)
 {
 printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
 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(DequeType *q)
 {
	return(q->rear ==  q->front);
 }
 
 // 큐 공백 확인 함수
 int is_empty(DequeType *q)
 {
	if((q->rear+1) % MAX_QUEUE_SIZE == q->front)
    	return 1;
    else
    	return 0;
}

// 큐 후단 삽입 함수
void add_rear(DequeType *q, int item)
{
	if( is_full(q)){
		error("큐가 포화상태입니다.");
        return;
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE; // 01234012....
    q->data[(q->rear)] = item;
}

// 큐 전단 삭제 함수
void delete_front(DequeType *q)
{
	if( is_empty(q)){
    	error("큐가 공백상태입니다.");
      	return;
    }
   q->front = (q->front+1) % MAX_QUEUE_SIZE;
   return q->data[q->front];
}

// 큐 front 데이터 출력 함수
element get_front(DequeType * q)
{
	if(is_empty(q))
    	error("큐가 공백상태입니다.");
    return q->data[(q->front+1)] % MAX_QUEUE_SIZE];
}

// 큐 전단 삽입
void add_front(DequeType *q, element val)
{
	int (is_full(q))
    	error("큐가 포화상태입니다.");
   	q->data[(q->front)] = val;//원형큐의 반시계 방향으로 삽입
    q->front = (q->front -1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

// 큐 후단 삭제
element delete_rear(DequeType *q)
{
	int prev = q->rear;
    if(is_empty(q))
    	error("큐기 공백상태입니다.");
    q->rear = (q->rear -1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q->data[prev];
}

// 큐 rear 데이타 출력 함수
element get_rear(DequeTYpe *q)
{
	if(is_empty(&q))
    	error("큐가 공백상태입니다.");
    return q->data[q->rear];
}

int main(void)
{
	DequeType queue;
    init_deque(&queue);
    for(int i = 0; i < 3; i++) {
    	add_front(&queue, i);
        deque_print(&queue);
    }
    for(int i = 0; i < 3; i++) {
    	delete_rear(&queue);
        deque_print(&queue);
     }
     return 0;
}