728x90
큐의 개념
일종의 리스트
삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서만 일어남.
삽입이 일어나는 쪽을 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;
}
'알고리즘, 자료구조 > 개념정리' 카테고리의 다른 글
[C][강의정리] 연결 리스트 개념과 기본 동작들 (5) (0) | 2022.07.12 |
---|---|
[C][강의정리] 연결 리스트 개념과 기본 동작들 (4) (0) | 2022.07.12 |
[C][강의정리] 연결 리스트 개념과 기본 동작들 (3) (0) | 2022.07.12 |
[C][강의정리] 연결 리스트 개념과 기본 동작들 (2) (0) | 2022.07.12 |
[C][강의정리] 연결 리스트 개념과 기본 동작들 (1) (0) | 2022.07.12 |