[자료구조] C언어로 큐(Queue) , 원형 큐(Circular Queue) 구현, 소스코드

 

안녕하세요, 이번엔 자료구조의 아주 기본인 큐를 배워보도록 하겠습니다.

 

큐(Queue)란 사전적 의미로 줄, 대기행렬, 꼬리 등의 의미가 있는데요,

 

놀이공원 같은 곳에서 먼저 줄을 서면 먼저 입장하게 되는데 큐는 이러한 방식입니다.

 

지난번에 배운 스택과 어떤 차이점이 있을까요?

 

리스트의 한쪽 끝에서만 삽입과 삭제가 일어나기 때문에

 

최근에 넣은 데이터가 먼저 나오는 스택(LIFO 방식)과 달리

 

큐는 먼저 넣은 데이터가 먼저 나오는  FIFO(First In First Out) 방식으로,

 

리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제가 가능한 구조입니다.

 

스택과의 매우 큰 차이를 아시겠나요?

 

그림으로 보면 다음과 같습니다.

 

 

 

 

위 그림처럼 한쪽(front)에서는 삭제가 가능하고,

 

다른 한쪽(rear)에서는 삽입이 가능한 구조입니다.

 

이를 C 소스로 확인해보겠습니다.

 

#include <stdio.h>
#define MAX 100
int front=-1;
int rear=-1;
int queue[MAX];
 
int IsEmpty(void){
    if(front==rear)//front와 rear가 같으면 큐는 비어있는 상태 
        return true;
    else return false;
}
int IsFull(void){
    int tmp=(rear+1)%MAX; //원형 큐에서 rear+1을 MAX로 나눈 나머지값이
    if(tmp==front)//front와 같으면 큐는 가득차 있는 상태 
        return true;
    else
        return false;
}
void addq(int value){
    if(IsFull())
        printf("Queue is Full.\n");
    else{
rear = (rear+1)%MAX;
 queue[rear]=value;
 }
 
}
int deleteq(){
    if(IsEmpty())
        printf("Queue is Empty.\n");
    else{
        front = (front+1)%MAX;
        return queue[front];
    }
}
 
int main(){
    
    addq(4);
    addq(7);
    addq(12);
    printf("%d\n",deleteq());
    printf("%d\n",deleteq());
    printf("%d\n",deleteq());
deleteq();
    
    return 0;
}

 

 

 

 

 

 

 

 

전체 소스코드입니다. 아주 정말 매우 간단하게 구현해 보았는데요,

 

위의 큐의 모형과 달리 소스는 원형 큐로 작성하였습니다.

 

기본적인 큐는 front값이 증가함에 따라 실제 가용한 배열의 크기가 줄어들지만,

 

원형 큐는 아래와 같은 구조로 rear값이 MAX를 넘어가면 다시 배열의 첫번째 위치로 들어가게 되어

 

배열을 효율적으로 사용하게 됩니다.

 

 

 

 

우선 입력값의 위치를 알리는 rear 와 출력될 위치를 알리는 front값을 각각 -1로 초기화해줍니다.

 

이 front값과 rear값으로 큐의 상태를 알 수 있는데요,

 

rear와 front의 값이 같다면 큐가 비어있음을 알 수 있고,

 

(rear+1)%MAX 값과 front의 값이 같다면 큐가 가득 차 있음을 알 수 있습니다.

 

위 그림을 보면서 생각하시면 쉽게 이해하실 수 있습니다.

 

큐에 데이터를 추가하려면 ++rear번째 항에 값을 넣어주고,

 

데이터를 빼려면 ++front번째 항에서 값을 가져옵니다.

 

 

 

소스 내에 임의로 4, 7, 12 순서대로 입력하였고,

 

deleteq()를 통해 하나씩 출력해보았습니다.

 

 

 

 

위와 같이 먼저 입력된 값이 먼저 출력되어

 

순서대로 4, 7, 12가 출력됨을 알 수 있습니다.

 

또한 큐가 비어있는 상태에서 deleteq()를 한 번 더 실행하였을때,

 

Queue is Empty가 출력되어 더이상 출력할 데이터가 없음을 알 수 있습니다.