[C] 큐(Queue)

큐(Queue)

- 먼저 들어온 데이터가 먼저 나가는 구조. (선입 선출(FIFO: First-In-First-Out))

- 큐에서 삽입이 일어나는 곳을 '후단(rear)'이라고 하고, 삭제가 일어나는 곳을 '전단(front)'이라고 함.

 

선형 큐 (Linear Queue)

- 배열로 구현된 큐.

- 이해하기 쉽다는 장점이 있음.

- 문제점

-> front와 rear의 값이 계속 증가만 하기 때문에 언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있어도 사용하지 못함. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜야 함. (상당한 시간이 걸리고 프로그램 코딩이 복잡해짐.)

 

원형 큐 (Circular Queue)

- 선형 큐의 문제점을 보완하기 위해 배열을 원형으로 생각하여 만든 큐.

- front와 rear의 값이 같으면 원형 큐가 비어 있음을 나타냄.

- 원형 큐에서는 하나의 자리는 항상 비워둠. (포화 상태와 공백 상태를 구별하기 위해)

- front==rear이면 공백 상태가 되고, front가 rear보다 하나 앞에 있으면 포화 상태가 됨.

 

// 원형 큐 프로그램

#include <stdio.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;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q) {
    return (q->front == q->rear);    // front == rear이면 공백 상태
}

// 포화 상태 검출 함수
int is_full(QueueType *q) {
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);    // front == (rear + 1)이면 포화 상태
}

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

