[C] 큐(Queue)

큐(Queue)

---

큐(Queue)?

큐는 FIFO(First In First Out)구조로 가장 먼저 들어간 값이 가장먼저 나오는 구조입니다.

삽입하는 put 동작과 삭제하는 get 동작이 있습니다.

front(앞)에서 값을 얻어내고, rear(뒤)에 값을 넣습니다.

1. 큐 형태

2. 큐 종류

큐의 종류는  선형 큐, 원형 큐, 우선순위 큐 등이 있습니다.

- 선형 큐(Linear Queue) : 기본적인 큐의 형태로 막대모양의 큐로 빈 공간 사용 시 모든 자료를 꺼내거나 옮겨야 한다는 단점이 있음

- 원형 큐(Circular Queue) : 선형큐의 단점을 보완하는 구조로 front와 rear가 연결된 형태

- 우선순위 큐(Priority Queue) : 데이터 삽입 시 우선순위에 따라 정렬 후 저장하는 방식

---

배열을 이용한 원형 큐 예제

원형큐의 경우 front, rear 구분을 위한 공간이 하나 필요합니다.

그래서, 크기가 10인 큐의 경우 사용가능한 공간은 9가 됩니다.

큐로 사용할 int형 배열 선언 및 초기화 함수

#include "stdio.h"

#define MAX 10

int queue[MAX];

int front, rear;

void init_queue(){

front = rear = 0;

}

초기화 함수

front와 rear값을 같게하면 초기화 가능

void clear_queue(){

front = rear;

}

put 함수

(rear+1) % 큐 크기 == front 일 경우 오버 플로우 발생

int put(int k){

if((rear+1) % MAX == front){

printf("QUEUE OVER FLOW!\n\n");

return -1;

}else{

queue[rear] = k;

rear = ++rear % MAX;

return 1;

}

원형큐는 아래 그림과 같이 모듈러를 생각하면 편합니다.

get 함수

front와 rear가 같을 경우 빈 값이므로 언더플로우 발생

int get(){

int k;

if(front == rear){

printf("QUEUE UNDER FLOW!\n\n");

return -1;

}else{

k = queue[front];

front = ++front % MAX;

return k;

}

}

큐의 값을 출력하는 함수

void print_queue(){

printf("\n");

for(int i=front; i!=rear; ++i % MAX){

printf("queue[%d]=%d\n",i,queue[i]);

}

if(front == rear){

printf("queque is empty!!! \n");

}

printf("\n");

}

메인함수

큐의 크기가 10이므로 10번째 값을 넣을때에 오버플로우가 발생하고,

10번째 값을 가져올 때에는 언더플로우가 발생합니다.

void main(){

init_queue();

put(1);

put(3);

put(6);

put(9);

put(7);

put(2);

put(0);

put(0);

put(10);

put(20); // 10번째 값

printf("################################################################\n");

print_queue();

for(int i=0; i<3; i++){

get();

}

printf("################################################################\n");

print_queue();

for(int i=0; i<7; i++){

get();

}

printf("################################################################\n");

put(0);

put(0);

put(10);

clear_queue();

print_queue();

}

실행결과

---

참고 : C로 배우는 알고리즘 (이재규)

관련 포스팅

[Data Strcuture] - 트리(Tree)

[Data Strcuture] - 큐(Queue)

[Data Strcuture] - 스택(Stack)

[Data Strcuture] - 연결리스트(LinkedList)