[자료구조] 배열로 큐(Queue) 구현- C

<자료구조의 기본 큐>

기본적인 큐에 개념을 알고, 간단하게 구현해보자

큐는 선입선출 방식의 자료구조이다. (FIFO - First In First Out)

즉, 먼저 들어간 것이 먼저 나오는 형태이다.

(반대로 늦게 들어간 것은 늦게 나온다)

보통 큐를 구현할 때는 head / tail 이라는 변수가 있다.

(head 대신 front, tail 대신 rear도 많이 사용한다.

또 enqueue / dequeue 라는 함수를 구현하여 데이터를 넣고 뺀다.

(enqueue 대신 push,put을 / dequeue 대신 pop, get이라고 명명하기도 한다)

그리고 큐가 비어있는지 꽉 차있는지 확인하는 함수도 구현한다.

위는 데이터를 아무것도 넣지않은 초기화 상태의 큐이다.

size=10;

이렇게 배열을 선형으로 사용하여 만든 큐를 선형큐라고 한다.

큐의 출력위치와 입력 위치가 같다는 것은 데이터가 아무것도 없다는 것을 의미한다.

int Q[size];
int head = 0;
int tail = 0;


int isEmpty()
{
    if(head==tail)
    {
        return 1;
    }
    return 0;
}

5라는 데이터를 큐에 넣으면(enqueue) tail이 있던 자리에 '5' 데이터를 넣고 다음 위치로 이동한다 (tail++)

void enqueue(int data)
{
    Q[tail] = data;
    tail++;
}

큐에서 데이터를 삭제 / 가져오면 (dequeue) head 자리의 data를 가져오고, head를 다음 위치로 이동한다 (head++)

위의 그림에서는 dequeue를 두 번한 상태이다.

int dequeue()
{
    int res = Q[head];
    head++;
    return res; // 삭제한 데이터를 바로 return
}

큐가 꽉 찼다.

물론 tail이 가리키는 위치에 데이터가 들어갈 자리가 있지만, 데이터를 삽입한 후 tail++시 tail이 다음으로 갈 수가 없다.

그래서 위의 상태가 선형큐가 꽉 찬 상태라고 보는 것이다.

이 상태를 어떻게 구분하느냐하면 tail+1 == head 조건으로 확인이 가능하다.

그럼 위의 상황에서는 9+1=10 이므로 head =10와 같고,

아래의 상황에서도 3+1= 4 이므로 head=4와 같다.

int isFull()
{
    if(tail+1==head)
    {
        return 1;
    }
    return 0;
}

선형큐는 구현하기에 아주 간편하고, 쉽다는 장점이 있다.

그러나 데이터를 아주 많이 넣었다 뺐다가 하기에는 큰 배열이 필요하다는 단점과,

isFull 함수 설명을 할 때 보았듯이 배열을 100% 사용하지 못한다는 단점이 있다.

이 단점을 해결한 것이 원형큐이다.

원형큐는 다음 포스팅에 설명하겠다.

공부 노트