자료구조 - 큐 (선형큐)

큐란?

스택의 경우 데이터를 차곡차곡 쌓아 올리는 형태이지만,

큐는 데이터를 줄 세우는 형태로 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있습니다.

이러한 특성을 선입선출 (FIFO - First In First Out) 이라고 합니다.

 

새로운 데이터는 큐의 뒤에서 추가되고, 데이터를 삭제할 때에는 큐의 앞에서 삭제하는 구조입니다.

그렇기 때문에 큐에서의 삽입과 삭제는 다른쪽에서 일어나게 됩니다.

큐의 구조

 

큐 연산

# 큐 생성
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(1)) queue_empty 오류;
    else q의 맨 앞에 있는 e를 제거하여 반환한다.
    
# 큐 맨 앞의 글자 반환
peek(q) ::=
    if (is_empty(q)) queue_empty 오류;
    else q의 맨 앞에 있는 e를  읽어서 반환한다.

 

선형큐

front - 큐의 첫번째 요소

rear - 큐의 마지막 요소

 

선형큐에서

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(const 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(" %2d |", 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;
}

 

실행결과