728x90
C언어로 쉽게 풀어쓴 자료구조: 5장 큐(선형, 원형),덱
큐(Queue)란?
먼저 들어온 데이터가 먼저 나가는 구조, 선입선출(FIFO, First in First out)
큐의 ADT
create(max_size) =
최대 크기가 max_size인 공백큐를 생성한다.
init(q) =
큐를 초기화 한다.
is_empty(q) =
if(size == 0) return TRUe;
else return FALSE;
is_full(q) =
if(size == max_size) return TRUe;
else return FALSE;
enqueue(q, e) =
if(is_full(q)) queue_full 오류;
else q의끝에 e를 추가한다.
dequeue(q) =
if(is_empty(q)) queue_empty 오류;
else q의 맨 앞에 있는 e를 제거하여 반환한다.
peek(q) =
if(is_empty(q)) queue_empty 오류;
else q의 맨 앞에 있는 e를 읽어서 반환한다.
5.2 선형큐
위에서 설명한 간단하게 생긴 큐가 선형큐이다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
int front;
int rear;
element data[MAX_QUEUE_SIZE];
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
void init_queue(QueueType *q)
{
q->rear = -1;
q->front = -1;
}
void queue_print(QueueType *q)
{
for (int i = 0; i<MAX_QUEUE_SIZE; i++) {
if (i <= q->front || i> q->rear)
printf(" | ");
else
printf("%d | ", q->data[i]);
}
printf("\n");
}
int is_full(QueueType *q)
{
if (q->rear == MAX_QUEUE_SIZE - 1)
return 1;
else
return 0;
}
int is_empty(QueueType *q)
{
if (q->front == q->rear)
return 1;
else
return 0;
}
void enqueue(QueueType *q, int item)
{
if (is_full(q)) {
error("큐가 포화상태입니다.");
return;
}
q->data[++(q->rear)] = item;
}
int dequeue(QueueType *q)
{
if (is_empty(q)) {
error("큐가 공백상태입니다.");
return -1;
}
int item = q->data[++(q->front)];
return item;
}
선형 큐는 쓰기 쉽지만 문제점이 있다.
- front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 된다.
- 배열의 앞부분이 비어 있더라도 사용하지 못한다
이를 보완하기 위해 배열의 끝네 도달하면 배열의 처음으로 데이터를 이동시키는 방법이 있다.
하지만 이보다 간단한 해결책은 원형큐를 사용하는 것이다.
5.3 원형큐
데이터 삽입, 삭제 전 front(가장 처음 들어간)와 rear(가장 최근에 들어간)을 원형으로 회전 시킨다.
※front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소(가장 최근에 들어간 값)를 가리킨다.
말이 원형이지 실제로 원형이 아니다...
선을 원처럼 사용한다는 의미..
10 삽입
20 삽입
삭제
➡️ 큐의 front가 rear보다 커지면 포화상태가 되어 오류 발생
원형큐 프로그램
#include <stdio.h>
#include <stdlib.h>
// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 공백 상태 검출 함수
void init_queue(QueueType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형큐 출력 함수
void queue_print(QueueType *q)
{
printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
if (!is_empty(q)) {
int i = q->front;
do {
i = (i + 1) % (MAX_QUEUE_SIZE);
printf("%d | ", q->data[i]);
if (i == q->rear)
break;
} while (i != q->front);
}
printf("\n");
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
// 삭제 함수
element peek(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// ===== 원형큐 코드 끝 ======
int main(void)
{
QueueType queue;
int element;
init_queue(&queue);
printf("--데이터 추가 단계--\n");
while (!is_full(&queue))
{
printf("정수를 입력하시오: ");
scanf("%d", &element);
enqueue(&queue, element);
queue_print(&queue);
}
printf("큐는 포화상태입니다.\n\n");
printf("--데이터 삭제 단계--\n");
while (!is_empty(&queue))
{
element = dequeue(&queue);
printf("꺼내진 정수: %d \n", element);
queue_print(&queue);
}
printf("큐는 공백상태입니다.\n");
return 0;
}
5.4 큐의 응용: 버퍼
서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화시키는 버퍼 역할을 담당한다.
5.5 덱
덱(deaue)이란?
큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다.
덱의 ADT
create(max_size) = 덱을성한다.
init(dq) = 큐를 초기화 한다.
is_empty(dq) = 덱이 공백 상태인지 검사한다.
is_full(dq) = 덱이 포화상태인지 검사한다.
add_front(dq, e) = 덱의 앞에 요소를 추가
add_rear(dq, e) = 덱의 뒤에 요소를 추가
delete_front(dq, e) = 덱의 앞에 요소를 반환한 후 삭제
delete_rear(dq, e) = 덱의 뒤에 요소를 반환한 후 삭제
get_front(dq) = 덱의 앞에 요소를 반환
get_rear(dq) = 덱의 뒤에 요소를 반환
원형 덱 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} DequeType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화
void init_deque(DequeType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(DequeType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(DequeType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형큐 출력 함수
void deque_print(DequeType *q)
{
printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
if (!is_empty(q)) {
int i = q->front;
do {
i = (i + 1) % (MAX_QUEUE_SIZE);
printf("%d | ", q->data[i]);
if (i == q->rear)
break;
} while (i != q->front);
}
printf("\n");
}
// 삽입 함수
void add_rear(DequeType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element delete_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
// 삭제 함수
element get_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
void add_front(DequeType *q, element val)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->data[q->front] = val;
q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
element delete_rear(DequeType *q)
{
int prev = q->rear;
if (is_empty(q))
error("큐가 공백상태입니다");
q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
return q->data[prev];
}
element get_rear(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[q->rear];
}
728x90
반응형
'C언어로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| [C언어로 쉽게 풀어쓴 자료구조] 7장 연결리스트 - Ⅱ (0) | 2024.11.23 |
|---|---|
| [C언어로 쉽게 풀어쓴 자료구조] 6장 연결리스트 - Ⅰ (1) | 2024.11.17 |
| [C언어로 쉽게 풀어쓴 자료구조] 4장 스택 (0) | 2024.11.11 |
| [C언어로 쉽게 풀어쓴 자료구조] 3장 배열, 구조체, 포인터 (2) | 2024.11.06 |
| [C언어로 쉽게 풀어쓴 자료구조] 1장 자료구조와 알고리즘 (2) | 2024.11.05 |