C - 큐(Queue)

큐는 입력과 출력하는 구멍이 다르다. 입력하는 구멍을 rear라고 하고 출력하는 구멍을 front라고 한다. 데이터를 넣고 꺼냄을 각각 enqueue, dequeue라고 한다.

front와 rear를 고정시키지 않고 변수형태로 정의하면 링 버퍼(ring buffer)로 큐를 구현 할 수 있다. 이러면 하나 출력 할 때마다 남은 데이터를 shift 할 필요가 없어진다.

헤더 (IntQueue.h)

#ifndef ___IntQueue
#define ___IntQueue

typedef struct {
	int max;
    int num; //현재의 요소 개수
    int front;
    int rear;
    int* que;
} IntQueue;

int Initialize(IntQueue* q, int max);

int Enque(IntQueue* q, int x);

int Deque(IntQueue* q, int* x);

int Peek(const IntQueue* q, int* x);

void Clear(IntQueue* q);

int Capacity(const IntQueue* q);

Int Size(const IntQueue* q);

int IsEmpty(const IntQueue* q);

int IsFull(const IntQueue* q);

int Search(const IntQueue* q, int x);

void Print(const IntQueue* q);

void Terminate(IntQueue* q);

#endif

함수(IntQueue.c)

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

int Initialize(IntQueue* q, int max) {
	q->num = q->front = q->rear = 0;
    
    if((q->que = calloc(max, sizeof(int))) == NULL) {
    	q-> max=0;
        return -1;
        }
    q->max = max;
    return 0;
}

int Enque(IntQueue* q, int x) {
	if(q->num >= q->max) return -1;
   	else {
    	q->num++;
        q->que[q->rear++] = x;
        
        if(q->rear == q->max) q->rear = 0;
        }
    }
    
int Deque(IntQueue* q, int* x) {
	if(q->num <= 0) return -1;
    else {
    	q->num--;
        *x = q->que[q->front++];
        
        if(q->front == q->max) q->front = 0;
    }
}

int Peek(const IntQueue* q, int* x) {
	if(q->num <= 0) return -1;
    *x = q->que[q->front];
    return 0;
}

void Clear(IntQueue* q) {
	q->num = q->front = q->rear = 0;
}

int Capacity(const IntQueue* q) {
	return q->max;
}

int Size(const IntQueue* q) {
	return q->num;
}

int IsEmpty(const IntQueue* q) {
	return q->num <= 0;
}

int IsFull(const IntQueue* q) {
	return q->num >= q->max;
}

int Search(const IntQueue* q, int x) {
	int i, idx;
    for(i=0; i < q->num; i++) {
    	if(q->que[idx = (i + q->front) % q->max] ==x)
        	return idx;
    }
    return -1;
}

void Print(const IntQueue* q) {
	int i;
    for(i = 0; i< q->num; i++)
    	printf("%d ", q->que[(i+ q->front) % q->max);
    putchar('\n\);
}

void Terminate(IntQueue* q) {
	if(q->que != NULL)
    	free(q->que);
    q->max = q->num = q->front = q->rear = 0;
}