[자료구조] 큐 (1)

📕스택의 경우, 나중에 들어온 데이터가 먼저 나가지만 큐는 먼저 데이터가 먼저 나가는 구조다 (FIFO : First - in - First - Out). 큐는 삽입과 삭제가 다른 쪽에서 일어난다.

rear: 큐의 후단, 삽입이 이루어짐
front: 큐의 전단, 삭제가 이루어짐

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 100

typedef char element;  //char라는 기본 데이터 타입을 element라는 이름으로 정의하겠다.

typedef struct //typedef 하면 구조체 이름 생략 가능, 자기 참조 필드가 없기 때문에 생략 가능함
{
	element queue[N];
	int front, rear;
}Queuetype;

void init(Queuetype* Q) //구조체 포인터로 받기
{
	Q->front = Q->rear = -1;
}

int isEmpty(Queuetype* Q)
{
	//top처럼 올라갔다 내려오는게 아니라 계속 오른쪽으로 가니까, 한번이라도 뭔가 있었다면 -1이 될 수 없음
	return Q->rear == Q->front;
}

int isFull(Queuetype* Q)
{
	return Q->rear == N - 1; //전체 배열의 크기 -1만큼
}

void enqueue(Queuetype* Q, element e)
{
	if (isFull(Q))
	{
		printf("FULL!\n");
		return;
	}
	else
	{
		Q->rear=Q->rear+1;
		Q->queue[Q->rear] = e;
	}
}

element dequeue(Queuetype* Q)
{
	if (isEmpty(Q))
	{
		printf("Empty!!\n");
		return -1;
	}
	else
	{
		Q->front++;
		return Q->queue[Q->front];
	}
}

element peek(Queuetype* Q)
{
	if (isEmpty(Q))
	{
		printf("Empty!!\n");
		return -1;
	}

	return Q->queue[Q->front +1];
}

void print(Queuetype* Q)
{
	printf("Front Pos : %d, Rear Pos: %d\n", Q->front, Q->rear);
	for (int i = Q->front+1; i <= Q->rear; i++)
		printf("[%c]", Q->queue[i]);
	
	printf("\n");
}

int main()
{
	Queuetype Q;
	init(&Q); //Q의 주소가 날라간다
	srand(time(NULL));

	for (int i = 0; i < 7; i++)
	{
		enqueue(&Q, rand() % 26 + 65);
	}

	dequeue(&Q);
	dequeue(&Q);
	dequeue(&Q);
	print(&Q);

}

선형큐의 단점: front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고, 배열의 앞부분이 비어있더라도 사용하지 못한다. 더 사용하려면 이동이 필요하다.



(2) 원형큐
front와 rear의 값이 배열의 끝 (N-1)에 도달하면 다음 증가되는 값은 0으로 한다. 즉, 배열이 원형으로 처음과 끝이 연결되어 있다고 생각하는 것이다.

💡원형큐에서 하나의 자리는 항상 비워둔다. 포화상태와 공백상태를 구별하기 위해서이다. front==rear이면 공백상태가 되고, front가 rear보다 하나 앞에 있으면 포화상태가 된다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 10

typedef char element;  //char라는 기본 데이터 타입을 element라는 이름으로 정의하겠다.

typedef struct //typedef 하면 구조체 이름 생략 가능, 자기 참조 필드가 없기 때문에 생략 가능함
{
	element queue[N];
	int front, rear;
}Queuetype;

void init(Queuetype* Q) //구조체 포인터로 받기
{
	Q->front = Q->rear = 0;
}

int isEmpty(Queuetype* Q)
{
	//top처럼 올라갔다 내려오는게 아니라 계속 오른쪽으로 가니까, 한번이라도 뭔가 있었다면 -1이 될 수 없음
	return Q->rear == Q->front;
}

int isFull(Queuetype* Q)
{
	return ((Q->rear +1)%N == Q->front); //전체 배열의 크기 -1만큼
}

void enqueue(Queuetype* Q, element e)
{
	if (isFull(Q))
		printf("FULL!\n");
	else
	{
		Q->rear = (Q->rear+1) %N;
		Q->queue[Q->rear] = e;
	}
}

element dequeue(Queuetype* Q)
{
	if (isEmpty(Q))
	{
		printf("Empty!!\n");
		return -1;
	}

	Q->front=(Q->front+1)%N;
	return Q->queue[Q->front];
}

element peek(Queuetype* Q)
{
	if (isEmpty(Q))
	{
		printf("Empty!!\n");
		return -1;
	}

	return Q->queue[(Q->front + 1)%N];
}

void print(Queuetype* Q)
{
	printf("Front Pos : %d, Rear Pos: %d\n", Q->front, Q->rear);
	
	int i = Q->front;
	while (i != Q->rear)
	{
		i = (i + 1) % N;
		printf("[%c] ", Q->queue[i]);
	}
	printf("\n");
}

int main()

{
	Queuetype Q;
	init(&Q); //Q의 주소가 날라간다
	srand(time(NULL));

	for (int i = 0; i < 5; i++)
		enqueue(&Q, rand() % 26 + 65); //아스키코드 대문자, 알파벳 값 난수로 발생

	print(&Q);

	for (int i = 0; i < 3; i++)
		printf("delete [%c] \n", dequeue(&Q));
	printf("\n\n");

	print(&Q);
}