[6] Queue

1. Queue란?

- 스택과는 다르게 먼저 들어온 데이터가 먼저 나가는 구조, 선입 선출(FIFO : First-In First-Out)

- 대표적인 예로 매표소가 있음.

- 삽입이 일어나는 후단(rear)과, 삭제가 일어나는 전단(front)로 이루어져있다.

- 가장 중요한 연산은 삽입(enqueue)과 삭제(dequeue)

- 가장 많이 이용되는 분야는 컴퓨터를 이용해 현실 세계의 실제 상황을 시뮬레이션 하는 곳임.

- 예를 들어 은행 대기열, 공항에서 이륙하는 비행기들, 인터넷에서 전송되는 데이터 패킷들을 모델링하는 큐.

- OS에서도 중요하게 사용됨. CPU를 효율적으로 사용하기 위한 큐가 있음(Ready Queue)

2. Queue의 종류

1) 선형 큐(Linear Queue)

- 데이터가 증가하면 rear가 뒤로 가고, 데이터를 삭제하려면 front가 뒤로 가면 됨.

- 문제점은, 언젠간 front와 rear가 배열의 끝에 도달할 것이라는 점. 즉, 앞이 비어도 사용하지 못한다는 점.

- 그래서 주기적으로 모든 요소들을 앞으로 당겨야 함. 이러면 시간도 오래걸리고, 프로그램 코딩도 복잡해짐.

2) 원형 큐(Circular Queue)

- 선형 큐의 문제점을 해결해줄 원형 큐.

- front와 rear가 배열의 끝인 MAX_QUEUE_SIZE-1에 도달하면, 다음에 증가되는 값은 0이 되도록 하는 것.

- 즉, 배열의 처음과 끝이 이어져 있다고 생각하는 것.

- 선형 큐와는 다르게 front와 rear의 개념이 살짝 바뀐다.

1) 초기 값은 -1이 아닌 0

2) front는 항상 큐의 첫 번째 요소의 하나 앞, rear는 마지막 요소를 가리킨다.

3) 데이터가 들어오면 rear가 한 칸 움직이고, 움직인 위치에 데이터를 넣는다.

4) 데이터를 삭제할 때는 front가 한 칸 움직이고, 움직인 위치의 데이터를 삭제한다.

- front == rear면 공백, front가 rear보다 하나 앞에 있으면 포화.

3. Queue의 구현

1) 원형 큐

#include<stdio.h>
#include<stdlib.h>
 
#define max_queue_size 100
 
typedef int element;
typedef struct {
    element queue[max_queue_size];
    int front, rear;
}QueueType;
 
void error(char *message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
void init(QueueType *q) {
    q->front = q->rear = 0;
}
 
// front랑 rear가 같으면 공백으로 간주.
int is_empty(QueueType *q) {
    return (q->front == q->rear);
}
 
// rear의 한 칸 앞이 front면 큐 포화
int is_full(QueueType *q) {
    return ((q->rear + 1) % max_queue_size == q->front);
}
 
void enqueue(QueueType *q, element item) {
    if (is_full(q))
        error("큐 포화\n");
 
    // rear를 한 칸 앞으로 이동시키고
    q->rear = (q->rear + 1) % max_queue_size;
    
    // 해당 위치에 item을 집어넣는다.
    q->queue[q->rear] = item;
}
 
element dequeue(QueueType *q) {
    if (is_empty(q))
        error("큐 공백\n");
 
    // front 앞으로 한 칸 움직임.
    q->front = (q->front + 1) % max_queue_size;
 
    return q->queue[q->front];
}
 
int main() {
 
    QueueType q;
    init(&q);
 
    printf("front : %d, rear : %d\n", q.front, q.rear);
 
    for (int i = 0; i < 3; i++)
        enqueue(&q, i);
 
    for (int i = 0; i < 3; i++) 
        printf("dequeue() = %d\n", dequeue(&q));
 
    printf("front : %d, rear : %d\n", q.front, q.rear);
    return 0;
}

2) 링크드리스트로 구현된 큐

- 배열로 구현된 큐에 비해 크기가 제한되지 않는다는 장점을 갖고 있음.

- 그러나, 배열로 된 큐보다는 코드가 복잡하고, 링크 필드 때문에 메모리 공간을 많이 사용함.

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
 
typedef int element;
typedef struct QueueNode {
    element item;
    QueueNode *link;
}QueueNode;
 
typedef struct {
    QueueNode *front, *rear;
}QueueType;
 
void error(char *message) {
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
void init(QueueType *q) {
    q->front = q->rear = NULL;
}
 
int is_empty(QueueType *q) {
    return q->front == NULL;
}
 
// 현재의 큐와, 넣을 item을 파라미터로 전달받음.
void enqueue(QueueType *q, element item) {
 
    // 전달받은 item을 넣어줄 temp Node 생성.
    QueueNode *temp = (QueueNode*)malloc(sizeof(QueueNode));
 
    if (temp == NULL)
        error("메모리 할당 불가능\n");
    else {
        temp->item = item;
        temp->link = NULL;
 
        // 큐가 비어있다면
        if (is_empty(q)) {
            // temp를 front, rear로 설정해준다.
            q->front = temp;
            q->rear = temp;
        }
 
        //큐가 공백이 아니라면
        else {
 
            // rear가 가장 마지막에 삽입된 노드를 가리키므로, rear의 next가 temp를 가리키게 하고
            q->rear->link = temp;
            
            //rear를 temp로 바꿔준다.
            q->rear = temp;
        }
    }
}
 
element dequeue(QueueType *q) {
 
    // 지울 자리를 임시로 가리키고 있을 temp
    QueueNode *temp = q->front;
    element item = temp->item;
 
    if (is_empty(q))
        error("큐가 비어있음\n");
    else {
        q->front = q->front->link;
        if (q->front == NULL) // 공백 상태인 경우
            q->rear = NULL;    // rear도 초기화 해준다.
        free(temp);
        return item;
    }
}
 
element peek(QueueType *q) {
    if (is_empty(q))
        error("큐 공백\n");
    else return q->front->item;
}
 
void main() {
    QueueType q;
 
    init(&q);
 
    for (int i = 1; i <= 3; i++)
        enqueue(&q, i);
    for (int i = 0; i < 3; i++) 
        printf("dequeue() = %d\n", dequeue(&q));
 
}

4. 덱(deque)이란?

- double-ended queue의 줄임말로, 전단과 후단 모두에 삽입과 삭제가 가능한 큐를 의미함.

- 굳이 구현까지 할 필요는 없을 것 같으니 패스.

5.