자료구조_선형큐

큐

나중에 들어온 데이터가 먼저 나가는 구조인 스택과 달리
큐(queue)는 먼저 들어온 데이터가 먼저 나가는 구조

즉, 큐는 FIFO

스택과 큐의 차이점

스택
삽입과 삭제가 같은 쪽에서 일어남

큐
삽입과 삭제가 다른 쪽에서 일어남

삽입이 일어나는 곳 : rear(후단)
삭제가 일어나는 곳 : front(전단)

enqueue 연산
큐에 요소를 추가하는 연산으로 큐의 맨 뒤에 새로운 요소를 추가

dequeue 연산
큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환

선형큐

front, rear의 초기값: -1
front는 큐의 첫번째 요소를 가리킴
rear는 큐의 마지막 요소를 가리킴

데이터가 증가 => rear를 하나 증가 => 그 위치에 데이터 저장
데이터를 삭제 => front를 하나 증가 => 그 위치에 데이터 삭제

선형큐 연습하기

#define _CRT_SECURE_NO_WARNINGS
#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 init_queue(QueueType *q) {
	q->front = -1;
	q->rear = -1;
}

//is_full 함수
int is_full(QueueType *q) {
	return q->rear == MAX_QUEUE_SIZE - 1;
}

//is_empty 함수
int is_empty(QueueType* q) {
	return q->front == q->rear;
}

//데이터 삽입 함수
void enqueue(QueueType *q, element item) {
	if (is_full(q)) {
		fprintf(stderr, "스택오버플로우\n");
		return;
	}
	else q->data[++(q->rear)] = item;
}

//데이터 삭제 함수
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		printf("큐가 비었음!\n");
		exit(1);
	}
	else return q->data[++(q->front)];
}

int main() {
	QueueType q;
	init_queue(&q);
	enqueue(&q, 10); enqueue(&q, 20); enqueue(&q, 30);

	for (int i = 0; i <= q.rear; i++) {
		printf("%d\n", q.data[i]);
	}
	printf("\n");
	printf("삭제 item 출력\n");

	element item = dequeue(&q);
	printf("%d\n", item);
	item = dequeue(&q);
	printf("%d\n", item);
	item = dequeue(&q);
	printf("%d\n", item);
}