[C][강의정리] 큐 개념과 구현 (1)

https://youtu.be/_aU2e70gYlo

 

큐의 개념

일종의 리스트

삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서만 일어남.

삽입이 일어나는 쪽을 rear, 삭제가 일어나는 쪽을 front

First In, First Out

예, 프린터 큐

 

 

 

enqueue: 큐 rear에 새로운 원소를 삽입하는 연산

dequeue: 큐 front에 있는 원소를 큐로부터 삭제

peek: 큐 front에 있는 front에 있는 원소를 제거하지 않고 반환하는 연산

is_empty: 큐가 비었는지 검사

 

 

 

큐의 응용

CPU 스케쥴링

데이터 버퍼

그 외에도 자원을 공유하는 대부분의 경우에 큐가 사용됨

 

 

큐의 규현

//queueADT.h
#ifndef QUEUEADT_H
#define QUEUEADT_H

#include <stdbool.h>

typedef int Item;

typedef struct queue_type *Queue;

Queue create();
void destroy(Queue q);
void make_empty(Queue q);
bool is_empty(Queue q);
void enqueue(Queue q, Item i);
Item dequeue(Queue q);
Item peek(Queue q);
int get_size(Queue q);

#endif

// queueADT.c
#include <stdio.h>
#include <stdlib.h>
#include "queueADT.h"

struct node {
	Item data;
    struct node *next;
};

struct queue_type {
	struct node *front;
    struct node *rear;
    int size;
};

void terminate(const char *message)
{
	printf("%s\n", message);
    exit(EXIT_FAILURE);
}

int get_size(Queue q)
{
	return q->size;
}

Queue create()
{
	Queue q = (Queue)malloc(sizeof(struct queue_type));
    if (q == NULL)
    	terminate("Error in create: queue could not be created.");
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
    return q;
}

void destroy(Queue q)
{
	make_empty(q);
    free(q);
}

void make_empty(Queue q)
{
	while (!is_empty(q))
    	dequeue(q);
    q->size = 0;
}

bool is_empty(Queue q)
{
	return q->front == NULL;
}

void enqueue(Queue q, Item i)
{
	struct node *new_node = malloc(sizeof(struct node));
    if (new_node == NULL)
    	terminate("Error in push: queue is full.");
        
    new_node->data = i;
    new_node->next = NULL;
    if (q->front == NULL)
    {
    	q->front = new_node;
        q->rear = new_node;
    }
    else
    {
    	q->rear->next = new_node;
        q->rear = new_node;
	}
    q->size++;
}

Item dequeue(Queue q)
{
	struct node *old_front;
    Item i;
    if (is_empty(q))
    	terminate("Error in dequeue: queue is empty.");
        
    old_front = q->front;
    i = old_front->data;
    if (q->front == NULL)
    	q->rear = NULL;
    free(old_front);
    q->size--;
    return i;
}

Item peek(Queue q)
{
	if (is_empty(q))
    	terminate("Error in peek: queue is empty.");
    return q->front->data;
}