[자료구조]큐

큐 란?

대기열이라고 생각하면 쉽다. 놀이공원에 갔을 때 줄을 선 순서대로 표를 살 수 있는 구조라고 보면 된다.

특징: FIFO(First In First Out)

"가장 먼저 들어온 것부터 먼저 나간다"

쓰임

수요 > 공급 인 경우 모두 큐를 사용할 수 있다(기다려야하므로).

큐 ADT

연산	기능
Queue_init	큐 초기화(큐 생성 후 가장 먼저 호출)
Enqueue	큐에 데이터 삽입
Dequeue	가장 앞에 있는(먼저 저장된) 데이터를 삭제
Queue_Is_empty	큐가 비었을 때 True, 데이터가 있는 경우 False를 반환
Queue_Peek	가장 처음의 데이터를 반환하되 삭제하지 않음

예시 코드

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

// 큐의 노드를 정의
typedef struct QueueNode{
	int data; // 큐에 저장될 데이터
    struct QueueNode* next; // 다음 노드를 가리키는 포인터
} QueueNode;

// 큐를 정의
typedef struct Queue{
	QueueNode* front; // 큐의 맨 앞을 가리키는 포인터
    QueueNode* rear; // 큐의 맨 뒤를 가리키는 포인터
} Queue;

// 큐를 초기화하는 함수
void Queue_init(Queue* queue){
	queue->front = queue->rear = NULL;
}

// 큐가 비어있는지 확인하는 함수
int Queue_Is_empty(Queue* queue){
	return queue->front == NULL;
}

// 큐에 데이터를 삽입하는 함수
void Enqueue(Queue* queue, int data){
	QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->data = data;
    temp->next = NULL;
    
    if(queue->rear == NULL){
    	queue->front = queue->rear = temp;
        return;
    }
    queue->rear->next = temp;
    queue->rear = temp;
}

// 큐에 데이터를 삭제하는 함수
void Dequeue(Queue* queue){
	if(Queue_Is_empty(queue)) return;
    QueueNode* temp = queue->front;
    queue->front = queue->front->next;
    if(queue->front == NULL){
    	queue->rear = NULL;
    }
    free(temp);
}

// 큐의 첫번째 데이터를 확인하는 함수
int Queue_Peek(Queue* queue){
	if(Queue_Is_empty(queue)){
    	return -1;
    }
    return queue->front->data;
}