Queue(큐) - 1 [Array Queue, Linked Queue]

1. 큐 추상 데이터 타입

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

 - 삽입이 일어나는 곳을 후단(rear), 삭제가 일어나는 곳을 전단(front)이라고 한다.

 - 객체 : n개의 element 타입의 요소들의 순서 있는 모임

 - 연산 :

•  create()
•  init(q)
•  is_empty(q)
•  is_full(q)
•  enqueue(q, e) : 큐의 뒤에 요소를 추가한다.
•  dequeue(q) : 큐의 앞에 있는 요소를 반환한 다음 삭제한다.
•  peek(q) : 큐에서 삭제하지 않고 앞에 있는 요소를 반환한다.

 - 사용 예로는 은행에서 기다리는 사람들의 대기열, 공항에서 이륙하는 비행기들, 인터넷에서 전송되는 데이터 패킷들을 모델링하는 데 큐가 이용된다.

 - 운영체제에서는 인쇄 작업큐, 사용자가 키보드를 누르면 키 스트로크 데이터가 큐에 저장된다.

 

2. 배열로 구현된 큐

 1) 선형 큐(linear queue)

  - front와 rear의 초기값은 -1이다.

  - 삭제할 때는 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다.

 

 2) 원형 큐

  - 원형 큐에서는 front와 rear의 개념이 약간 변경된다. 먼저 초기값은 -1이 아닌 0이다.

  - front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타낸다.

  - 원형 큐에서는 하나의 자리는 항상 비워둔다. 왜냐하면 포화 상태와 공백 상태를 구별하기 위해서이다.

 

#include <stdio.h>

#define MAX_QUEUE_SIZE 100
typedef int 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];
}
// 주 함수
void main()
{
	QueueType q;
	init(&q);
	printf("front=%d rear=%d\n", q.front, q.rear);
	enqueue(&q, 1);
	enqueue(&q, 2);
	enqueue(&q, 3);
	printf("dequeue()=%d\n", dequeue(&q));
	printf("dequeue()=%d\n", dequeue(&q));
	printf("dequeue()=%d\n", dequeue(&q));
	printf("front=%d rear=%d\n", q.front, q.rear);
}

 

3. 연결 리스트로 구현된 큐

 - 연결 리스트로 만들어진 큐를 연결된 큐(linked queue)라고 한다.

 - 크기가 제한되지 않는다는 장점, 링크 필드 때문에 메모리 공간을 더 많이 사용한다.

typedef int element;	// 요소의 타입
typedef struct QueueNode {	// 큐의 노드의 타입 
	element item;
	struct QueueNode *link;
} QueueNode;
typedef struct {		// 큐 ADT 구현
	QueueNode *front, *rear;
} QueueType;
// 오류 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// 초기화 함수
void init(QueueType *q)
{
	q->front = q->rear = NULL;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return (q->front == NULL);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return 0;
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
	QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
	if (temp == NULL)
		error("메모리를 할당할 수 없습니다");
	else {
		temp->item = item; 		// 데이터 저장
		temp->link = NULL; 		// 링크 필드를 NULL
		if (is_empty(q)) { 		// 큐가 공백이면
			q->front = temp;
			q->rear = temp;
		}
		else { 		// 큐가 공백이 아니면
			q->rear->link = temp;  // 순서가 중요
			q->rear = temp;
		}
	}
}
// 삭제 함수
element dequeue(QueueType *q)
{
	QueueNode *temp = q->front;
	element item;
	if (is_empty(q))			// 공백상태
		error("큐가 비어있습니다");
	else {
		item = temp->item; 		// 데이터를 꺼낸다.
		q->front = q->front->link; // front를 다음노드를 가리키도록 한다.
		if (q->front == NULL) 	// 공백 상태
			q->rear = NULL;
		free(temp); 			// 동적메모리 해제
		return item; 			// 데이터 반환
	}
}
// peek 함수
element peek(QueueType *q)
{
	element item;
	if (is_empty(q))
		error("큐가 비어 있읍니다");
	else {
		item = q->front->item;	// 데이터를 꺼낸다.
		return item; 			// 데이터 반환
	}
}
// 연결된 큐 테스트 함수
void main(void)
{
	QueueType q;

	init(&q);
	enqueue(&q, 1);
	enqueue(&q, 2);
	enqueue(&q, 3);
	printf("dequeue()=%d\n", dequeue(&q));
	printf("dequeue()=%d\n", dequeue(&q));
	printf("dequeue()=%d\n", dequeue(&q));
}

 

 

[Reference]

• 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년