[자료구조] - 큐 (Queue)(선형큐)(C언어)

[ 큐의 개념 ]

: 컴퓨터의 기본적인 자료구조 중 하나로 먼저 집어넣은 자료가 먼저 나오는 FIFO(First In First Out) 또는 LILO(Last In Last Out) 구조의 자료형식을 말함.

 

큐는 선형큐와 원형큐가 존재하며 이번 포스팅에서는 선형큐에 대해 알아보겠습니다.

 

선형큐는 데이터를 집어넣는 Enqueue 기능과 데이터를 내보내는 Dequeue 기능이 존재합니다.

큐의 핵심 key 로는 front 와 rear이 존재합니다.

 

Front는 가장 먼저 들어온 데이터를 가리키고 Rear은 가장 나중에 들어온 데이터를 가리키게 됩니다.

 

예시로 살펴봅시다

< Enqueue >

첫번째 데이터가 들어옴

두번째 데이터가 들어옴

세번째 데이터가 들어옴

Enqueue의 방식을 살펴보면 front는 고정되어 있고 새로 들어오는 데이터는 큐의 끝(tail)에 저장되는 방식이 반복됩니다. 데이터가 들어옴에 따라 rear은 계속 이동합니다.

 

< Dequeue >

 

반대로 Dequeue는 데이터를 꺼낼 때마다 front가 rear 쪽으로 한 칸 씩 이동하게 되겠죠.

 

 

데이터 삽입 : rear 

데이터 삭제 : front 

 

에서 일어난다고 보면 됩니다.

 

[ 코드 ]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
	int data;
	struct Node* next;
}Node;

typedef struct Queue {
	Node* front;
	Node* rear;
	int dataNum;
}Queue;

void InitQueue(Queue* queue);
bool IsEmpty(Queue* queue);
void Enqueue(Queue* queue, int data);
int Dequeue(Queue* queue);
void Peek(Queue* queue);

int main() {
	Queue q;
	InitQueue(&q);
	for (int i = 1; i <= 5; i++) {
		Enqueue(&q, i);
	}
	Peek(&q);
	while (!IsEmpty(&q)) {
		printf("%d ", Dequeue(&q));
	}
	printf("\n");

	return 0;

}
void InitQueue(Queue* queue) {
	queue->front = NULL;
	queue->rear = NULL;
	queue->dataNum = 0;
}

bool IsEmpty(Queue* queue) {
	if (queue->dataNum == 0)
		return true;
	else
		return false;
}

void Enqueue(Queue* queue, int data) {
	Node* curr = (Node*)malloc(sizeof(Node));
	curr->data = data;
	curr->next = NULL;

	if (IsEmpty(queue)) {//큐가 비어있는 경우
		queue->front = curr;
	}
	else {
		queue->rear->next = curr;
	}
	queue->rear = curr;//맨 뒤를 현재 집어넣은 curr로
	queue->dataNum++;//데이터 개수 1 증가
}

int Dequeue(Queue* queue) {
	int result = 0;
	Node* curr = (Node*)malloc(sizeof(Node));
	if (IsEmpty(queue)) {
		return result;
	}
	curr = queue->front;//제일 앞 노드를 curr로 설정
	result = curr->data;//제일 앞 노드 데이터 반환 예정
	queue->front = curr->next;//맨 앞을 curr 다음 노드로 설정
	free(curr);//노드 버리기
	queue->dataNum--;//큐 데이터 개수 1 감소
	return result;
}

void Peek(Queue* queue) {
	printf("%d\n", queue->rear->data);
}