[자료구조] 큐(QUEUE)를 알아보자!

큐

---

먼저 들어온 데이터가 먼저 나가는 자료구조 -> 선입선출(First-In First-Out) ex) 매표소 대기줄: 먼저 온 사람이 먼저 계산

종류: 선형큐, 원형 큐, 덱... 

• enqueue: 큐의 끝에 데이터 추가
• dequeue: 큐 맨 앞의 데이터 제거 & 반환

● 큐의 연산

• init(q) - 큐 초기화
• is_empty(q) - 큐가 공백상태인지 검사
• is_full(q) - 큐가 포화상태인지 검사
• enqueue(q,e) - 큐의 끝에 데이터(e) 추가
• dequeue(q) - 큐의 맨 앞 데이터 제거 및 반환
• peek(q) - 큐의 맨 앞 데이터 반환 

 

● 선형큐(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 -> front = -1;
    q -> rear = -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;
    }
}

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

// dequeue
int dequeue(QueueType *q) {
    if (is_empty(q)){
        error("큐가 공백상태입니다.");
        return -1;
    }
    int item = q -> data[++(q->front)];
    return item;
}
                 
int main(void) {
    QueueType q;
    
    init_queue(&q);
    
    enqueue(&q, 10);
    queue_print(&q);
    enqueue(&q, 20);
    queue_print(&q);
    enqueue(&q, 30);
    queue_print(&q);
    
    dequeue(&q);
    queue_print(&q);
    dequeue(&q);
    queue_print(&q);
    dequeue(&q);
    queue_print(&q);
    
    return 0;
}

이렇게 실행해 보시면 queue의 enqueue와 dequeue 과정을 볼 수 있습니다 :)

출력 결과

 

● 원형큐(Circular Queue)

원형 큐의 경우도 선형 큐와 같이 1차원 배열을 사용하여 메모리에 순차적으로 데이터를 저장한다는 점에서는 같지만 원형 큐와 선형 큐의 차이점은 원형 큐는 논리적으로 배열의 처음과 끝이 연결되어있다고 간주합니다. 

이렇게 함으로써 선형큐에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없었던 반면, 원형 큐는 Dequeue로 발생한 배열의 빈 공간을 활용할 수 있는 이점을 얻을 수 있습니다.

배열을 이용해 원형 큐를 구현해 보겠습니다.

선형큐의 구현과 어떤 점이 다른지 비교해보시면 좋을 것 같습니다!

#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 -> front = 0;
    q -> rear = 0;
}

void queue_print(QueueType *q) {
    printf("front: %d, rear: %d \n", q -> front, q -> rear);
    
    if (!is_empty(q)){
        int i = q -> front;
        do{
            i = (i+1) % MAX_QUEUE_SIZE;
            printf("%d |", q->data[i]);
            if (i == q -> rear){
                break;
            }
        } while(i != q->front);
    }
    printf("\n");
}

int is_full(QueueType *q){
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q -> front);
}

int is_empty(QueueType *q) {
    return (q->front == q ->rear);
}

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

// dequeue
int dequeue(QueueType *q) {
    if (is_empty(q)){
        error("큐가 공백상태입니다.");
        return -1;
    }
    
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q -> data[q->front];
}
                 
int main(void) {
    QueueType q;
    int element = 10;
    
    init_queue(&q);
    
    printf("데이터 추가 단계 \n\n");
    
    while(!is_full(&q)){
        enqueue(&q, element);
        queue_print(&q);
        element += 10;
    }
    printf("큐 포화상태 \n\n");
    
    printf("데이터 삭제 단계 \n\n");
    
    while(!is_empty(&q)){
        element = dequeue(&q);
        printf("꺼낸 정수: %d \n", element);
        queue_print(&q);
    }
    
    printf("큐 공백상태 \n\n");
    return 0;
}

 

출력 결과

 

● 덱(Deque)

deque은 double-ended 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];
} DequeType;

// 오류 함수
void error(char *message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void init_deque(DequeType *q){
    q -> front = 0;
    q -> rear = 0;
}

int is_full(DequeType *q){
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q -> front);
}

int is_empty(DequeType *q){
    return (q->front == q ->rear);
}

void deque_print(DequeType *q) {
    printf("front: %d, rear: %d \n", q -> front, q -> rear);
    
    if (!is_empty(q)){
        int i = q -> front;
        do{
            i = (i+1) % MAX_QUEUE_SIZE;
            printf("%d |", q->data[i]);
            if (i == q -> rear){
                break;
            }
        } while(i != q->front);
    }
    printf("\n");
}

// 삽입 함수

void add_front(DequeType *q, element item){
    if(is_full(q)){
        error("큐가 포화상태입니다.");
    }
    
    q -> data[q->front] = item;
    q -> front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

void add_rear(DequeType *q, element item){
    if(is_full(q)){
        error("큐가 포화상태입니다.");
    }
    
    q -> rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q -> data[q->rear] = item;
}

// 삭제 함수

element delete_front(DequeType *q){
    if(is_empty(q)){
        error("큐가 공백상태입니다.");
    }
    
    q -> front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q -> data[q->front];
}

element delete_rear(DequeType *q){
    int prev = q -> rear;
    
    if(is_empty(q)){
        error("큐가 공백상태입니다.");
    }
    
    q -> rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q -> data[prev];
}
                 
int main(void) {
    DequeType q;
    init_deque(&q);
    
    for(int i = 0;i < 4; i++){
        if (i < 2){
            add_front(&q, i);
        }else{
            add_rear(&q, i);
        }
        deque_print(&q);
    }
    
    printf("\n");
    
    for(int i = 0;i < 4; i++){
        
        if (i<2){
            delete_rear(&q);
        }else{
            delete_front(&q);
        }
        deque_print(&q);
    }
    return 0;
}

결과: