C Circular Queue 만들기

Circular Queue의 C 버전이다

 

내용은 C++의 Circular Queue와 같으므로 내용보단 구조적인 차이를 염두해 두고 만들어 보겠다

https://suldenlion.tistory.com/78

(C++로 자료구조 구현하기) Queue 만들기 (version.2 - Circular Queue)

 

우선 main.c 프로그램이다

#include <stdio.h>
#include "queue.h"

extern void print(Queue *q);
main() 
{
	Queue q;
	int i;

	initialize(&q);
	print(&q);
	enqueue(&q, 10);
	enqueue(&q, 20);
	enqueue(&q, 30);
	printf("%d\n", dequeue(&q));
	for (i = 1; i < 200; i++) {
		enqueue(&q, i);
		printf("%d\n", dequeue(&q));
	}
	print(&q);
}

 

printf()를 위한 stdio.h와 queue를 정의한 queue.h 파일을 include 시켜준다

그리고 큐의 내용을 출력시켜보기 위한 print() 함수를 만들것인데 함수 사용을 위해서 main() 함수 위쪽에 "extern void print(Queue *q); 라고 라인을 추가시켜야 한다. C언어의 특징 중 하나인 Forward declaration 이라고 한다.

 

메인에서는 큐를 initialize 시켜주고 enqueue, dequeue, print를 각각 해본다.

 

 

다음으로 Queue의 헤더 파일이다.

#define MAX		(15)

typedef struct _queue {
	int s[MAX];
	int front;
	int rear;
} Queue;

extern void initialize(Queue *p);
extern void enqueue(Queue *p, int x);
extern int dequeue(Queue *p);
extern void print(Queue *p);

 

구조체 형식으로 Queue를 정의한 후 data member로 배열, front 변수, rear 변수를 정의해 둔다.

밑에는 사용할 메서드들을 추상화 시켜 놓는다.

 

 

그 다음으로 Queue.c를 구현해 보자면

#include <stdio.h>
#include <stdlib.h>
#include "Queue.h"

typedef char	BOOL;

#define TRUE		(1)
#define FALSE		(0)	

BOOL isFull(Queue *q);
void overFlow();

void print(Queue *q) {
	int i;
	printf("%d, %d\n", q->front, q->rear);
	for (i = 0; i < MAX; i++) {
		printf("%d ",q->s[i]);
	}
	printf("\n");
}

void initialize(Queue *q) {
	int i;
	q->front = 0;
	q->rear = 0;
	for (i = 0; i < MAX; i++) q->s[i] = 0;
}

void enqueue(Queue *q, int x) {
	if (isFull(q)) overFlow();
	q->rear = ((q->rear)+1)%MAX;
	q->s[q->rear] = x;
}

BOOL isFull(Queue *q) {
	if (((q->rear)+1)%MAX == q->front) return TRUE;
	return FALSE;
}

void overFlow() {
	printf("Overflow\n");
	exit(-1);
}

BOOL isEmpty(Queue *q) {
	if (q->front == q->rear) return TRUE;
	return FALSE;
}

void empty() {
	printf("Empty\n");
	exit(-1);
}

int dequeue(Queue *q) {
	if (isEmpty(q)) empty();
	q->front = ((q->front)+1)%MAX;
	return q->s[q->front];
}

Queue 자체는 C++ Circular Queue와 방식이 같다. 차이점으로는 큐의 data member들에 접근할때 일일히 자바의 this에 해당하는 "->"를 해주어야 한다는 것이다. 

또한 C언어에는 boolean type 이 없기 때문에 BOOL이란 이름의 char 타입의 리턴을 위한 변수를 매크로로써 지정해준다.

마찬가지로 TRUE와 FALSE를 각각 1과 0으로 지정해 놓고 사용하도록 한다.

 

확실히 C가 사용하기 귀찮은 부분이 많은것 같다.