자료구조 큐의 개념과 배열로 구현하는 방법

1. 큐란 무엇인가

 

큐(queue)는 뒤쪽으로 들어가서 앞쪽으로 나오는 자료 구조다. 스케줄링, 탐색 알고리즘 등에서 다방면으로 활용된다. 큐는 크게 데이터를 넣는 push, 데이터를 빼내는 pop 함수로 이루어진다. 스택과 마찬가지로 배열을 이용한 구현 방법과 연결 리스트를 이용한 구현 방법으로 나누어진다. 

 

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

 

자료구조 큐 그림

 

2. 큐를 배열로 구현하기

 

#include <stdio.h>
#define SIZE 10000
#define INF 99999999

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

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

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

 

먼저 큐의 사이즈를 10,000으로 미리 정하고, INF라는 변수를 임의의 무한대 수로 지정한다. front, rear는 각각 앞 인덱스, 뒤 인덱스로 처음에 모두 0이다. 

 

push() 함수는 매개변수로 정수형을 받아 rear에 1을 더한 위치에 데이터를 넣는다. 큐는 뒤에서부터 들어오기 때문이다. 그리고 원소의 개수가 앞서 지정한 사이즈 10,000을 넘기면 큐 오버플로우를 표시해준다. pop() 함수는 front에 해당하는 값을 꺼낸 다음 1을 더한다. front와 rear가 같으면 꺼낼 큐가 없기 또 반환 값은 반드시 존재해야 하기 때문에 마이너스 무한대를 리턴해서 오류가 있음을 함수를 호출한 곳에 알려준다. 

 

 

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();
}

큐의 처음
4
6
큐의 끝

 

push, pop 함수 임의로 실행 후 큐에 남은 원소들을 차례로 리턴하는 show() 함수를 만들어 출력해보면 앞에서 제시한 그림과 같은 결과가 나온다.