[자료구조] 큐(Queue)의 개념 정리와 구현

큐란?

- 먼저 들어온 데이터가 먼저 나가는 자료구조

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

 

큐 ADT

- create(max_size) : 최대 크기가 max_size인 공백큐를 생성한다.

- init(q) : 큐를 초기화한다.

- is_empty(q): 큐가 비어있으면 true를, 아니면 false를 반환한다.

- is_full(q) : 큐가 가득 차 있으면 true를, 아니면 false를 반환한다.

- enqueue(q, e) : 큐가 is_full이면 error, 아니면 q의 끝에 e를 추가한다.

- dequeue(q) : 큐가 is_empty이면 error, 아니면 q의 맨 앞에 있는 e를 제거하여 반환한다.

- peek(q) : 큐가 is_empty이면 error, 아니면 q의 맨 앞에 있는 e를 읽어서 반환한다.

 

 

선형 큐

- 배열을 선형으로 사용하여 큐를 구현

- 삽입을 계속하기 위해서는 요소들을 이동시켜야 하는 불편함이 있다.

 

원형 큐

- 큐의 전단과 후단을 관리하기 위한 2개의 변수가 필요

- front : 첫번째 요소 하나 앞의 인덱스

- rear : 마지막 요소의 인덱스

- 공백 상태 : front == rear

- 포화 상태 : front % (배열의 크기)  == (rear + 1) % (배열의 크기)

* 포화 상태와 공백상태를 구별하기 위하여 하나의 공간은 항상 비워둔다. 

 

덱 (deque)

- 덱은 doble-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐이다.

 

덱 ADT

- 객체: n개의 element형으로 구성된 요소들의 순서있는 모임

- create() : 덱을 생성한다.
- init(dq) : 덱을 초기화한다. 

- is_empty(dq) : 덱이 공백상태인지를 검사한다. 

- is_full(dq) : 덱이 포화상태인지를 검사한다.
- add_front(dq, e) : 덱의 앞에 요소를 추가한다.

- add_rear(dq,e) : 덱의뒤에요소를추가한다.

- delete_front(dq) : 덱의 앞에 있는 요소를 반환한 다음 삭제한다.

- delete_rear(dq) : 덱의 뒤에 있는 요소를 반환한 다음 삭제한다.

- get_front(q) : 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다. 
- get_rear(q) : 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.

 

배열로 구현한 선형 큐

#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)
			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)
{
	if (is_full(q)) {
		error("큐가 포화상태입니다.");
		return;
	}
	q->data[++(q->rear)] = item;
}

int dequeue(QueueType *q)
{
	if (is_empty(q)) {
		error("큐가 공백상태입니다.");
		return -1;
	}
	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;
}

 

선형 큐를 활용한 미팅 주선 프로그램

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 3 //3으로 설정
#define MAX_STRING 100 // 추가

typedef struct { //수정
     char name[MAX_STRING];
} element;

typedef struct {
    element  queue[MAX_QUEUE_SIZE];
    int  front, rear;
} QueueType;
//
void error(char *message)
{
    fprintf(stderr,"%s\n",message);
    exit(1);
}
// 초기화 함수
void init(QueueType *q)
{
    q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
    return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
    return ((q->rear+1)%MAX_QUEUE_SIZE == q->front);
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
      if( is_full(q) )
        error("큐가 포화상태입니다");
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
       if( is_empty(q) )
        error("큐가 공백상태입니다");
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}
// 보기 함수
element peek(QueueType *q)
{
       if( is_empty(q) )
        error("큐가 공백상태입니다");
    return q->queue[(q->front+1) % MAX_QUEUE_SIZE];
}

int get_count(QueueType *q)
{
    return ((q->rear - q->front) + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

void print_queue(QueueType *q) // 추가, 20141016 수정
{
    int size;
    size = get_count(q);
    
    int idx = (q->front + 1) % MAX_QUEUE_SIZE;

    for (int i = 0; i < size; i++)
    {
        printf("%s ", q->queue[idx].name);
        idx = (idx + 1) % MAX_QUEUE_SIZE;
    }
    printf("\n");
}

void try_match(char *name, QueueType *partnerQ, QueueType *myQ) //추가 부분: 더 좋은 함수 이름??
{
    element person;
    strcpy(person.name, name);
    enqueue(myQ, person);
    
    if (!is_empty(partnerQ) && !is_empty(myQ)) {
        printf("커플이 탄생했습니다! %s과 %s\n", myQ->queue[myQ->front + 1].name, partnerQ->queue[partnerQ->front].name);
        dequeue(myQ);
        dequeue(partnerQ);
    }
    else {
        printf("아직 대상자가 없습니다. 대기자가 꽉찼으니 담 기회를 이용\n");
    }
}

int main(void)
{
     QueueType manQ, womanQ;
     char choice;
     char name[MAX_STRING];
     char gender;

     init(&manQ);
     init(&womanQ);

     printf("미팅 주선 프로그램입니다.\n");
     
     printf("i(nsert, 고객입력), c(heck, 대기자 체크), q(uit):");
     scanf("%c", &choice);
 
     while (choice != 'q') {
          switch(choice) {
          case 'i':
               printf("이름을 입력:");
               scanf("%s", name);
               fflush(stdin);
               printf("성별을 입력(m or f):");
               scanf("%c", &gender);
               if (gender == 'm')
                    try_match(name, &womanQ, &manQ);
               else
                    try_match(name, &manQ, &womanQ);
               break;
          case 'c':
               printf("남성 대기자 %d명: ", get_count(&manQ));
               print_queue(&manQ);
               printf("여성 대기자 %d명: ", get_count(&womanQ));
               print_queue(&womanQ);
          }
          fflush(stdin);
          printf("i(nsert, 고객입력), c(heck, 대기자 체크), q(uit):");
          scanf("%c", &choice);
     }
}