선형큐의 문제점
- front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달
- 배열의 앞부분이 비어 있더라도 사용하지 못함
- 따라서 주기적으로 모든 요소를 왼쪽으로 이동시켜야 함
- 이와 같은 문제를 해결하기 위해 원형 배열을 고려
원형큐
- front와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE-1)에 도달하면 다음에 증가되는 값이 0이 되도록 함
- 처음과 끝이 연결된 원형 배열을 상정
- 원형큐에서 front와 rear의 초기값은 -1이 아닌 0
- front는 항상 큐의 첫 번째 요소의 하나 앞을, rear는 마지막 요소를 가리킴
- 데이터가 삽입 시 rear가 먼저 증가되고, 증가된 위치에 데이터 삽입
- 데이터 삭제 시 front가 먼저 증가되고, 증가된 위치에서 데이터 삭제
- front==rear이면 원형큐가 공백 상태
- 공백 상태와 포화 상태를 구별하기 위해 하나의 자리는 항상 비워 둠
- 요소들이 개수를 저장하는 별도의 count 변수를 사용한다면 한 자리를 비워두지 않아도 무방
원형큐의 삽입, 삭제 알고리즘
- 선형큐와 유사코드 동일
- 삽입이나 삭제 전에 front와 rear를 원형 회전시켜 하나 증가시키고, 증가된 위치에 데이터 삽입 또는 삭제
- front와 rear를 원형으로 회전시키는 것이 중요
- 나머지 연산자(%) 이용하여 원형 회전 구현
front = (front+1)%MAX_QUEUE_SIZE;
rear = (rear+1)%MAX_QUEUE_SIZE:- front와 rear 값은 (MAX_QUEUE_SIZE-1)에서 하나 증가되면 0으로 변화
- MAX_QUEUE_SIZE가 5라면 front와 rear는 0, 1, 2, 3, 4, 0, ... 과 같이 변화
원형큐의 구현
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {
int front, rear;
element data[MAX_QUEUE_SIZE];
}QueueType;
//오류 함수
void error(char* message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
void init_queue(QueueType* q) {
q->front = 0;
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;
}>>
