[자료구조] C언어 - 우선순위 큐(priority queue) 구현 - 객체지향

- C언어로 구현한 우선순위 큐(priority queue) 코드이다. 완벽하진 않지만 c에서 객체지향 개념을 넣을 수 있는 기본 베이스는 마련해둔 코드이다.

 

- 글 말고 github으로 보려면 여기를 누르면 된다.

 

- 영어를 잘 못하지만 주석을 영어로 작성했으므로 틀린 표현이 많을 수 있다. (댓글로 알려줘요 ㅠ)

 

 

0. 사용 예시

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

int main(int argc, char* argv[])
{
	priority_queue_t* q = create_priority_queue();

	q->op->insert(q, 132);
	q->op->insert(q, 6929);
	q->op->insert(q, 232);
	q->op->insert(q, 5933);
	q->op->insert(q, 3254);
	q->op->insert(q, 12);
	q->op->print(q);
	
	q->op->del(q, 3254);
	q->op->print(q);

	q->op->destroy(q);
}

 

1. priority_queue.h

/**
* Priority Queue Header
* made by nahwasa
*/

#ifndef PRIORITY_QUEUE_H_NAHWASA
#define PRIORITY_QUEUE_H_NAHWASA
 
#define MAX_SIZE 100

typedef struct {
	int* arr;
	int rear;
	int capacity;
	struct priority_queue_operations* op;
} priority_queue_t;

struct priority_queue_operations {
	void (*insert)(priority_queue_t* q, int data);
	void (*del)(priority_queue_t* q, int data);
	void (*print)(priority_queue_t* q);
	void (*destroy)(priority_queue_t* q);
};	

extern priority_queue_t* create_priority_queue();

#endif

 

2. priority_queue.c

/**
* Priority Queue using array
* made by nahwasa
*/

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

static void insert(priority_queue_t* q, int data);
static void del(priority_queue_t* q, int data);
static void print(priority_queue_t* q);
static void destroy(priority_queue_t* q);

static struct priority_queue_operations op = 
	{
		.insert = insert,
		.del = del,
		.print = print,
		.destroy = destroy
	};
 
priority_queue_t* create_priority_queue()
{
	priority_queue_t* q = (priority_queue_t*)malloc(sizeof(priority_queue_t));
	q->arr = (int*)malloc(sizeof(int) * MAX_SIZE);
    	q->rear = -1;
	q->op = &op;
	q->capacity = MAX_SIZE;
}

static void destroy(priority_queue_t* q)
{
	free(q->arr);
	q->arr = NULL;
	q->op = NULL;
	free(q);	
	q = NULL;
}

/*
* arrange array and insert 'data'
*/
static void re_arrange_and_insert(priority_queue_t* q, int data)
{
	int i, j;
 
	for (i = 0; i <= q->rear; i++)	{
		if (data >= q->arr[i]) {
			for (j = q->rear + 1; j > i; j--){
				q->arr[j] = q->arr[j - 1];
			}
			q->arr[i] = data;
			return;
		}
	}
	q->arr[i] = data;
}

/*
* when array size is over, must increase size
*/
static void increase_array_size(priority_queue_t* q)
{
	int i;
	int* new_arr = (int*)malloc(sizeof(int) * (q->capacity + MAX_SIZE));
	q->capacity += MAX_SIZE;
	
	for (i = 0; i <= q->rear; i++) {
		new_arr[i] = q->arr[i];
	}

	free(q->arr);
	q->arr = new_arr;
}

/*
* insert 'data' to 'q'
*/
static void insert(priority_queue_t* q, int data)
{
	if (q->rear >= MAX_SIZE - 1) {
		increase_array_size(q);
	}

	if (q->rear == -1) {
		q->rear++;
		q->arr[q->rear] = data;
		return;
	} else
		re_arrange_and_insert(q, data);

	q->rear++;
}

/*
* remove 'data' from 'q'
*/
static void del(priority_queue_t* q, int data)
{
	int i;
 
	if (q->rear==-1) {
		printf("No Data in Q\n");
		return;
	}
 
	for (i = 0; i <= q->rear; i++) {
		if (data == q->arr[i]) {
			for (; i < q->rear; i++){
				q->arr[i] = q->arr[i + 1];
			}
 
			q->arr[i] = -99;
			q->rear--;

			return;
		}
	}

	printf("Can't find %d\n", data);
}
 

static void print(priority_queue_t* q)
{
	int i;

	if (q->rear == -1){
		printf("No Data in Q\n");
		return;
	}
 
	for (i = 0; i <= q->rear; i++){
		printf("%d ", q->arr[i]);
	}
	printf("\n");
}