// 삭제 함수
element dequeue(QueueType *q) {
    if (is_empty(q)) {
        error("큐가 공백상태입니다.");
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

// 피크 함수
element peak(QueueType *q) {
    if ((is_empty)) {
        error("큐가 공백상태입니다.");
    }
    return q->queue[(q->front + 1) % MAX_QUEUE_SIZE];
}

// 주 함수
void main() {
    QueueType q;
    init(&q);
    printf("front=%d rear=%d\n", q.front, q.rear);                                                                          
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    printf("front=%d rear=%d\n", q.front, q.rear);
}

 

 

연결된 큐 (Linked Queue)

- 연결리스트로 구현된 큐.

- 배열로 구현된 큐에 비하여 크기가 제한되지 않는다는 장점이 있음.

- 배열로 구현한 큐에 비하여 코드가 약간 더 복잡해지고, 링크 필드 때문에 메모리 공간을 더 많이 사용한다는 단점이 있음.

 

// 연결된 큐 프로그램
#include <stdio.h>
#include <malloc.h>

typedef int element;    // 요소의 타입
typedef struct QueueNode { // 큐의 노드 타입
    element item;
    struct QueueNode *link;
} QueueNode;

typedef struct {        // 큐 ADT 구현
    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);
}

// 삽입 함수
void enqueue(QueueType *q, element item) {
    QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
    if (temp == NULL) {
        error("메모리를 할당할 수 없습니다.");
    }
    else {
        temp->item = item;        // 데이터 저장
        temp->link = NULL;        // 링크 필드를 NULL로 설정
        if (is_empty(q)) {            // 큐가 공백이라면
            q->front = temp;
            q->rear = temp;
        }
        else {        // 큐가 공백이 아니면
            q->rear->link = temp;    // 순서가 중요
            q->rear = temp;
        }
    }
}

// 삭제 함수
element dequeue(QueueType *q) {
    QueueNode *temp = q->front;
    element item;
    if (is_empty(q)) {        // 공백 상태
        error("큐가 비어 있습니다.");
    }
    else {
        item = temp->item;        // 데이터를 꺼낸다.    
        q->front = q->front->link;    // front를 다음 노드를 가리키도록 한다.                                                 
        if (q->front == NULL) {        // 공백 상태
            q->rear = NULL;
        }
        free(temp);        // 노드 메모리 해제
        return item;        // 데이터 반환
    }
}

// peek 함수
element peek(QueueType *q) {
    if (is_empty(q)) {
        error("큐가 비어있습니다.");
    }
    else {
        return q->front->item;        // 데이터 반환 
    }
}

// 연결된 큐 테스트 함수
void main() {
    QueueType q;

    init(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
    printf("dequeue()=%d\n", dequeue(&q));
}

 

덱 (Deque)

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

- 덱은 스택과 큐의 연산들을 모두 가지고 있음.

- 덱은 보통 이중 연결 리스트로 구현됨. (전단과 후단에서 모두 삽입, 삭제가 가능해야 하기 때문에 양쪽으로 링크를 가지고 있어야 편리하기 때문.)

- 이중 연결리스트의 첫 번째 노드와 마지막 노드를 가리키는 포인터를 동시에 가지고 있어야 함.

- 덱과 관련된 변수는 첫 번째 노드를 가리키는 변수인 head와 마지막 노드를 가리키는 tail이 됨.

 

// 덱 프로그램                                                                                                              

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

typedef int element;        // 요소의 타입

typedef struct DlistNode {    // 노드의 타입
    element data;
    struct DlistNode *llink;
    struct DlistNode *rlink;
} DlistNode;

typedef struct DequeType {        // 덱의 타입
    DlistNode *head;
    DlistNode *tail;
} DequeType;

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

// 초기화 함수
void init(DequeType *dq) {
    dq->head = dq->tail = NULL;
}

// 공백 검출 함수
int is_empty(DequeType *dq) {
    if (dq->head == NULL) return TRUE;
    else return FALSE;
}

// 노드 생성 
DlistNode *create_node(DlistNode *llink, element item, DlistNode *rlink) {
    DlistNode *node = (DlistNode *)malloc(sizeof(DlistNode));
    if (node == NULL) error("메모리 할당 오류");
    node->llink = llink;
    node->data = item;
    node->rlink = rlink;
    return node;
}

// 후단에 삽입
void add_rear(DequeType *dq, element item) {
    DlistNode *new_node = create_node(dq->tail, item, NULL);

    if (is_empty(dq)) {
        dq->head = new_node;
    }
    else {
        dq->tail->rlink = new_node;
    }
    dq->tail = new_node;
}

// 전단에 삽입
void add_front(DequeType *dq, element item) {
    DlistNode *new_node = create_node(NULL, item, dq->head);

    if (is_empty(dq)) {
        dq->tail = new_node;
    }
    else {
        dq->head->llink = new_node;
    }
    dq->head = new_node;
}

// 전단에서의 삭제
element delete_front(DequeType *dq) {
    element item;
    DlistNode *removed_node;

    if (is_empty(dq)) error("공백 덱에서 삭제");
    else {
        removed_node = dq->head;        // 삭제할 노드
        item = removed_node->data;        // 데이터 추출
        dq->head = dq->head->rlink;        // 헤드 포인터 변경
        free(removed_node);                    // 메모리 공간 반납
        
        if (dq->head == NULL){                // 공백 상태이면
            dq->tail = NULL;
        }
        else {                                        // 공백 상태가 아니면
            dq->head->llink = NULL;        
        }
    }
    return item;
}

// 후단에서의 삭제
element delete_rear(DequeType *dq) {
    element item;
    DlistNode *removed_node;

    if (is_empty(dq)) error("공백 덱에서의 삭제");
    else {
        removed_node = dq->tail;            // 삭제할 노드
        item = removed_node->data;        // 데이터 추출
        dq->tail = dq->tail->llink;            // 테일 포인터 변경
        free(removed_node);                    // 메모리 공간 반납

        if (dq->tail == NULL) {                // 공백 상태이면
            dq->head = NULL;
        }
        else {                                        // 공백 상태가 아니면
            dq->tail->rlink = NULL;
        }
    }
    return item;
}

// 출력 함수
void display(DequeType *dq) {
    DlistNode *p;
    printf("(");
    for (p = dq->head; p != NULL; p = p->rlink) {
        printf("%d ", p->data);
    }
    printf(")\n");
}

// 주 함수
void main() {
    DequeType deque;

    init(&deque);
    add_front(&deque, 10);            // 전단에 10 삽입
    add_front(&deque, 20);            // 전단에 20 삽입
    add_rear(&deque, 30);            // 후단에 30 삽입
    display(&deque);                    // 덱의 내용 출력

    delete_front(&deque);            // 전단에서 삭제
    delete_rear(&deque);            // 후단에서 삭제
    display(&deque);                    // 덱의 내용 출력
}

 

큐의 응용

 

1) 버퍼

- 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화시키는 버퍼 역할을 담당함.

예) CPU와 프린터 사이의 프린팅 버퍼, CPU와 키보드 사이의 키보드 버퍼 등

- 대개 데이터를 생산하는 생산자 프로세스가 있고 데이터를 소비하는 소비자 프로세스가 있으며 이 사이에 큐로 구성되는 버퍼가 존재함.
- 만약 동일한 컴퓨터에서 생산자와 소비자 프로세스가 동시에 수행된다면 공유되는 큐를 동시에 접근하여 문제가 발생할 수 있음.
-> 공유되는 큐를 사용하기 전에 큐를 사용한다고 먼저 락(lock)을 거는 것이 필요함.

   (내가 큐를 조작하고 있는 동안에 동시에 수행되는 다른 프로세스가 큐를 건드리지 않도록 하는 것)

 

2) 시뮬레이션
- 큐는 주로 큐잉 이론에 따라 컴퓨터로 시스템의 특성을 시뮬레이션하여 분석하는 데 이용됨.
- 큐잉 모델은 고객에 대한 서비스를 수행하는 서버와 서비스를 받는 고객들로 이루어짐.

 

내용 출처 : C언어로 쉽게 풀어쓴 자료구조 (천인국 외 지음, 생능출판사)