[S/W] 간단한 큐(Queue)의 구현

간단한 큐(Queue)의 구현

순환 큐가 가장 좋은 것으로 알고 있지만 

빠른 알고리즘의 구현을 할 경우에는 전체 큐의 범위를 넉넉하게 잡고 아래와 같은 방식으로 구현하였다.

큐는 BFS 알고리즘을 쓸때 주로 이용된다.

여기서 사용된 Front 와 Rear 의 용도는 다음과 같다.

값의 존재 기준으로 보면

Front 는 값이 존재하는 제일 앞에서 index 값이 -1 만큼인 값

Rear 는 값이 존재하는 제일 마지막에서 index 값이 +1 만큼인 값

값을 넣어야 하는 기준으로 보면

값을 꺼낼 때 Front 의 현재 index 에서 +1의 위치 값을 꺼내온다.

값을 넣을 때 Rear 의 index 위치에 값을 넣는다.

Queue에 Push 할때는 Rear 가 가리키는 Index 에 넣고 Rear 의 값을 +1 한다.

Queue에 있는 값을 Pop으로 꺼낼때는 Front 의 +1한 다음 Index 값이 Rear 와 같은 경우 Null 을 알려주고 그렇지 않은 경우 Front 값을 +1 하고 해당 위치에 값을 Return 한다.

#include <stdio.h>

#define SIZE 100

struct vertex{
	int x;
	int y;
}typedef vertext;

vertext queue[SIZE];
int front=-1;
int rear=0;

void push_rear(vertext a){
	queue[rear++] = a;
}

vertext pop_rear(){
	if (rear == front+1){
		// QUEUE NULL
		printf("QUEUE is NULL\n");
	}
	else{
		return queue[++front];
	}
}

void printQueue(){
	int i=front+1;
	printf("QUEUE : ");
	if (i < rear){
		do{
			printf("(%d, %d) ", queue[i].x, queue[i].y);
			i++;
		} while (i< rear);
	}
	printf("\n");

}

int main(){
	int i=0;
	int T=0;
	vertext value;
	int b,c,d,e,f,g;

	int a[10];
	
	while (1){
		printf("----------------\n");
		printf("1. Push 2.Pop\n");
		scanf("%d", &T);

		if (T == 1){
			scanf("%d %d", &value.x, &value.y);
			printf("%d %d", value.x, value.y);
			push_rear(value);

		}
		else if (T == 2){
			pop_rear();
		}

		printf("----------------\n");
		printQueue();
	}

	return 0;
}