배열을 이용한 큐(Queue)

배열로 구현한 큐(QUEUE)

 

선형 큐

#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 10
#define ERROR_CODE 65000
typedef int element;

typedef struct{
	element queue[QUEUE_SIZE];
	int front;
	int rear;
}ArrayQueue;

ArrayQueue* createQueue(){
	ArrayQueue *q = (ArrayQueue*)malloc(sizeof(ArrayQueue));
	q->front = -1;
	q->rear = -1;
	return q;
}

int enQueue(ArrayQueue *q, element data){
	if(isFull(q)){
		printf("Queue is Overflow\n");
		return 0;
	}
	q->rear++;
	q->queue[q->rear] = data;
	return 1;
}

element deQueue(ArrayQueue *q){
	if(isEmpty(q)){
		printf("Queue is Underflow\n");
		return ERROR_CODE;
	}
	q->front++;
	return q->queue[q->front];
}

element peek(ArrayQueue *q){
	if(isEmpty(q)){
		printf("Queue is Empty");
		return ERROR_CODE;
	}
	return q->queue[q->front+1];
}

int isEmpty(ArrayQueue *q){
	if(q->front == q->rear){
		return 1;
	}
	else
		return 0;
}

int isFull(ArrayQueue *q){
	if(q->rear >= QUEUE_SIZE-1){
		printf("Queue is Overflow");
		return 1;
	}
	else
		return 0;
}

void printQueue(ArrayQueue *q){
	int i;
	for(i=q->front+1;i<=q->rear;i++){
		printf("%d\t", q->queue[i]);
	}
	printf("\n");
}

int main(){
	ArrayQueue* q1, *q2;
	q1=createQueue();
	q2=createQueue();
	enQueue(q1,10);
	enQueue(q1,20);
	printQueue(q1);
	deQueue(q1);
	printQueue(q1);
	return 0;
}

front와 rear가 같으면 비어있는 상태

rear가 QUEUE_SIZE-1과 같으면 가득찬 상태

 

선형 큐는 QUEUE_SIZE가 3이라면

3개의 데이터를 삽입하고 삭제하면

rear가 마지막 인덱스를 가르키기 때문에

비어있어도 가득찼다는 결과가 나온다

 

그 상태에서 추가를 하려면 배열 공간을 초과해서

오류가 뜨기 때문에 나온게 원형 큐

 

원형 큐

#include <stdio.h>
#include <stdlib.h>
#define QUEUE_SIZE 10
#define ERROR_CODE 65000
typedef int element;

typedef struct{
	element queue[QUEUE_SIZE];
	int front;
	int rear;
}ArrayQueue;

ArrayQueue* createQueue(){
	ArrayQueue *q = (ArrayQueue*)malloc(sizeof(ArrayQueue));
	q->front = 0;//-1로하면 포화상태 체크가 힘듦
	q->rear = 0;//-1로하면 포화상태 체크가 힘듦
	return q;
}

int enQueue(ArrayQueue *q, element data){
	if(isFull(q)){
		printf("Queue is Overflow\n");
		return 0;
	}
	q->rear = (q->rear+1)%QUEUE_SIZE;
	q->queue[q->rear] = data;
	return 1;
}

element deQueue(ArrayQueue *q){
	if(isEmpty(q)){
		printf("Queue is Underflow\n");
		return ERROR_CODE;
	}
	q->front = (q->front+1)%QUEUE_SIZE;
	return q->queue[q->front];
}

element peek(ArrayQueue *q){
	if(isEmpty(q)){
		printf("Queue is Empty");
		return ERROR_CODE;
	}
	return q->queue[q->front+1];
}

int isEmpty(ArrayQueue *q){
	if(q->front == q->rear){
		return 1;
	}
	else
		return 0;
}

int isFull(ArrayQueue *q){
	if((q->rear+1)%QUEUE_SIZE == q->front){
		return 1;
	}
	else
		return 0;
}

void printQueue(ArrayQueue *q){
	int i=q->(front+1)%QUEUE_SIZE;

	if(q->front == q->rear)return ;

	while(1){
		printf("%d\t", q->queue[i]);
		if(i==q->rear)break;
		i = (i+1)%QUEUE_SIZE;
	}
	printf("\n");
}

int main(){
	ArrayQueue* q1, *q2;
	q1=createQueue();
	q2=createQueue();
	enQueue(q1,10);
	enQueue(q1,20);
	printQueue(q1);
	deQueue(q1);
	printQueue(q1);
	return 0;
}

원형 큐와 선형 큐의 차이

 

원형큐는 front와 rear를 0으로 초기화

 

원형 큐의 삽입, 삭제 연산시 front와 rear를 증가시키면서 mod연산을 해줌

QUEUE_SIZE와 rear가 같으면 다시 처음 인덱스에 삽입하기 위해