[C] 큐 개념, 종류 및 작동 방식, 코드 정리

큐

---

먼저 집어 넣은 데이터가 먼저 나오는 FIFO ( First In First Out ) 구조로 저장되는 형식을 말합니다.

프린터의 출력, 키보드 입력 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에서  사용됩니다.

큐는 Put ( 삽입 ), Get ( 삭제 ) 를 이용하여 구현됩니다.

Put 은 큐에 자료를 넣는 것을, Get 은 큐에서 자료를 꺼내는 것을 의미합니다.

Front 와 Rear 은 데이터의 위치를 가르키며, Front 는 데이터를 Get 할 수 있는 위치, Rear 는 데이터를 Put 할 수 있는 위치를 의미합니다.

큐가 가득차서 자료를 더이상 넣을 수 없는 경우를 오버플로우, 큐가 비어있어 자료를 꺼낼수 없는 경우를 언더플로우라고 합니다.

큐의 종류 및 작동방식

---

선형과 환형이 있습니다.

선형의 개념 및 작동방식

막대 모양으로 된 큐 입니다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 자료를 꺼내거나 한 칸씩 옮겨야 한다는 단점이 있습니다.

ENQ 는 enque 의 약자로 Put 을 , DEQ 는 deque 의 약자로 Get 을 의미합니다.

1. A 가 삽입(Put)됩니다.

2. B 가 삽입(Put)됩니다.

3. C 가 삽입(Put)됩니다.

4. A 가 삭제(Get)됩니다.

5. D 가 삽입(Put)됩니다.

6. D 가 큐의 끝에 도달하였으므로 E 는 큐에 삽입되지 못합니다.

7. B 가 삭제(Get)됩니다.

환형의 개념 및 작동방식

선형 큐의 문제점을 보완항 방식입니다.

Front 가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내서 원형으로 연결하는 방식입니다. 원형 큐라고도 칭합니다.

1. A 가 삽입(Put)됩니다.

2. B 가 삽입(Put)됩니다.

3. C 가 삽입(Put)됩니다.

4. D 가 삽입(Put)됩니다.

5. A 가 삭제(Get)됩니다.

6. D 가 큐의 끝에 도달하였으므로 E 를 큐의 맨 앞으로 보내 빈 공간이 있는 경우 삽입(Put)합니다.

링크드 큐

연결 리스트를 사용하여 만든 큐로, 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않습니다.

환형 큐 방식으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리합니다.

배열로 구현한 환형 큐 소스

---

#include <stdio.h>

#define MAXSIZE 10

int queue[MAXSIZE];
int front, rear;

void put(int val) {

    if ((rear+1) % MAXSIZE == front) {
        printf ("Queue Overflow.");
    }

    queue[rear] = val;
    rear = ++ rear % MAXSIZE;
}

int get (void) {
    int ret;

    if (front == rear) {
        printf ("Queue Underflow.");
        return -1;
    }

    ret = queue[front];
    front = ++front%MAXSIZE;
    return ret;
}
  
void main(void)
{
    int i;
    int j;
    int k;
    front = 0;
    rear = 0;

    put(5);
    put(4);
    i = get();
    j = get();
    put(7);
    printf("%d, %d\n", i, j);
    for( k = front; k != rear; k = ++k%MAXSIZE)
      printf("%d, ", queue[k]);
}