큐

큐

- 큐(Queue)는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료 구조(Data Structure)

- 이러한 특성 때문에 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용됨

 

push : 큐에 데이터를 넣음

pop : 큐에서 데이터를 빼냄

 

push(7) - push(5) - push(4) - pop() - push(6) - pop()

 4 6

 

큐의 구현

- 큐는 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어 짐

- 가장 기본적인 형태의 자료구조로 구현 난이도는 낮은 편

 

배열을 이용한 큐 구현

* 큐의 선언

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
#define INF 9999999

int queue[SIZE];
int front = 0;
int rear = 0;

 

* 큐 삽입 함수

void push(int data) {
    if (rear >= SIZE) {
        printf("큐 오버플로우 발생. \n");
        return;
    }
    queue[rear++] = data;
}

 

* 큐 추출 함수

int pop() {
    if (front == rear) {
        printf("큐 언더플로우 발생.\n");
        return -INF;
    }
    return queue[front++];
}

 

* 큐 전체 출력 함수

void show() {
    printf("--- 큐의 앞 ---.\n");
    for (int i = front; i <rear; i++) {
        printf("%d\n", queue[i]);
    }
    printf("--- 큐의 뒤 ---.\n");
}

 

* 완성된 큐 사용하기

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10000
#define INF 9999999

int queue[SIZE];
int front = 0;
int rear = 0;

void push(int data) {
    if (rear >= SIZE) {
        printf("큐 오버플로우 발생. \n");
        return;
    }
    queue[rear++] = data;
}

int pop() {
    if (front == rear) {
        printf("큐 언더플로우 발생.\n");
        return -INF;
    }
    return queue[front++];
}

void show() {
    printf("--- 큐의 앞 ---.\n");
    for (int i = front; i <rear; i++) {
        printf("%d\n", queue[i]);
    }
    printf("--- 큐의 뒤 ---.\n");
}

int main(void){
    push(7);
    push(5);
    push(4);
    pop();
    push(6);
    pop();
    show();
    system("pause");
    return 0;
}

 

연결 리스트를 이용한 큐 구현

* 큐의 선언

#define INF 9999999

typedef struct {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
    int count;
} Queue;

 

큐 삽입 과정

front                                                                rear

data next(일반 노드) > data next(일반 노드) > data next(삽입할 노드)

 

* 큐 삽입 함수

void push(Queue *queue, int data) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if (queue->count == 0) { // 큐가 비어 있으면 카운트 값을 0으로
        queue->front = node; // 프론트에는 노드를 넣어줌
    }
    else {
        queue->rear->next = node;
    }
    queue->rear = node;
    queue->count++;
}

 

큐 추출 과정

                                        front                            rear

data next( 삭제할 노드) > data next(일반 노드) > data next(일반 노드)

 

* 큐 추출 함수

int pop(Queue *queue) {
    if (queue->count == 0) {
        printf("큐 언더플로우 발생");
        return -INF;
    }
    Node *node = queue->front;
    int data = node->data;
    queue->front = node->next;
    free(node);
    queue->count;
    return data;
}

 

* 큐 전체 출력 함수

void show(Queue *queue) {
    Node *cur = queue->front;
    printf("--- 큐의 앞 ---\n");
    while (cur != NULL) {
        printf("%d\n", cur->data);
        cur = cur->next;
    }
    printf("--- 큐의 뒤 ---\n");
}

 

* 완성된 큐 사용하기

#include <stdio.h>
#include <stdlib.h>
#define INF 9999999

typedef struct {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
    int count;
} Queue;

void push(Queue *queue, int data) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if (queue->count == 0) { // 큐가 비어 있으면 카운트 값을 0으로
        queue->front = node; // 프론트에는 노드를 넣어줌
    }
    else {
        queue->rear->next = node;
    }
    queue->rear = node;
    queue->count++;
}

int pop(Queue *queue) {
    if (queue->count == 0) {
        printf("큐 언더플로우 발생");
        return -INF;
    }
    Node *node = queue->front;
    int data = node->data;
    queue->front = node->next;
    free(node);
    queue->count;
    return data;
}

void show(Queue *queue) {
    Node *cur = queue->front;
    printf("--- 큐의 앞 ---\n");
    while (cur != NULL) {
        printf("%d\n", cur->data);
        cur = cur->next;
    }
    printf("--- 큐의 뒤 ---\n");
}

int main(void) {
    Queue queue;
    queue.front = queue.rear = NULL;
    queue.count = 0;
    push(&queue, 7);
    push(&queue, 5);
    push(&queue, 4);
    pop(&queue);
    push(&queue, 6);
    pop(&queue);
    show(&queue);
    system("pause");
    return 0;
}