[자료구조][C] 큐 _ 선형큐(Linear Queue)

💬 큐

앞서 배웠듯 스택의 경우 나중에 들어온 데이터가 먼저 나가는 구조이다. 그러나 큐는 먼저 들어온 데이터가 먼저 나가는 구조이다.

즉, FIFO (First In First Out) 선입선출 형태를 띈다. 

출처 - yongseong.log

데이터는 큐의 후단(rear)에 삽입되고 전단(front)를 통해 나간다. 즉, 삽입과 삭제가 같은 곳이 아니라는 것 !

 

- 전단(front) : 데이터의 삭제 연산 (가장 먼저 들어왔던 데이터가 쌓여있는 쪽) -> dequeue 연산

- 후단(rear) : 데이터의 삽입 연산 (가장 나중에, 최근에 삽입된 데이터가 쌓여있는 쪽) -> enqueue 연산

 

💬 큐의 연산

enqueue: 큐의 rear 에 새로운 원소를 삽입하는 연산 

dequeue: 큐의 front에 있는 원소를 큐로부터 삭제하고 반환하는 연산

peek: 큐의 front에 있는 원소를 제거하지 않고 반환하는 연산

is_empty: 큐가 비었는지 검사

is_full: 큐가 포화상태인지 검사

---

 

💬 선형 큐 (Linear Queue) 코드

#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(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(" %d | ",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);
}

 

 

---

 

 

void init_queue(QueueType* q){
    q->rear= -1;
    q->front= -1;
}

초기화 함수이다. rear과 front의 값을 -1로 초기화 해준다. 왜냐하면 데이터가 0번 인덱스부터 저장되기 때문이다. 

데이터가 증가(enqueue)할 경우에는 rear 값을 증가시키고 그 위치에 데이터를 저장한다. 그리고 데이터를 삭제(dequeue) 할 때에는 front를 하나 증가시키고 front가 가리키는 위치에 있는 데이터를 삭제하여 반환한다.

따라서, 선형 큐에서의 공백상태는 front와 rear이 같아진 상태이다. 데이터가 삭제되면 front의 값이 증가하면서 rear값과 가까워 지게된다. 

 

 

void queue_print(QueueType* q){
    for (int i=0;i<MAX_QUEUE_SIZE;i++){
        if (i<=q->front || i>q->rear)
            printf(" | ");
        else
            printf(" %d | ",q->data[i]);
    }
    printf("\n");
}

queue 안에 있는 데이터 값을 출력해주는 함수이다. 먼저 변수 i가 미리 설정해둔 큐의 사이즈보다 작을때 까지 i의 값을 증가시켜준다.

만약 i 보다 전단, front 의 값이 작거나 같거나 i보다 후단, rear의 값이 크다면 안에 데이터가 없는 것이므로 | 만을 출력해준다.

이때 주의해야할 점은 rear의 값과 i의 값이 같다면 데이터가 존재한다는 뜻이다. 

 

 

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;
}

is_full 함수는 큐가 포화상태인지 확인해준다. 만약 rear의 값이 큐의 최대 사이즈 -1 (인덱스가 -1 부터 시작하므로) 일 경우는 큐의 포화상태임을 뜻한다. 따라서 TRUE 값인 1을 반환해준다.

 

is_empty 함수는 큐가 공백상태인지 확인한다. 만약 큐의 front 값과 rear값이 동일할 경우 이는 공백상태임을 뜻한다.

 

 

void enqueue(QueueType* q,int item)
{
    if (is_full(q)){
        error("큐가 포화상태입니다.");
        return;
    }
    q->data[++(q->rear)]=item;
}

enqueue 함수는 데이터 값을 넣어준다. 따라서 매개변수로 넣을 데이터 변수인 Item을 설정해준다. 만약 큐가 포화상태이면 데이터가 들어가지 못하므로 if_full 함수를 통해 큐가 포화상태인지 확인해준다. 스택의 push 함수와 마찬가지로 q-> rear의 값을 먼저 증가시키고 그 값에 item 을 넣어주면 된다. 

 

 

int dequeue(QueueType* q){
    if(is_empty(q)){
        error("큐가 공백상태입니다.");
        return -1;
    }
    int item=q->data[++(q->front)];
    return item;
}

dequeue 함수는 데이터를 삭제해주는 역할을 한다. 따라서 큐의 상태가 공백임을 확인해야 한다. 만약 큐가 공백상태일 경우 에러 메시지를 나타낸다. 이 함수도 위의 enqueue와 마찬가지로 미리 front를 증가시키고 그 값에 데이터를 넣어준다. 

---

이러한 선형 큐는 CPU 작업 스케줄링에서도 사용된다. 큐를 사용하여 우선순위를 결정해주는 것이다. 그러나 이러한 선형 큐는 front와 rear값이 계속해서 증가만 하기 때문에 배열의 앞부분이 비어있더라도 사용하지 못하는 단점을 지닌다.

 

이러한 작업을 가능하게 하기 위해서는 주기적으로 모든 요소들을 후단으로부터 전단으로 이동시켜야하는데 매번 이동시키면 코드의 수행시간이 오래 걸리며 코드 또한 복잡해진다. 따라서 훨씬 효율적으로 작업할 수 있는 원형 큐가 나타났다.