큐란?
스택의 경우 데이터를 차곡차곡 쌓아 올리는 형태이지만,
큐는 데이터를 줄 세우는 형태로 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있습니다.
이러한 특성을 선입선출 (FIFO - First In First Out) 이라고 합니다.
새로운 데이터는 큐의 뒤에서 추가되고, 데이터를 삭제할 때에는 큐의 앞에서 삭제하는 구조입니다.
그렇기 때문에 큐에서의 삽입과 삭제는 다른쪽에서 일어나게 됩니다.
큐 연산
# 큐 생성
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(1)) queue_empty 오류;
else q의 맨 앞에 있는 e를 제거하여 반환한다.
# 큐 맨 앞의 글자 반환
peek(q) ::=
if (is_empty(q)) queue_empty 오류;
else q의 맨 앞에 있는 e를 읽어서 반환한다.
선형큐
front - 큐의 첫번째 요소
rear - 큐의 마지막 요소
선형큐에서
front, rear 의 초기화 값은 -1 입니다.
데이터가 증가되면 rear 의 값을 하나 증가시키고 그 위치에 데이터가 저장됩니다.
데이터를 삭제할 때는 front 를 하나 증가시키고 front 가 가리키는 위치에 데이터를 삭제합니다.
선형큐 프로그램
#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(const 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(" %2d |", 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;
}
int main(void) {
int 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;
}
실행결과
'Computer Science' 카테고리의 다른 글
자료구조 - 큐 (원형큐) (0) | 2023.12.01 |
---|---|
자료구조 - 스택 (0) | 2023.11.24 |
자료구조 - 선형자료구조 (연결리스트) (2) | 2023.09.23 |
자료구조 - 복잡도 (0) | 2023.09.22 |