[알고리즘 이론] 큐(Queue)

큐(Queue)

큐(Queue)는 스택(Stack)과 반대의 개념을 갖고 있다. 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 특성을 띄고있는데 큐는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First-In First-Out) 특성을 띈다.

Ex> 매표소에서 표를 사는경우, 가장 먼저온 손님이 먼저 구매하게 된다. 

Ex> 보통 컴퓨터와 주변기기 사이에는 항상 큐가 존재한다. 그 이유는 컴퓨터의 CPU와 주변기기 사이에는 속도 차이가 있기 때문에 CPU를 효율적으로 사용하기 위하여 큐를 사용해야한다. 

 

queue의 구조

• 선입선출(FIFO: First-In First-Out) : 먼저 들어온 데이터가 먼저 나가는 구조이다.
• 큐는 뒤(Back,Rear)에서 새로운 데이터가 추가되고 앞(Front)에서 데이터가 하나씩 삭제된다. 여기서 알 수 있는건 스택의 경우 데이터 추가/제거가 같은 방향에서 일어나지만 큐의 경우에는 다른쪽에서 일어난다는 특징이 있다. (코딩안에서도 데이터 추가/제거에 관련해서 스택은 top 변수만 필요로 했지만 큐의 경우에는 추가와 관련된 rear 변수와 제거와 관련된 front 변수가 필요하다.
• 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화시키는 버퍼역할을 한다.

배열을 통해 구현한 큐

소스 코드를 분석하여 더 쉽게 큐를 이해해보자.

#include <stdio.h>
#include <stdlib.h>
 
// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
    element  data[MAX_QUEUE_SIZE];
    int  front, rear;
} QueueType;
 
// 오류 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
// 공백 상태 검출 함수
void init_queue(QueueType *q)
{
    q->front = q->rear = 0;
}
 
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
    return (q->front == q->rear);
}
 
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
 
// 원형큐 출력 함수
void queue_print(QueueType *q)
{
    printf("QUEUE(front=%d rear=%d) = ", 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 enqueue(QueueType *q, element item)
{
    if (is_full(q))
        error("큐가 포화상태입니다");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}
 
// 삭제 함수
element dequeue(QueueType *q)
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}
 
// 삭제 함수
element peek(QueueType *q)
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// ===== 원형큐 코드 끝 ======
 
int main(void)
{
    QueueType queue;
    int element;
 
    init_queue(&queue);
    printf("--데이터 추가 단계--\n");
    while (!is_full(&queue))
    {
        printf("정수를 입력하시오: ");
        scanf("%d", &element);
        enqueue(&queue, element);
        queue_print(&queue);
    }
    printf("큐는 포화상태입니다.\n\n");
 
    printf("--데이터 삭제 단계--\n");
    while (!is_empty(&queue))
    {
        element = dequeue(&queue);
        printf("꺼내진 정수: %d \n", element);
        queue_print(&queue);
    }
    printf("큐는 공백상태입니다.\n");
    return 0;
}

---

덱(deque)

덱(deque)이란 double-ended queue의 줄임말로서 큐의 front와 rear에서 모두 데이터 추가/제거가 가능한 큐를 의미한다. 덱은 front와 관련된 연산자들만 사용하면 스택이 되고, 삽입(데이터 추가)은 rear, 삭제(데이터 제거)는 front만을 사용하면 큐로 동작하는 특징이 있다.

#include <stdio.h>
#include <stdlib.h>
 
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
    element  data[MAX_QUEUE_SIZE];
    int  front, rear;
} DequeType;
 
// 오류 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}
 
// 초기화 
void init_deque(DequeType *q)
{
    q->front = q->rear = 0;
}
 
// 공백 상태 검출 함수
int is_empty(DequeType *q)
{
    return (q->front == q->rear);
}
 
// 포화 상태 검출 함수
int is_full(DequeType *q)
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
 
// 원형큐 출력 함수
void deque_print(DequeType *q)
{
    printf("DEQUE(front=%d rear=%d) = ", 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_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 get_front(DequeType *q)
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
 
void add_front(DequeType *q, element val)
{
    if (is_full(q))
        error("큐가 포화상태입니다");
    q->data[q->front] = val;
    q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
 
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];
}
 
element get_rear(DequeType *q)
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    return q->data[q->rear];
}
 
int main(void)
{
    DequeType queue;
 
    init_deque(&queue);
    for (int i = 0; i < 3; i++) {
        add_front(&queue, i);
        deque_print(&queue);
    }
    for (int i = 0; i < 3; i++) {
        delete_rear(&queue);
        deque_print(&queue);
    }
    return 0;
}