큐(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' 카테고리의 다른 글
| [C] 삽입 정렬(Insertion Sort) (0) | 2019.04.19 |
|---|---|
| [C] 선택 정렬(Selection Sort) (0) | 2019.04.19 |
| [C] 트리(Tree) (0) | 2019.04.07 |
| [C] 스택(Stack) (1) | 2019.03.29 |
| [C] 연결리스트(LinkedList) (0) | 2019.03.28 |