앞서 이야기한 선형큐에는 많은 문제점이 있다.
1. 배열의 앞부분이 비어있더라도 사용할 수 없어 메모리 낭비가 심하다.
2. 큐의 크기가 제한적이다.
3. 데이터 이동 비용이 크다.
4. 큐가 포화상태일 경우 사용 불가하다. 때문에 동적으로 조정하여 해결해야한다.
이러한 선형큐의 문제점들을 쉽게 해결할 수 있는 것이 원형큐이다.
원형큐 연산
front 와 rear 의 초기값은 모두 0이다.
front 는 큐의 첫 번째 요소의 하나 앞을, rear 은 마지막 요소를 가리킨다.
front 와 rear 의 값이 (배열의크기 - 1) 의 위치에서 하나 증가할 땐 0이 된다.
- 데이터 삽입 시
포화상태 검사 후 rear 증가, 증가된 위치에 새로운 데이터 삽입
- 데이터 삭제 시
공백 상태 검사 후 front 증가, 증가된 위치에 데이터 삭제
원형큐의 포화상태와 공백상태를 구별하기 위해 하나의 자리는 항상 비워두어야 한다. 그렇지 않으면 공백상태와 포화상태를 구분할 수 없다.
- 공백 상태
front == rear
- 포화 상태
front == rear + 1
원형큐 프로그램
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define _CRT_SECURE_NO_WARNINGS
// 원형큐 정의
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(const char* message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화 함수
void init_queue(QueueType* q) {
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
bool is_empty(QueueType* q) {
return (q->front == q->rear);
}
// 포화상태 검출 함수
bool 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];
}
// 메인함수
int main(void) {
QueueType queue;
int element;
init_queue(&queue);
printf("--데이터 추가 단계--\n");
while (!is_full(&queue)) {
printf("정수를 입력하시오: ");
scanf_s("%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;
}
실행결과
'Computer Science' 카테고리의 다른 글
자료구조 - 큐 (선형큐) (0) | 2023.11.27 |
---|---|
자료구조 - 스택 (0) | 2023.11.24 |
자료구조 - 선형자료구조 (연결리스트) (2) | 2023.09.23 |
자료구조 - 복잡도 (0) | 2023.09.22 |