1차원 정수 배열을 사용하여 정수를 저장하는 큐 작성
- 1차원 정수 배열을 정의하고
- 삽입, 삭제를 위한 변수인 front와 rear 생성
- front는 큐의 첫 번째 요소를 가리키고, rear는 큐의 마지막 요소를 가리킴
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
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->front = -1;
q->rear = -1;
}
void queue_print(QueueType* q) {
for (int i = 0; i < sizeof(q); 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;
}
element dequeue(QueueType* q) {
if (is_empty(q)) {
error("큐가 공백상태입니다.");
return -1;
}
element item = q->data[++(q->front)];
return item;
}- front와 rear의 초기값은 -1
- 데이터가 증가되면 rear을 하나 증가하고 그 위치에 데이터 저장
- 삭제 시에도 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제
int main(void) {
element item = 0;
QueueType q;
init_queue(&q);
enqueue(&q, 10); queue_print(&q);
enqueue(&q, 20); queue_print(&q);
enqueue(&q, 30); queue_print(&q);
item = dequeue(&q); queue_print(&q);
item = dequeue(&q); queue_print(&q);
item = dequeue(&q); queue_print(&q);
return 0;
}>>
선형 큐 응용 - 작업 스케줄링
- 큐는 운영 체제에서도 사용됨
- 운영 체제는 많은 작업들을 동시에 실행
- CPU가 하나뿐이고 모든 작업들은 우선순위를 가지지 않는다고 가정하면 작업들은 운영 체제에 들어간 순서대로 처리
- 이때 큐를 사용하여 작업 처리 가능
| Q[0] | Q[1] | Q[2] | Q[3] | Q[4] | front | rear | 설명 |
| -1 | -1 | 공백 큐 | |||||
| Job#1 | -1 | 0 | Job#1 추가 | ||||
| Job#1 | Job#2 | -1 | 1 | Job#2 추가 | |||
| Job#1 | Job#2 | Job#3 | -1 | 2 | Job#3 추가 | ||
| Job#2 | Job#3 | 0 | 2 | Job#1 삭제 | |||
| Job#3 | 1 | 2 | Job#2 삭제 |
