7. 데이터 구조 - Queue의 이해 및 구현

1. queue의 개념

스택의 경우, 나중에 들어온 데이터가 먼저 나가는 구조인 후입선출인 반면, 큐는 먼저 들어온 데이터가 먼저 나가는 구조로 이러한 특성은 선입선출(FIFO : first-in first-out)이라고 한다. 

또한 큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조로 이루어져있기때문에 스택에서 삽입과 삭제를 구현하기 위해 사용되었던 변수가 top 1개만 사용하였지만, 큐는 삽입에 관련된 변수를 rear 라고 하고, 삭제에 관련된 변수를 front라고 한다.

 

큐는 은행에서 기다리는 사람들의 대기열, 혹은 인터넷에서 전송되는 데이터 패킷들을 모델링하는데에 사용되곤 한다.  

2. queue의 ADT

그렇다면 queue의 ADT에 대해서 살펴보자.

일단 queue를 기본적인 배열을 통해서 구현한다고 가정했을 때, 

대기열이 비어 있는지 확인하는 과정 -> is_empty
대기열이 꽉 차있는지 확인하는 과정 -> is_full
맨 뒤에 대기열에 들어가는 과정 -> enqueue
맨 앞으로 대기열에서 빠져 나가는 과정 -> dequeue
맨 앞의 대기열이 무엇인지 확인하는 과정 -> peek

 

으로 나눌 수 있다.

 

 

3. queue의 구현

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
 
typedef struct {
    int front;
    int rear;
    int data[MAX_SIZE];
}quetype;
 
void init(quetype* q) {
    q->front = -1;
    q->rear = -1;
}
 
int is_empty(quetype* q) {
    if (q->front == q->rear) {
        return 1;
    }
    else
        return 0;
}
 
int is_full(quetype* q) {
    if (q->rear == MAX_SIZE - 1) {
        return 1;
    }
    else
        return 0;
}
 
void enqueue(quetype* q, int a) {
 
    if (is_full(q)) {
        printf("꽉 찼습니다.");
        return;
    }
    q->data[++(q->rear)] = a;
}
 
int dequeue(quetype* q) {
    if (is_empty(q)) {
        printf("비었습니다.");
        return -1;
    }
    int result = q->data[++(q->front)];
    return result;
 
}
 
void queue_print(quetype* q) {
    for (int i = 0; i < MAX_SIZE; i++) {
        if (i <= q->front || i > q->rear) {
            printf("|    ");
        }
        else {
            printf("| %2d ", q->data[i]); // 2칸 너비로 출력
        }
    }
    printf("|\n"); // 마지막 닫는 구분자 추가
}
 
int main(void) {
    int a = 0;
    quetype q;
 
    init(&q);
 
    enqueue(&q, 10);
    queue_print(&q);
    enqueue(&q, 20);
    queue_print(&q);
    enqueue(&q, 30);
    queue_print(&q);
 
    a = dequeue(&q);
    queue_print(&q);
    a = dequeue(&q);
    queue_print(&q);
    a = dequeue(&q);
    queue_print(&q);
 
    return 0;
}